86 Conjecture

86 is conjectured to be the largest power of 2 not containing a zero. This simply stated conjecture has proven itself to be proof-resistant. Let us see why.

What is the probability that the nth power of two will not have any zeroes? The first and the last digits are non-zeroes; suppose that other digits become zeroes randomly and independently of each other. This supposition allows us to estimate the probability of 2n not having zeroes as (9/10)k-2, where k is the number of digits of 2n. The number of digits can be estimated as n log102. Thus, the probability is about cxn, where c = (10/9)2 ≈ 1.2 and x = (9/10)log102 ≈ 0.97. The expected number of powers of 2 without zeroes starting from the power N is cxN/(1-x) ≈ 40 ⋅ 0.97N.

Let us look at A007377, the sequence of numbers such that their powers of 2 do not contain zeros: 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 18, 19, 24, 25, 27, 28, 31, 32, 33, 34, 35, 36, 37, 39, 49, 51, 67, 72, 76, 77, 81, 86. Our estimates predicts 32 members of this sequence starting from 6. In fact, the sequence has 30 conjectured members. Similarly, our estimate predicts 2.5 members starting from 86. It is easy to check that the sequence doesn’t contain any more numbers below 200 and our estimate predicts 0.07 members after 200. As we continue checking larger numbers and see that they do not belong to the sequence, the probability that the sequence contains more elements vanishes. With time we check more numbers and become more convinced that the conjecture is true. Currently, it has been checked up to the power 4.6 ⋅ 107. The probability of finding something after that is about 1.764342396 ⋅10-633620.

Let us try to approach the conjecture from another angle. Let us check the last K digits of powers of two. As the number of possibilities is finite, these last digits eventually will start cycling. If we can show that all the elements inside the period contain zeroes, then we need to check the finite number of powers of two until this period starts. If we can find such K, we can prove the conjecture.

Let us look at the last two digits of powers of two. The sequence starts as: 01, 02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04. As we would anticipate, it starts cycling. The cycle length is 20, and 90% of numbers in the cycle don’t have zeroes.

Now let’s continue to the last three digits. The period length is 100, and 19 of them either start with zero or contain zero. The percentage of elements in the cycle that do not contain zero is 81%.

The cycle length for the last n digits is known. It is 4 ⋅ 5n-1. In particular the cycle length grows by 5 every time. The number of zero-free elements in these cycles form a sequence A181610: 4, 18, 81, 364, 1638, 7371, 33170. If we continue with our supposition that the digits are random, and study the new digits that appear when we move from the cycle of the last n digits to the next cycle of the last n+1 digits, we can expect that 9/10 of those digits will be non-zero. Indeed, if we check the ratio of how many numbers do not contain zero in the next cycle compared to the previous cycle, we get: 4.5, 4.5, 4.49383, 4.5, 4.5, 4.50007. All of these numbers are quite close to our estimation of 4.5. If this trend continues the portion of the numbers in the cycle that don’t have zeroes tends to zero; however, the total of such numbers grows exponentially. We can even estimate that the expected growth is 4 ⋅ 4.5n-1. From this estimation, we can derive the conjecture:

Conjecture. For any number N, there exists a power of two such that its last N digits are zero-free.

Indeed, the last N digits of powers of two cycle, and there are an increasing number of members inside that cycle that do not contain zeroes. The corresponding powers of two don’t have zeroes among N rightmost digits.

So, how do we combine the two results? First, the expected probability of finding the power of two larger than 86 that doesn’t contain zero is minuscule. And second, we most certainly can find a power of two that has as many zeroless digits at the end as we want.

To combine the two results, let us look at the sequences A031140 and A031141. We can deduce from them that for the power 103233492954 the first zero from the right occupies the 250th spot. The total number of digits of that power is 31076377936. So 250 is a tiny portion of the digits.

As time goes by we grow more and more convinced that 86 is the largest power of two without zeroes, but it is not at all clear how we can prove the conjecture or whether it can be proven at all.

My son, Sergei, suggested that I claim that I have a proof of this conjecture, but do not have enough space in the margin to fit my proof in. The probability that I will ever be shamed and disproven is lower than the probability of me winning a billion dollars in the lottery. Though then, if I do win the big bucks, I will still care about being shamed and disproven.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

11 Comments

  1. Andrei Zelevinsky:

    Since the fact that humans have 10 fingers doesn’t seem to have any deep mathematical significance, it is not clear why this problem is of any real interest. It would be much more natural to use base 2, making the statement much more elegant! :)

  2. Tanya Khovanova:

    Andrei,

    The fact that the inside digits of the powers of 2 behave randomly in some sense makes it interesting.

  3. JAM:

    @Andrei: Base 2 is a tad boring (as I’m sure you’re aware). But what happens in other bases? Presumably we can make similar conjectures for these. What are the (seemingly) equivalent powers of 2 in bases 3 to 9? What about higher bases? Is there any pattern in (what we think) our maximum power is? Does something similar occur for powers of, e.g. 3?

  4. BB:

    “…but it is not at all clear how we can prove the conjecture or whether it can be proven at all.”

    It cannot be unprovable, since it can be deterministically disproven by presenting a counterexample.
    http://en.wikipedia.org/wiki/Busy_beaver#Applications

  5. Xamuel:

    @BB

    Is it known that there does not exist a pair (n,m) such that the statement “The nth busy beaver number is m” is independent (of PA, or ZFC, or something else)?

  6. BB:

    @Xamuel – great question, this never occured to me. I take back my previous comment. Thanks!

  7. ano:

    “86 is conjectured to be the largest power of 2 not containing a zero.” — But… but 86 is not a power of 2!

    (That was my first reaction on reading the first sentence; took me a while before I understood what was meant. I don’t know what would be better notation/terminology, though.)

  8. Marin Mersenne:

    This is very interesting, I wish you would do more posts about math phenomena.

  9. Tanya Khovanova:

    There is an interesting discussion: http://www.reddit.com/r/math/comments/fwr5m/the_86_conjecture_no_powers_of_two_higher_than/

  10. Noor Khan:

    http://www.wolframalpha.com/input/?i=2^87
    This is saying 2^87 has many zeroes

  11. Barak A. Pearlmutter:

    If you did have a proof, you could demonstrate that fact to us without actually telling us the proof by using a zero-knowledge interactive proof protocol.

Leave a comment


+ six = 8