All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 86 at most (Posted on 2012-08-18)
286 is conjectured to be the largest power of 2 not containing a zero.
This simply stated conjecture has proven itself to be proof-resistant.

Source: several articles on the web
Do not try to find a counterexample.
Try to explain why it sounds true and why it is so hard to prove.

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 more detailed solution Comment 2 of 2 |

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

 Search: Search body:
Forums (0)