Author 
Topic: Random šExponentiation (Read 3620 times) 

Barukh
Guest

Maybe some people will find the following problem interesting: Let N be a random natural number. 1. What is the probablity that number 2^{N} has a leading digit 1? 2. Generalize for any leading digit M. 3. Generalize for any natural exponent base B. All the numbers are written in base 10.


IP Logged 



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Random šExponentiation
« Reply #1 on: Aug 9^{th}, 2003, 5:17am » 
Quote Modify

:: 1x10^{m} <= 2^{n} < 2x10^{m} m <= nlog2 < log2+m As log2<1, nlog2 will be m point something. So it is only the fractional part of nlog2 that is significant. That is, 0 <= frac(nlog2) < log2 We know that in general 0 <= frac(klog2) < 1 and frac(klog2) is uniformly distributed. Hence, P(leading digit is 1) = log2 Generalisation will follow from, dx10^{m} <= 2^{n} < (d+1)x10^{m} log(d)+m <= nlog2 < log(d+1)+m Similarly, log(d) < log(d+1) < log(d)+1, so, again, only the fractional part is important: frac(log(d)) <= frac(nlog2) < frac(log(d+1)). Leading to, P(leading digit is d) = frac(log(d+1))–frac(log(d)) = frac(log((d+1)/d))). I'll let someone else do base B. ::

« Last Edit: Aug 9^{th}, 2003, 5:22am by Sir Col » 
IP Logged 
mathschallenge.net / projecteuler.net



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Random šExponentiation
« Reply #2 on: Aug 10^{th}, 2003, 2:36am » 
Quote Modify

Actually, I've just thought of a problem with the general result. It lies with the conclusion that follows... Quote:log(d)+m <= nlog2 < log(d+1)+m 
 What happens when d=9? Unfortunately the inequality, frac(log(d)) <= frac(nlog2) < frac(log(d+1)), becomes log9 <= frac(nlog2) < 0, as the fractional part of log10 is 0. As this is a special case, we could refine the result by saying that it holds for d=1,2,...,8, and for d=9, P(leading digit is 9) = 1–log9. In fact, because log(d) and log(d+1), for d=1,2,...,8, are both less than one, we could simplify the whole thing by dropping the frac() function, and say that, P(leading digit is d)=log((d+1)/d). This, of course, holds for d=1,2,...,9.

« Last Edit: Aug 10^{th}, 2003, 2:45am by Sir Col » 
IP Logged 
mathschallenge.net / projecteuler.net



Barukh
Guest


Re: Random Exponentiation
« Reply #3 on: Aug 10^{th}, 2003, 10:43am » 
Quote Modify
Remove

Sir Col: yes, your solution is correct. It uses the following proposition: on Aug 9^{th}, 2003, 5:17am, Sir Col wrote::: ... and frac(klog2) is uniformly distributed. 
 Can you prove the statements, or at least some of them, without using this advanced result?


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #4 on: Aug 11^{th}, 2003, 4:49pm » 
Quote Modify

