Author |
Topic: Random šExponentiation (Read 4722 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 2N 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 9th, 2003, 5:17am » |
 Quote  Modify
|
::
1x10m <= 2n < 2x10m
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,
dx10m <= 2n < (d+1)x10m
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 9th, 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 10th, 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 10th, 2003, 2:45am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Guest
|
|
Re: Random Exponentiation
« Reply #3 on: Aug 10th, 2003, 10:43am » |
Quote Modify
 Remove
|
Sir Col: yes, your solution is correct. It uses the following proposition:
on Aug 9th, 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 11th, 2003, 4:49pm » |
Quote Modify
|
nice problem; thanks for sharing it!
All logs in the following write-up are base 10 logs, unless otherwise stated. Sorry the write-up 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 = 2N 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 2N 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 round-trip 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 11th, 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 11th, 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 = BN 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 non-negative 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 1026 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 logB-sized 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 non-analytical 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(k-1) = log10(k) - log10(k-1); 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 12th, 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 12th, 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 12th, 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 12th, 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 12th, 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 alpha1,1. Keep hopping, generating alpha1,i, until If alpha1,i is larger than 2*pi-alpha1,1 (that is, until you are going to pass zero on your next hop). Call this alpha1,k1
Now hop again to generate alpha2,1. Note that alpha2,1 is smaller than alpha1,1. (We will have to consider how much smaller later). Now jump k1+1 more times to generate alpha2,2. Keep jumping, k1+1 at a time, to generate alpha2,i, until alpha2,i > 2*pi-alpha2,1. Call this alpha2,k2.
Now do the same thing to generate the alpha3,is, jumping (k1+1)*k2+1.
Generate an infinite number of these alphaj,i. After showing that the values of alphaj,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 12th, 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 12th, 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 12th, 2003, 6:53pm » |
Quote Modify
|
on Aug 12th, 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 12th, 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 12th, 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 12th, 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 13th, 2003, 1:49pm » |
Quote Modify
|
1) log10 k = pi * p/q for integer k
I think this has to do with transcendental numbers. Rearranging, we get:
(log10 k)*q/p = pi
log10 ( kq/p ) = pi
kq/p = 10pi
I think that kq/p is an algebraic (non-transcendental) number, so 1) has no solution if 10pi is transcendental. However, proving something is transcendental is extremely difficult. In fact, there are only a dozen or so well-defined 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 13th, 2003, 8:59pm » |
Quote Modify
|
The existance of integers k, p, and q such that
[pi] = (p/q)log10 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 15th, 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 15th, 2003, 3:58am » |
Quote Modify
|
read some stuff on mathworld ...
http://mathworld.wolfram.com/AlgebraicNumber.html
http://mathworld.wolfram.com/TranscendentalNumber.html
yes, kq/p is an algebraic integer of degree p, since it's a root for the following polynomial equation, where k,q,p[in][bbz]
xp = kq
as far as proving that 10pi is/isn't transcendental, this might prove useful:
Gelfond-Schneider 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]Gelfond-Schneider 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 16th, 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 15th, 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 Gelfond-Schneider 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 15th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print