2^86 is the 26-digit number 77371252455336267181195264.
The probability that 26 random digits would contain no zeros is (9/10)^26 or about 1/15.5. There might be a quibble about the first and last digits' not being random, as they can't be zero, but (9/10)^24 is still about 1/12.5. These are not insurmountable odds, and in fact 2^86 did make it through without a zero.
But as the numbers get larger, the probability decreases:
number of digits reciprocal of probability that
n n - 2 random digits lack a zero
(10/9)^(n-2)
26 12.53660012188684
27 13.92955569098537
28 15.47728410109486
29 17.19698233454984
30 19.10775814949982
31 21.23084238833314
32 23.5898248759257
33 26.21091652880635
34 29.1232405875626
35 32.35915620840289
The number of digits in powers of two is the ceiling of the common log of 2 to the power:
power digits
86 26
87 27
88 27
89 27
90 28
91 28
92 28
93 28
94 29
95 29
On its face, the next few powers of 2 could reasonably be expected to turn up one without zeros, though less than 50% likely as the next nine powers each have only a 1/14 to 1/17 chance of delivering.
In fact, the program below finds that all the powers of 2 beyond 2^86, through 2^3500, have at least one zero:
2^3500 has 1054 digits, and this program
10 P=1
20 for Ex=1 to 3500
40 P=P*2
70 Good=1:S=cutspc(str(P))
80 Ix=instr(S,"0")
90 if Ix=0 or Ex=3500 then print Ex,P
100 next Ex
finds that 2^86 is the last power of 2 lacking a zero up through 2^3500:
n 2^n
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
13 8192
14 16384
15 32768
16 65536
18 262144
19 524288
24 16777216
25 33554432
27 134217728
28 268435456
31 2147483648
32 4294967296
33 8589934592
34 17179869184
35 34359738368
36 68719476736
37 137438953472
39 549755813888
49 562949953421312
51 2251799813685248
67 147573952589676412928
72 4722366482869645213696
76 75557863725914323419136
77 151115727451828646838272
81 2417851639229258349412352
86 77371252455336267181195264
are the only ones found.
Now, what's the probability that a given n-digit number will lack a zero?
(9/10)^n
(Here, with such large numbers, we're treating that -2 in n-2 as not very significant, especially as we'll be adding probibilities, thereby overestimating them anyway, as explained below.)
But we wish to know the probability that all powers of 2 past 3500 have zeros, that is, we find none that lack a zero, so we're also seeking the probability that any does lack a zero.
That probability is certainly smaller than the sum of the individual probabilities for the individual powers, as that summing will multiply include multiple occurrences even though only the first found will decide that any (i.e., at least one) exist: P(A or B or C ...) < P(A) + P(B) + P(C) + ... .
So what is that sum of probabilities in our instance?
On average there will be about 3.1 * n powers of 2 of length n, so we seek Sigma{n=3501 to inf}3.1*(9/10)^n. That's about
3.1 * 9^3501 / 10^3500 ~= 1.97 * 10^-159 or 1/(5*10^158)
by considering the sum of the infinite geometric series.
I'm sure that the consideration of higher powers of 2 than just 2^3500 has taken place and so this tail probability of finding at least one zero-free number is even lower than what I could verify using UBASIC.
But looking back: what was the probability that seeking between 87 and 3500 inclusive we'd find or fail to find a 2^n that lacked a zero?
(9/10)^(k-2) that any one value, k = length(2^i), lacked a zero.
1 - (9/10)^(k-2) that any particular value, 2^k, had a zero.
Prod{i=87 to 3500}(1 - (9/10)^(k(i)-2)) that all have at least one zero; here showing k as a function of i.
The length of 2^i (i.e., k(i)) can be given by k(i)=ceil(i*log(2)).
That probability, that all the powers of two from 87 through 3500 would all have at least one zero, comes out to about 14% (0.14186...). That's small but attainable and in fact found to be the case. As show above, once it's past this, the odds of finding another lacking a zero are negligible.
|
|
Posted by Charlie
on 2012-08-18 15:07:44 |
more detailed solution
