From mp.cs.niu.edu!rusin Mon Jun 17 09:11:20 CDT 1991
Article: 5688 of sci.math
Newsgroups: sci.math,rec.puzzles
Path: mp.cs.niu.edu!rusin
From: rusin@mp.cs.niu.edu (David Rusin)
Subject: Re: Digital Product
Message-ID: <1991Jun14.211645.30861@mp.cs.niu.edu>
Organization: Northern Illinois University
References: <1610@acf5.NYU.EDU>
Date: Fri, 14 Jun 1991 21:16:45 GMT
Lines: 143
In article <1610@acf5.NYU.EDU>, ambati@acf5.nyu.edu (FJLevM{n[]Balamurali Ambati) writes:
> Let the "digital product" of a positive integer be evaluated as
> follows: [...]
> If a positive integer is randomly selected,
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,...,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.)
In the meantime, I think I had better get back to work :-(
Dave rusin@math.niu.edu
Article 5712 of sci.math:
Path: mp.cs.niu.edu!linac!uwm.edu!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!cam-cl!news
From: cet1@cl.cam.ac.uk (C.E. Thompson)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Digital Product
Message-ID: <1991Jun15.161924.7192@cl.cam.ac.uk>
Date: 15 Jun 91 16:19:24 GMT
References: <1610@acf5.NYU.EDU> <1991Jun14.211645.30861@mp.cs.niu.edu>
Reply-To: cet1@cl.cam.ac.uk (C.E. Thompson)
Organization: U of Cambridge Comp Lab, UK
Lines: 64
In article <1991Jun14.211645.30861@mp.cs.niu.edu>, rusin@mp.cs.niu.edu
(David Rusin) writes:
--- An amusing and perceptive article on "digital products" ---
> 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
JANET: cet1@uk.ac.cam.phx
Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
Article 5713 of sci.math:
Path: mp.cs.niu.edu!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!kth.se!sunic!mcsun!ukc!cam-cl!news
From: cet1@cl.cam.ac.uk (C.E. Thompson)
Newsgroups: sci.math
Subject: Niggle (was Re: Digital Product)
Keywords: Mobius Riemann Mertens
Message-ID: <1991Jun15.162649.7738@cl.cam.ac.uk>
Date: 15 Jun 91 16:26:49 GMT
References: <1610@acf5.NYU.EDU> <1991Jun14.211645.30861@mp.cs.niu.edu>
Reply-To: cet1@cl.cam.ac.uk (C.E. Thompson)
Organization: U of Cambridge Comp Lab, UK
Lines: 35
In article <1991Jun14.211645.30861@mp.cs.niu.edu>, rusin@mp.cs.niu.edu
(David Rusin) writes:
--- An amusing and perceptive article on "digital products" ---
in the tail of which he writes the following which I feel compelled
to niggle at...
> 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).
!!!!!!!
Invariably.
> 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).
The Riemann Hypothesis will prove O(N^{1/2+\epsilon}) for all positive
\epsilon, but not O(N^{1/2}). The latter is the Mertens Hypothesis
(actually, Mertens conjectured |Sum| <= \sqrt N, i.e. with coefficient
1) which implies the Riemann Hypothesis, but is not known to be implied
by it. (The Mertens Hypothesis implies, for example, that all the
non-trivial zeros of \zeta(s) are not only on the critical line, but
that they are simple.)
> (All this is from dusty memory, so no flames here for inaccuracy, OK?)
Flames? In sci.math? We don't do that sort of thing, do we?
Chris Thompson
JANET: cet1@uk.ac.cam.phx
Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk