Does there exist another power of 2, except 65536, that doesn't contain a power of two digit?

[axn]

Originally Posted by LaurV

Almost
I didn't "follow" with a rigorous proof, it was a sketch only. Tested to 2^1G, as said.

Therefore I can't say "for sure". But is should be "easy" to follow with the modularity to see where all candidates "disappear" all. I don't think you need more than 12-15 digits. But a better way should be possible for a formal proof (which I don't know). I may do this later if nobody has a better idea.

This approach is not going to work.

If we consider n lower order digits, they cycle with a periodicity 5^(n-1). So you need to find an n such that all 5^(n-1) residues turn up bad -- then that will constitute a rigorous proof. If we assume the digits of a residue (except the final 6) are randomly distributed, the probability of a given residue being good is (6/10)^(n-1). There are 5^(n-1) such residues. So on average, you expect (6/10)^(n-1) * 5^(n-1) = 3^(n-1) good residues. This is diverging.

This approach is not going to work.

[LaurV]

Originally Posted by axn

This approach is not going to work.
...

This approach is not going to work.

Yep, we figured out as much
...
Yep, we figured out as much

[Dylan14]

This looked like an interesting problem to code up in Python. Here is one code snippet that does the search brute force, like the OP did:

#Challenge - find a power of 2 such that it does not have a power of 2 digit in its decimal expansion.
#we have a hint: the number is a power of 16, so we need to consider numbers of the form 2^4m
#but not m = 0, since 4m = 0, and 2^0 = 1, which implies 1 is a power of two.
#so we can start the search from m = 1
#a known solution is 65536 = 2^16, are there any more?

m = 1
while m<=100000:
    p = 4*m
    num = pow(2,p)
    decimalexpansion = str(num)
    length = len(decimalexpansion)   #number of digits in the decimal expansion of 2^4m
    goodchar = 0   #number of digits that aren't 1,2,4 or 8
    for char in decimalexpansion:
        if char == "1" or char == "2" or char == "4" or char == "8":
            #we have found a power of 2 in the expansion, so this m is no good
            #increment m and reset goodchar.
            m += 1
            goodchar = 0
            break
        else:
            #increment goodchar
            goodchar += 1
            #did we reach the end of the number without finding a 1, 2, 4 or 8?
            if goodchar == length:
                #print the p and m value, increment m, reset goodchar, and break out of the for loop
                print(p, ", ", m)
                m += 1
                goodchar = 0
                break
            else:
                #keep going in the loop
                continue

The method of looking at the last d digits is interesting, but as already mentioned, we can find (perhaps via brute force) a number n such that 2^n has the last d+1 digits not containing a 1, 2, 4 or 8.

[axn]

Originally Posted by Dylan14

The method of looking at the last d digits is interesting, but as already mentioned, we can find (perhaps via brute force) a number n such that 2^n has the last d+1 digits not containing a 1, 2, 4 or 8.

No need to brute force. R.Gerbicz already showed big numbers, but basically, using the periodicity of residues, we can iteratively improve a record.

For example:

Mod(16,10^52)^449745173682458698749542266945460 = 2907070905095635370900390399505557009995060033355776 (51 digits)

where 449745173682458698749542266945460 = 30617335 + 5^36*3 + 5^42*3 + 5^44*4 + 5^46*3

[R. Gerbicz]

Originally Posted by LaurV

That's the opposite problem. This would just be eliminated, it is of no interest for us. Find one which has no 1, 2, 4, 8, please

Congrats, and you could easily generalize it: this time using only 6 and 9 in the last 50 places

? Mod(2,10^50)^5342684466535587793434484498741672
%26 = Mod(96996666999996996999999996669699999969969696669696, 100000000000000000000000000000000000000000000000000)

[Viliam Furik]

Originally Posted by Dylan14

This looked like an interesting problem to code up in Python

I did code it in Python, too:

f = open("strp.txt", "a")


def check(strp):
    for a in strp:
        if a == "1" or a == "2" or a == "4" or a == "8":
            return 1
    return 0


def nonpower2(a, b):
    p = 16 ** a
    strp = str(p)
    if check(strp) == 0:
        print(strp)
        f.write("\n")
        f.write(strp)
        f.write("\n")
    for x in range(a, b):
        p *= 16
        strp = str(p)
        if check(strp) == 0:
            print(strp)
            f.write("\n")
            f.write(strp)
            f.write("\n")

Just in case it finds good number, it writes it into a file.

[Dr Sardonicus]

Although periodicity goes out the window, and again it can never lead to a proof, Benford's Law tells us that the proportion of n for which the block of k leading digits is lacking a given nonempty proper subset of the decimal digits, tends to 0 as k increases without bound. For each k > 1, however, there will be a positive proportion of n's whose leading block of k digits lacks the digits in the given subset. (I say k > 1 to allow for the exceptional case that the leading digit is never 0.)

For k = 1, the proportion of n for which 2^n has a leading digit of 1, 2, 4 or 8 is

log(2/1)/log(10) + log(3/2)/log(10)+log(5/4)/log(10)+log(9/8)/log(10) or 0.62518, approximately, and

2^n has a leading digit of 3, 5, 6, 7, or 9 for the other log(4/3)/log(10) + log(6/5)/log(10) + log(7/6) + log(8/7)/log(10) + log(10/9)/log(10) = .37482 approximately of n's.

[CRGreathouse]

Originally Posted by Dr Sardonicus

Although periodicity goes out the window, and again it can never lead to a proof, Benford's Law tells us that the proportion of n for which the block of k leading digits is lacking a given nonempty proper subset of the decimal digits, tends to 0 as k increases without bound. For each k > 1, however, there will be a positive proportion of n's whose leading block of k digits lacks the digits in the given subset. (I say k > 1 to allow for the exceptional case that the leading digit is never 0.)

For k = 1, the proportion of n for which 2^n has a leading digit of 1, 2, 4 or 8 is

log(2/1)/log(10) + log(3/2)/log(10)+log(5/4)/log(10)+log(9/8)/log(10) or 0.62518, approximately, and

2^n has a leading digit of 3, 5, 6, 7, or 9 for the other log(4/3)/log(10) + log(6/5)/log(10) + log(7/6) + log(8/7)/log(10) + log(10/9)/log(10) = .37482 approximately of n's.

Right, and you can extend this to higher powers of 10 and find 22.3%, 13.4%, 8.0%, 4.8%, 2.9%, 1.7%, and 1.0% with the first 2, 3, ..., 8 digits not powers of 2.

[code]ok(n)=#setintersect(Set(digits(n)),[1,2,4,8])==0
do(N)=sum(n=3*10^(N-1),10^N-1,if(ok(n), log(1+1/n)/log(10)))

[Dr Sardonicus]

Originally Posted by CRGreathouse

Right, and you can extend this to higher powers of 10 and find 22.3%, 13.4%, 8.0%, 4.8%, 2.9%, 1.7%, and 1.0% with the first 2, 3, ..., 8 digits not powers of 2.

[code]ok(n)=#setintersect(Set(digits(n)),[1,2,4,8])==0
do(N)=sum(n=3*10^(N-1),10^N-1,if(ok(n), log(1+1/n)/log(10)))

The number of terms in the sum for N-digit "ok" numbers in the problem at hand is 5*6^N-1, proving the sum is positive for every N. The smallest possible n is (as you indicate) 3*10^N-1.

Since for x > 0 we have log(1+x) < x, the sum S is less than (number of terms)(largest term), S < 5*6^N-1/(3*10^N-1) = (3/5)^N-2. Even this ludicrously conservative upper bound tends to 0 as N increases without bound.

If 0 < x < 1 we have log(1 + x) > x/2, which gives the lower bound (5*6^N-1)(1/2)10^-N or S > (1/4)(3/5)^N-1.

[CRGreathouse]

Originally Posted by Dr Sardonicus

The number of terms in the sum for N-digit "ok" numbers in the problem at hand is 5*6^N-1, proving the sum is positive for every N.

Oh right, of course.