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