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
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.
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",iI conjecture: maybe 7 is interesting because the rest are all proven.
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.
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)).
lvps1000vm: Thanks for the code.
I edited your comment to change your “code” tag to a “pre” tag and that restored your indentation.
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
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.
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.