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:
        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

Tagged with: ,
Posted in Math, Python
8 comments on “Digits in powers of 2
  1. Yves Langlois says:

    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. lvps1000vm says:

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

    def digits(n):
        s = set()
        while n > 0:
            n /= 10
            if len(s) == 10:
        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. lvps1000vm says:

    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. TomF says:

    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. John says:

    lvps1000vm: Thanks for the code.

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

  6. robru says:

    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. David Feuer says:

    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. Dave Radcliffe says:

    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.

2 Pings/Trackbacks for "Digits in powers of 2"
  1. [...] Digits in powers of 2 per Bit3Lux ::: The Endeavour [...]

  2. [...] interest in this question was inspired by a blog post by John D. Cook. Share this:PrintEmailMoreStumbleUponGoogle [...]