wu :: forums « wu :: forums - Random šExponentiation » Welcome, Guest. Please Login or Register. Jan 24th, 2022, 2:37am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, Eigenray, towr, Grimbal, Icarus, ThudnBlunder, william wu)    Random šExponentiation « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Random šExponentiation  (Read 4289 times)
Barukh
Guest

 Random šExponentiation   « on: Aug 9th, 2003, 4:12am » Quote Modify Remove

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

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)).

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

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

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

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

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

william wu

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

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

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »