For each integer n, write out n in base 10 and let g(n) be the product of the nonzero digits appearing.

I can't believe I spent this much time on this question but here goes...

SUMMARY: Digital product question is really hard, requires subtle
information about distributions of terms in sequences.

A recent question on the net asked the following question: for each
integer n, write out n in base 10 and let g(n) be the product of the
nonzero digits appearing. Then iterate g until you get a single digit,
f(n)=lim_{k->\infty} g^k (n) \in {1,2,...,9} [Editor: was {1,2,...,10}].
The question asks for the percentage of time each of the digits arises
as the result f(n), that is, asks for

h(k) = lim_{N->\infty}  (1/N) . | { n >0, n<= N : f(n) = k } | .

(Calculations have been given for N=10^6 or so.) There is the more
basic question of whether or not the limit even exists.

There was some question about whether this h(k) is really what we want
to measure. I usually accept this as the only obvious definition of
what it means to "take a random integer n and see what the chance is
that f(n)=k", but as I will show below this point does need to be
raised here.

OK, so I thought I'd drop the anthropocentric base 10 and try the
easier base 3. Note g(n) = 2^{number of 2's in base-3 expansion of n},
so calculating f really amounts to knowing the base-3 expansion of the
powers of 2. I have asked around and have been told that really nothing
is known about this. (Exception: There are an even number of 1's in the
expansion. Proof left as an exercise).

There are two limits to compute (h(1) and h(2)) and they add up to 1.
We can equally well try to compute the expected value of f; this is
E=1*h(1)+2*h(2). From any of the three limits we can get the other two.
I will try to compute E.

Now, just as a guess, we would think that f(n) varies more or less
randomly between 1 and 2 as n marches along, right? In other words, we
look to see E=1.5. I ran through the definition of E (actually I tried
h(1)) for N up through about 10^6 and found that the expected values E
came out to about 1.5, but wandered around, as you would expect of an
apparently random distribution of 1's and 2's on the integers.

If the limit  E  really exists, we can calculate it on a subsequence
such as the set of integers  N = 3^M. Now, a simple counting argument
(where do you put the 2's in the base-3 expansion?) shows that the
fraction computing  E  is then

        (1/3^M) . \Sum _{r=0} ^{r=M}  2^{M-r} \binomial{M,r} f(2^r)

If you take out the values of  f  here, you have a sum which is just an
instance of the binomial theorem, adding up to  3^M.

Well, calculating  f(2^r) is not hard for small values of r. I ran my
PC for a few minutes and got f(2^r) for r up to 150 or so. This allows
me to calculate the sums converging to E taking  N = 3^M = 3^150 --
pretty darn far out. Sure enough, we get  E about equal to 1.5.

HOWEVER...

Plotting the sums versus  M  shows a graph wandering around 1.5 pretty
slowly. For M up to 150 I find about 8 local minima and maxima ranging
from 1.4 to 1.6; the consecutive M coordinates usually differ by 25-30.
So my confidence that these sums are _converging_ to  1.5 is weakened.

Well, what can we prove? Here's something you should notice. In the
binomial sum up above, there are  M+1 terms adding to  3^M.  Most of
them, though, are much smaller than average. This is some sort of
skewed binomial distribution (statisticians probably understand these
real well) but you can show that the coefficients

         (1/3^M) . 2^{M-r} \binomial{M,r}

with  r =  M/3 + t \sqrt M  are about as big as

        (1/\sqrt M) . C . exp( -9/4  t^2)  . (1 + O (1/\sqrt M) )

(Use Stirling's approximation and a lot of paper). That is, you get a
standard bell curve near the top of the graph. In particular, you can
show that the sum of these coefficients with  |t| < t_0 is
Erf((3/2)t_0)+ O(1/\sqrt M). A particular conclusion is

PROPOSITION: About 71% of the total of the sum of the coefficients
results from only  \sqrt M  values of  r  , namely those in
        (M/3 - t \sqrt M ,    M/3 + t \sqrt M).

Now, here's what I had in mind when I said that the method of
determining "random" is important. So far as I can tell the
distribution of the values  f(2^r)  I needed above is "random". I would
not hesitate to guess that the percent of occurences of 1's,

        lim  (1/M) . | {r : f(2^r) = 1 } |

exists and is equal to  0.5. (Heck, I'll guess just about anything not
violently contradicted by data). BUT EVEN SUCH A "RANDOM" DISTRIBUTION
IS NOT ENOUGH to prove that the original expected value  E is 1.5! The
key here is that the number of terms that dominate the binomial sum is
pretty small compared to the number of terms. For example, suppose the
sequence of  f(2^r) eventually started to equal this sequence:

        1 2 2 2 1 1 1 1 1 2 2 2 2 2 2 2 ...

(alternate after 2n-1 terms). In the naive distribution, you see that
_this_ sequence has an expected value of 1.5. But if  I substitute these
1's and 2's into the binomial sum instead of f(2^r), I will conclude
(use the Proposition) that the sums DO NOT converge to 1.5 and that
therefore the expected value E we were seeking at the very start DOES
NOT EXIST!

Another way of saying this is the following. In order for the limit  E
to exist, it is necessary that the sequence f(2^r) be "really random",
which I define to mean: the expected value of the terms in the new
sequence is 1.5  FOR EVERY ONE  of the binomial distributions
(1/3^M)(2^{M-r})\binomial(M,r). These look kinda like lots of bell
curves spread across the real axis, getting flatter as their center
moves right. You've probably seen that picture so I won't draw it here
:)

Here's a similar problem which I hope has no bearing on the problem at
hand. Number theorists have this function \mu(n) = (-1)^{# of distinct
primes dividing n}. It bops around pretty randomly between -1 and +1
(and 0, usually assigned if n is not square-free). The expected value is
zero, if you mean lim (1/N) \Sum \mu (n). But just how close to
randomly distributed is it? As I recall it takes something like the
Riemann Hypothesis to show that \Sum \mu (n) is bounded by O(\sqrt N).
(All this is from dusty memory, so no flames here for inaccuracy, OK?)

So what about those digital products? Well, I'd be delighted to say a
little more if someone can tell me something about the number of 2's in
the ternary expansion of 2^r. Anything. Any easy way to compute them?
Does the base-3 expansion of  r  play any part? (I find the ternary
expansions of 2^(3^s) suggestive for s=0,1,2,maybe 3).  How about this:
can anyone even tell me if there is a last r such that 2^r has no 2's in
it? (Probably the number of 2's in 2^r  is about (1/3)(log2)/(log3) . r
+ little-o ( r), but I can't even guess what kind of big-O term to try
for.)

-- David Rusin <rusin@math.niu.edu>

In article <1991Jun14.211645.30861@mp.cs.niu.edu>, rusin@mp.cs.niu.edu
(David Rusin) writes:

> OK, so I thought I'd drop the anthropocentric base 10 and try the
> easier base 3. Note g(n) = 2^{number of 2's in base-3 expansion of n},
> so calculating f really amounts to knowing the base-3 expansion of
> the powers of 2. I have asked around and have been told that really
> nothing is known about this. (Exception: There are an even number of
> 1's in the expansion. Proof left as an exercise).

Indeed, many questions to do with simultaneous representations of
numbers in two or more bases seem to be intractable. Relevant, here,
for example is a conjecture of Erdos that 2^k in base 3 has at least
one '2' for k>8 (equivalent to 3 | {2^{k+1} \choose 2^k} for such k).
See section B33 of [1] (which I have recently been looking at for other
reasons which may be the subject of another posting soon). This is the
question you ask later

> How about this: can anyone even tell me if there is a last r such
> that 2^r has no 2's in it? (Probably the number of 2's in 2^r  is
> about (1/3)(log2)/(log3) . r  + little-o ( r), but I can't even guess
> what kind of big-O term to try for.)

i.e. which k have g(k) = 1 in your notation. I believe that the problem
is still open: one would be delighted to be able to prove merely that
the number of exceptional k is finite (which it is, of course, on any
hypothesis of "normal", i.e. pseudo-random, behaviour, as you suggest).

If even this form of the "digital product" problem is too difficult,
maybe we should consider the form in which (non-leading) zeros are not
omitted from the product. In this case it is indeed true that "nearly
all" (in your sense) numbers have f(n) = 0, but we can still ask about
which n have f(n) non-zero. In base 2 these are just the numbers 2^k-1.
In base 3, g(n) is either zero or a power of 2, so we need to know
g(2^k) for all k.

Probably for k>15, 2^k in base 3 has at least one non-leading '0' (2^15
is '1122221122'), and so f(2^k) = 0, but it is no more likely that we
can prove this than the Erdos conjecture mentioned before. If we
*could* prove it, then we would be able to characterise the n such that
f(n) is non-zero as "those numbers which (in base 3) have no 0s,
indefinitely many 1s, and at most four 2s" (with f(n) = 1,2,1,1,2
according to whether there are 0,1,2,3,4 2s, respectively: the numbers
with 15 2s collapse at the next stage as g(g(2^15)) = g(2^6) = 0).

Question: can we prove this *without* proving the intractable lemma? It
would be sufficient so show that 2^k (k>15) in base 3 never consists
entirely of many 1s and <=15 2s.

By the way, a related problem concerned with the behaviour of 3^k in
base 2 comes up in the context of Waring's problem, the known solution
for which could be stated more simply if one could prove that (3/2)^k
never has extravagantly small fractional part; or equivalently that 3^k
never has extravagantly large blocks of 0s in its binary expansion.

Reference:
[1] "Unsolved Problems in Number Theory", Richard K. Guy, 1981,
    Springer-Verlag, ISBN 0-387-90593-6

-- Chris Thompson <cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk>