Musings on mathematics and teaching.

Month: December, 2012

Which powers of 2 do not contain the digit 7?

Which powers of 2 do not contain the digit 7? A quick search reveals the following examples.

2^0 = 1 
2^1 = 2 
2^2 = 4 
2^3 = 8 
2^4 = 16 
2^5 = 32 
2^6 = 64 
2^7 = 128 
2^8 = 256 
2^9 = 512 
2^10 = 1024 
2^11 = 2048 
2^12 = 4096 
2^13 = 8192 
2^14 = 16384 
2^16 = 65536 
2^18 = 262144 
2^19 = 524288 
2^22 = 4194304 
2^23 = 8388608 
2^25 = 33554432 
2^28 = 268435456 
2^33 = 8589934592 
2^41 = 2199023255552 
2^42 = 4398046511104 
2^49 = 562949953421312 
2^50 = 1125899906842624 
2^54 = 18014398509481984 
2^61 = 2305843009213693952 
2^71 = 2361183241434822606848

These exponents are listed in the On-line Encyclopedia of Integer Sequences as A035062.

I have continued the search for exponents up to 1010, and found no other powers of 2 that do not contain the digit 7. If we suppose that the decimal digits of powers of 2 are random, then it is extremely unlikely that other examples exist. Observe that 2n has approximately n\log_{10} 2 decimal digits, so the probability that 2n does not contain the digit 7 is approximately rn where

r = (0.9)^{\log_{10} 2} \approx 0.96878.

Given that no examples exist for 72 \le n \le 10^{10}, we can estimate the probability of an additional example via the infinite sum \sum_{n=10^{10}}^{\infty} r^n = \frac{r^{10^{10}}}{1-r} \approx 5 \times 10^{-137743771}.

This probability is so small that it almost defies comprehension. Imagine that every person in the State of New York picked a random combination for the Powerball lottery, that they all picked the same numbers purely by chance, and they all won the jackpot. Absurd as it is, this event is more probable than finding another power of 2 which does not contain the digit 7, unless there is some hidden pattern in the digits which has escaped our attention.

I wrote a Python program to conduct my search. Since powers of 2 grow very rapidly, it is not efficient to generate all of their digits, so I only kept track of the last 70 digits. If a 7 is not found in the last 70 digits, then the last 400 digits are checked using the three-argument pow function. If a 7 is not found in the last 400 digits, then n is printed, but no further checks are made. Here is my code:

n = 0
N = 1
while 1:
    if not('7' in str(N)) and not('7' in str(pow(2, n, 10**400))):
        print "2^" + str(n)                   
    n += 1
    N = (N * 2) % 10**70

My interest in this question was inspired by a blog post by John D. Cook.

Bayes’ Theorem and the Fake Facebook Lottery Winner

After the recent $587.5 million Powerball jackpot, the following picture was posted to Facebook, where it was shared over 2 million times.

Fake Powerball Ticket

It is not too hard to figure out that the picture is a fake. The most obvious clue is that the numbers are out of order. The numbers on an authentic Powerball ticket are always in ascending order, except for the last number. But I was doubtful for another reason — Bayes’ theorem.

There are two scenarios that must be considered. The first scenario is that Nolan actually did win the jackpot, and he wishes to share his good fortune with a random stranger. The second scenario is that Nolan did not win the lottery, and the picture is a fake. (Other scenarios are theoretically possible, but we will disregard them.)

Let us define some events. Let A be the event that a player selected at random wins the Powerball jackpot, and let B be the event that a player selected at random would make an offer similar to the one shown above. We wish to estimate the conditional probability of A given B. According to Bayes’ theorem, the probability can be computed as follows:

P(A|B) = \displaystyle \frac{P(B|A) P(A)}{P(B|A) P(A) + P(B|\neg A) P(\neg A)}

The probabilities in this formula are difficult to estimate, but let’s make an attempt. We know that there were two winners in the drawing, and I will guesstimate that about 20 million people bought tickets, so P(A) = 1/10,000,000.

The other probabilities are more difficult to predict. It certainly seems unlikely that a lottery winner would offer to give $1 million to a complete stranger. Perhaps it’s even more unlikely that a (randomly selected) non-winner would pretend to win the lottery and offer to share it with a stranger. But it does not seem reasonable to suppose that the first event is 10 million times more likely than the second. So we must conclude that the denominator is dominated by its second term, hence P(A|B) must be close to zero. In other words, the picture is (probably) fake.