nice problem; thanks for sharing it! All logs in the following writeup are base 10 logs, unless otherwise stated. Sorry the writeup is a little verbose but I try to make it as accessible as possible. :: (highlight below to see my solution) ==== First agree that the number K = 2^{N} will have a leading digit of 1 if the following condition is satisfied: 0 <= (log K) mod 1 < log 2 Justification: Write K in scientific notation. For example, if K = 2^20 = 1048576, then K = 1.048576 x 10^6. We will generalize the scientific notation for K as: K = a.b1b2b3b4 x 10^m where m is a positive integer. Now take the base 10 logarithm of both sides: log K = log(a.b1b2b3b4 x 10^m) = log(a.b1b2b3b4) + log(10^m) = log(a.b1b2b3b4) + m Now take both sides modulo 1. Note that taking a real number modulo 1 leaves only the part of the number after the decimal place. (So 3.4 mod 1 = 0.4) log K mod 1 = [log(a.b1b2b3b4) + m] mod 1 = log(a.b1b2b3b4) mod 1 We want to establish a target range for this last expression if a = 1, since the b1 b2 b3 ... digits can be anything. So the number a.b1b2b3b4 can vary between 1.00000 and 1.99999 < 2. Thus the range is [0,log2), since log(1) mod 1 = 0 mod 1 = 0, and log(2) mod 1 = log 2. ==== Now looking at our expression f(N) = log K mod 1 = log 2^{N} mod 1 = N*log2 mod 1, consider what happens as we keep incrementing N starting from N = 1. Realize that f(N) must always be in the range [0,1), due to the mod 1. So we can think of f(N) repeatedly wrapping around the [0,1) unit circle. Each time we wrap, we must hit the target range [0,log2) exactly once, because f(N) = N*log2 mod 1 and thus every time we increment N, we hop around the unit circle by a distance of log2. We cannot miss the target range on a roundtrip since our hop has the same length as the range. The probability that K has a leading digit of 1 is then equivalent to the ratio of target range hits to hops in a round trip. The distance in a round trip is 1. We hop by log2. Thus it takes 1/log2 hops to make a round trip. Of those hops, we established that only one of them will hit the target range. Thus the ratio is 1/(1/log2) = log2. Note: We should specify our probability measure for this problem, since it's weird to talk about a random natural number ... the probability of choosing any natural number in a uniform distribution is 0, since the naturals are infinite. But intuitively we're talking about some ratio that tends to infinity. Let E be the event that our randomly chosen natural number starts with a 1. Our measure m(E) is m(E) = lim(k>oo) E n {1, ... ,k}/k where n is intersection and   is cardinality. Note that this measure is a bit pathological because it's only finitely additive, not countably additive. For instance, let x be a natural number. Then m({x}) = 0. However, if we pass the set of all natural numbers N, then m(N) = 1. Yet 1 != m({1}) + m({2}) + ... = 0 + 0 + ... Thanks to [psilo] over IRC for his help and time with this problem. ::

« Last Edit: Aug 11^{th}, 2003, 4:57pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #5 on: Aug 11^{th}, 2003, 6:33pm » 
Quote Modify

Trying to generalize my work analytically and failed ... :: (highlight to see) === What if our base is B, and we want the probability that the first digit of K = B^{N} is X? Applying the target range argument shown above, if a = X, then a.b1b2b3b4 will range between X.00000 and X.9999. Thus the target range for log K mod 1 becomes [logX,log(X+1)). Note that this target range must always lie between 0 and 1, since X < 10, and thus log X < 1 because we are taking base 10 logs. Also, note that the argument still holds if B is a number greater than 9, because scientific notation will always reduce B^N to [ a nonnegative number < 10 ] x [ some power of 10 ]. For example, if K = 20^20, then K = (2 x 10)^20 = 2^20 10^20 = (1.048576 x 10^6) x 10^20 = 1.048576 x 10^26 and when we compute log K mod 1, the 10^{26} term disappears anyways. Now let's look at hopping. log K mod 1 = NlogB mod 1. Starting from 0, we go around the unit circle in logBsized hops, desiring to hit the range [logX,log(X+1)). Now I'm a bit stuck! In the case B=2 X=1, it was easy to determine # of hits in a round trip, because the hopsize fit the target range length so nicely. However, now you might hit the target range every trip, or every other trip, or maybe every three trips. New puzzle: Imagine a circle with radius r centered at the origin. A continguous arc of the circle is colored green, from (r,a) to (r,b) in polar coordinates (so a and b are angles). Starting from (r,0), you hop counterclockwise around the circle in arc lengths of size B. What is the fraction of times you hit the green section, as the number of hops tends to infinity? Not sure if there's a clean way to solve this analytically. A nonanalytical way to resolve this for a given (B,X) pair might the following: Take a rational approximation A/B of the hopsize. and tallying how many times I hit the target range in B jumps. Then I see how close that count is to A. The difference is some measure of error. Something like that, haven't thought much about it. I printed out the possible hopsizes and target range lengths: HOPSIZES >> log10(2:9) ans = 0.3010 0.4771 0.6021 0.6990 0.7782 0.8451 0.9031 0.9542 TARGET RANGE LENGTHS >> for k=2:10, d(k1) = log10(k)  log10(k1); end >> d d = 0.3010 0.1761 0.1249 0.0969 0.0792 0.0669 0.0580 0.0512 0.0458 This shows that the hopsize tends to be larger than the target range by a factor of roughly 1 to 20. I believe this strikes out the possibility of simply approximating the answer by the target range length, because we may miss the target range often. However if hopsize was much less than target range length, such an approximation would be alright. ::


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #6 on: Aug 12^{th}, 2003, 8:22am » 
Quote Modify

Got a new plan for attacking the issues left unresolved in previous post. All of the following points must be proven: 1. log k is not equal to pi times a rational number, where k is some positive integer > 1. 2. if the hopsize is an irrational multiple of pi, then the sequence of points generated by hopping around the circle is dense. 3. the density of these points implies an asymptotically uniform distribution of points around the circle. 4. thus the probability is given by (target range length)/(circumference of circle) = (target range length), since the circumference of our circle is 1. 1. at first seemed like a stupid question to ask, but now it seems far from obvious. Maybe has something to do with how pi is transcendental? Icarus better know 2. is what inspired this train of thought. I showed the "New Puzzle" problem from the previous post to a friend and he was reminded of an academic exercise where he had to prove 2., but no longer remembers how. I'm not sure how either. 3. and 4. should be argued with formal arithmetic. disclaimer: i don't know what i'm talking about

« Last Edit: Aug 12^{th}, 2003, 7:22pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #7 on: Aug 12^{th}, 2003, 9:40am » 
Quote Modify

i have a fallacious proof for (1)! Fallacious proof that log10(k) cannot be a product of pi and a rational number, where k is an integer that is greater than 1 and not a power of 10: Proof by contradiction: Suppose log10(k) = (p/q)*pi, where (p/q) is a rational. Raise both sides to base 10. Then k = 10^(p/q * pi). p/q * pi is irrational, since rational * irrational = irrational. And 10^(irrational) = irrational. But k is rational. Since rational != irrational, we have a contradiction. b00m!

« Last Edit: Aug 12^{th}, 2003, 5:43pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Random šExponentiation
« Reply #8 on: Aug 12^{th}, 2003, 9:45am » 
Quote Modify

I have also proved 2. It was a fairly simple proof which derived from the consideration of a special set of points you could get hopping around the circle, with hopping distances that are natural numbers. Start, without loss of generality, at angle zero. Then hop once. You will end up at a new location alpha_{1,1}. Keep hopping, generating alpha_{1,i}, until If alpha_{1,i} is larger than 2*pialpha_{1,1} (that is, until you are going to pass zero on your next hop). Call this alpha_{1,k1} Now hop again to generate alpha_{2,1}. Note that alpha_{2,1} is smaller than alpha_{1,1}. (We will have to consider how much smaller later). Now jump k1+1 more times to generate alpha_{2,2}. Keep jumping, k1+1 at a time, to generate alpha_{2,i}, until alpha_{2,i} > 2*pialpha_{2,1}. Call this alpha_{2,k2}. Now do the same thing to generate the alpha_{3,i}s, jumping (k1+1)*k2+1. Generate an infinite number of these alpha_{j,i}. After showing that the values of alpha_{j,1} go to zero, you can see that for any point on the circle, there are an infinite number of points with integer angles in its neighbourhood. I assume this is what you mean by "dense".


IP Logged 
Doc, I'm addicted to advice! What should I do?



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #9 on: Aug 12^{th}, 2003, 9:55am » 
Quote Modify

Can I get problem (1) named after me? Wutang's Conjecture: Log10 k != rationalNumber * pi, where k is an integer > 1 and not a power of 10 Note: I just realized this question isn't relevant to the random exponentiation problem, because in that problem our circle has length 1, not some length in terms of pi. And log10 k is not a rational multiple of 1. Nevertheless I think this new problem is interesting too.

« Last Edit: Aug 12^{th}, 2003, 6:06pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Random šExponentiation
« Reply #10 on: Aug 12^{th}, 2003, 6:53pm » 
Quote Modify

