Digits in powers of 2

Does the base 10 expansion of 2^n always contain the digit 7 if n is large enough?

As of 1994, this was an open question (page 196 here). I don’t know whether this has since been resolved.

The following Python code suggests that the conjecture may be true for n ≥ 72.

def digits(n):
    s = set()
    while n > 0:
        s.add(n%10)
        n /= 10
    return s

for i in range(71, 10000):
    p = 2**i
    if 7 not in digits(p):
        print i, p

Update: It appears that 2^n contains every digit for n > 168. See this comment.

Related post: Open question turned into exercise

8 thoughts on “Digits in powers of 2

  1. Why specifically the conjecture is about only 7?

    5 doesn’t seem to be there either.
    9 is not present for i=108 but always after until 10000.

  2. In fact, 168 looks like the greatest number to miss any digit

    def digits(n):
        s = set()
        while n > 0:
            s.add(n%10)
            n /= 10
            if len(s) == 10:
                break
        return s
    
    for i in range(100, 100000):
        p = 2**i
        if len(digits(p)) < 10:
            print i, len(digits(p))
        if i % 10000 == 0:
            print "checked",i
    

    I conjecture: maybe 7 is interesting because the rest are all proven.

  3. Oh, the previous comment lost the identation. I was just checking that all digits are present and not just 7. After 168 doesn’t appear to return more results.

  4. Implementation detail: this really only needs four lines:
    for i in xrange(71, 10000):
    p = 2**i
    if ‘7’ not in str(p):
    print i, p

    If you really need the SET of digits in x: set(str(x)).

  5. lvps1000vm: Thanks for the code.

    I edited your comment to change your “code” tag to a “pre” tag and that restored your indentation.

  6. TomF: You beat me to it. Not only is str() simpler than digits(), it is significantly faster, too. Here are some benchmarks:


    $ time python digits.py
    71 2361183241434822606848

    real 0m48.748s
    user 0m48.712s
    sys 0m0.000s

    $ time python str.py
    71 2361183241434822606848

    real 0m0.575s
    user 0m0.564s
    sys 0m0.008s

  7. I think you can get much faster code by giving up on using built-in (binary) numbers altogether. Just do all the arithmetic in (binary coded) decimal. Instead of calculating 2**n each time, store an array of, say, 40000 digits, and double it on each iteration, scanning for sevens as you do. I believe this should be much faster than doing an expensive binary-to-decimal conversion each time.

    Note: there are all sorts of tricks I don’t know to make BCD arithmetic faster, if you need.

  8. I suggest that you keep only the last 60 digits or so, by setting N = (N*2) % (10**60) after each iteration. If there is no 7 in the last 60 digits, then check the last 200 digits by using pow(2, n, 10**200). If that also fails then try the last 400 digits, etc. Only compute the entire decimal expansion as a last resort. You can check exponents into the billions with this approach.

Comments are closed.