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

Home > Numbers
86 at most (Posted on 2012-08-18) Difficulty: 3 of 5
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.)
Solution 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information