on Aug 12^{th}, 2003, 8:22am, william wu wrote:Maybe has something to do with how pi is transcendental? Icarus better know 
 Sorry, but Icarus don't know! James, towr, and wowbagger (and Pietro, if he's still around) probably know more. I've never studied much in transcendentality. I've seen proofs of the transcendental nature of e and pi, but all that I can recall is that they involved truncations of the series expansions. PS. What's with the demotions? James, towr, and I now have the esteemed rank of uberpuzzler to ourselves!

« Last Edit: Aug 12^{th}, 2003, 6:55pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #11 on: Aug 12^{th}, 2003, 7:05pm » 
Quote Modify

I just figured the threshholds were too low for the long run. Too many uberpuzzlers walking around I'm looking into a YaBB mod which will allow for more possible ranks.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Random šExponentiation
« Reply #12 on: Aug 12^{th}, 2003, 7:16pm » 
Quote Modify

So! My strategy of talking every subject to death and continuing annoying arguments (not to mention pointless posts such as this one) has finally paid off!


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Random šExponentiation
« Reply #13 on: Aug 13^{th}, 2003, 1:49pm » 
Quote Modify

1) log_{10} k = pi * p/q for integer k I think this has to do with transcendental numbers. Rearranging, we get: (log_{10} k)*q/p = pi log_{10} ( k^{q/p} ) = pi k^{q/p} = 10^{pi} I think that k^{q/p} is an algebraic (nontranscendental) number, so 1) has no solution if 10^{pi} is transcendental. However, proving something is transcendental is extremely difficult. In fact, there are only a dozen or so welldefined numbers that are proven to be transcendental. There are a few classes of numbers that are known or thought to be transcendental as well. Look on the Wolfram math site ... it's all there somewhere. But my knowledge of transcendental numbers is very limited. I could be wrong on many things here.


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Random šExponentiation
« Reply #14 on: Aug 13^{th}, 2003, 8:59pm » 
Quote Modify

The existance of integers k, p, and q such that [pi] = (p/q)log_{10} k would be a discovery to astonish the entire mathematics community. But even so I do not know how to prove they don't exist.

« Last Edit: Aug 15^{th}, 2003, 5:42pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Random šExponentiation
« Reply #15 on: Aug 15^{th}, 2003, 3:58am » 
Quote Modify

read some stuff on mathworld ... http://mathworld.wolfram.com/AlgebraicNumber.html http://mathworld.wolfram.com/TranscendentalNumber.html yes, k^{q/p} is an algebraic integer of degree p, since it's a root for the following polynomial equation, where k,q,p[in][bbz] x^{p} = k^{q} as far as proving that 10^{pi} is/isn't transcendental, this might prove useful: GelfondSchneider Theorem: If [alpha] and [beta] are algebraic numbers with [alpha][ne]0, [alpha][ne]1, and [beta][notin][bbq], then [alpha][smiley=supbeta.gif] is transcendental. see http://www.math.sc.edu/~filaseta/gradcourses/Math785/Math785Notes8.pdf for more on this theorem Code: // h0h0 no png generation here! :) [center][color=orange][b]GelfondSchneider Theorem[/b]: If [alpha] and [beta] are algebraic numbers with [alpha][ne]0, [alpha][ne]1, and [beta][notin][bbq], then [alpha][smiley=supbeta.gif] is transcendental.[/color][/center] 
 (Icarus: thanks; i removed the subscripts from your previous post now that the images have been trimmed )

« Last Edit: Aug 16^{th}, 2003, 3:06am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Random šExponentiation
« Reply #16 on: Aug 15^{th}, 2003, 5:35pm » 
Quote Modify

Thanks! That's even better! I've been looking at this, but as yet I don't see how to use the GelfondSchneider theorem to show that 10^{[pi]} is transcendental. Since [pi] is transcendental, it does not apply directly of course. Tricks like that used to show that e^{[pi]} is transcendental: e^{[pi]} = (1)^{i}, don't seem to work either, since we still have a transcendental ln10 in the exponent. But we don't really need to show that 10^{[pi]} is transcendental. Wutang's conjecture [langle] [wutang] [rangle] follows if we can show that n^{[pi]} is not an integer for all integers n > 1 (actually we only need to show it for powers of 10, but in this case the general condition might be easier). (By the way  that is the oddest looking "orange" I've ever seen. )

« Last Edit: Aug 15^{th}, 2003, 5:51pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



