wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Random šExponentiation
        
(Message started by: Barukh on Aug 9^th, 2003, 4:12am)

Title: Random šExponentiation
Post by Barukh on Aug 9^th, 2003, 4:12am

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.

Title: Re: Random šExponentiation
Post by Sir Col on Aug 9^th, 2003, 5:17am

::[hide]
1x10^m <= 2ⁿ < 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ⁿ < (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. ::)
[/hide]::

Title: Re: Random šExponentiation
Post by Sir Col on Aug 10^th, 2003, 2:36am

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, [hide]P(leading digit is 9) = 1–log9[/hide].

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, [hide]P(leading digit is d)=log((d+1)/d)[/hide]. This, of course, holds for d=1,2,...,9.

Title: Re: Random Exponentiation
Post by Barukh on Aug 10^th, 2003, 10:43am

Sir Col: yes, your solution is correct. It uses the following proposition:

on 08/09/03 at 05:17:35, 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? ::)

Title: Re: Random šExponentiation
Post by william wu on Aug 11^th, 2003, 4:49pm

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)
[hide]

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

[/hide]
::

Title: Re: Random šExponentiation
Post by william wu on Aug 11^th, 2003, 6:33pm

Trying to generalize my work analytically and failed ...

:: (highlight to see)
[hide]

===
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 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 10²⁶ 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.
[/hide]
::

Title: Re: Random šExponentiation
Post by william wu on Aug 12^th, 2003, 8:22am

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

Title: Re: Random šExponentiation
Post by william wu on Aug 12^th, 2003, 9:40am

i have a fallacious proof for (1)! :D

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!

Title: Re: Random šExponentiation
Post by James Fingas on Aug 12^th, 2003, 9:45am

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*pi-alpha_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*pi-alpha_2,1. Call this alpha_2,k2.

Now do the same thing to generate the alpha_3,is, 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".

Title: Re: Random šExponentiation
Post by william wu on Aug 12^th, 2003, 9:55am

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.

Title: Re: Random šExponentiation
Post by Icarus on Aug 12^th, 2003, 6:53pm

on 08/12/03 at 08:22:54, 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!

Title: Re: Random šExponentiation
Post by william wu on Aug 12^th, 2003, 7:05pm

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.

Title: Re: Random šExponentiation
Post by Icarus on Aug 12^th, 2003, 7:16pm

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!http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/devil.gif

Title: Re: Random šExponentiation
Post by James Fingas on Aug 13^th, 2003, 1:49pm

1) log₁₀ k = pi * p/q for integer k

I think this has to do with transcendental numbers. Rearranging, we get:

(log₁₀ k)*q/p = pi
log₁₀ ( k^q/p ) = pi
k^q/p = 10^pi

I think that k^q/p is an algebraic (non-transcendental) 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 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.

Title: Re: Random šExponentiation
Post by Icarus on Aug 13^th, 2003, 8:59pm

The existance of integers k, p, and q such that

[pi] = (p/q)log₁₀ 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.

Title: Re: Random šExponentiation
Post by william wu on Aug 15^th, 2003, 3:58am

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:

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

Title: Re: Random šExponentiation
Post by Icarus on Aug 15^th, 2003, 5:35pm

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