Is 128 the only multi-digit power of 2 such that each of its digits is also a power of 2?
The number $128$ can be written as $2^n$ with integer $n$, and so can its every individual digit. Is this the only number with this property, apart from the one-digit numbers $1$, $2$, $4$ and $8$?
I have checked a lot, but I don't know how to prove or disprove it.
Solution 1:
This seems to be an open question. See OEIS sequence A130693 and references there.
Solution 2:
Here's some empirical evidence (not a proof!).
Here are the first powers which increase the length of 1-2-4-8 runs in the least significant digits (last digits):
Power 0: 1 digits. ...0:1 Power 7: 3 digits. ...0:128 Power 18: 4 digits. ...6:2144 Power 19: 5 digits. ...5:24288 Power 90: 6 digits. ...9:124224 Power 91: 7 digits. ...9:8248448 Power 271: 8 digits. ...0:41422848 Power 1751: 9 digits. ...3:242421248 Power 18807: 10 digits. ...9:8228144128 Power 56589: 14 digits. ...3:21142244442112 Power 899791: 16 digits. ...9:8112118821224448 Power 2814790: 17 digits. ...6:42441488812212224 Power 7635171: 19 digits. ...5:2288212218148814848 Power 39727671: 20 digits. ...6:48844421142411214848 Power 99530619: 21 digits. ...6:142118882828812812288 Power 233093807: 25 digits: ...0:2821144412811214484144128 Power 22587288091 : 26 digits: ...9:81282288882824141181288448
Easy to see, this run length grows veeeery slow: $25$ digits of $233093807*log_{10}2 \approx 70168227$ decimal digits are powers of 2. Hardly 25 can reach 70168227.
Let's look at it deeper. Consider $2^k$ having $n$ decimal digits (obviously $n \le k$). Let's say $2^k \mod 5^n = a$. Then by CRT we can recover $2^k \mod 10^n$ (note that $2^k \equiv 0 \pmod {2^n}$):
$$f(a) \equiv 2^k \equiv a \cdot 2^n \cdot (2^{-n})_{\mod 5^n} \pmod{10^n}$$
Now let's assume that $2^k$ randomly goes over $\mod 5^n$. How many there are elements $x \in (0,\dots,5^n-1)$ such that $f(x) \mod 10^n$ consists from digits 1-2-4-8? There are at most $4^n$ such values (all possible combinations of 1-2-4-8 $n$ times), from $5^n$ (remark - we should consider only coprime with 5 numbers, there are $5^{n-1}*4$ such). So if $2^k$ acts randomly, then the probability of getting 1-2-4-8 value is limited by $(4/5)^{n-1}$, which decreases exponentially with $n$ (and $k$).
Now how much powers of 2 do we have for each $n$? Constant amount, 3 or 4! So, if for some small $n$ there are no such values, then very probably for all numbers it's also true.
Remark: this may look mouthful, nearly same explanation could be given modulo $10^n$. But in my opinion it's easier to believe that $2^k$ randomly goes over $\mod 5^n$ than $\mod 10^n$. EDIT: Also, $2$ is a primitive root modulo $5^n$ for any $n$, so it indeed goes over all $5^{n-1}*4$ accounted values.
Remark 2: the exact amount of $x$, such that $f(x) \mod 10^n$ consist from digits 1-2-4-8, from experiments:
... n=15: 54411 / 30517578125 ~= 2^-19.0973107004 n=16: 108655 / 152587890625 ~= 2^-20.4214544789 n=17: 216803 / 762939453125 ~= 2^-21.7467524186 n=18: 433285 / 3814697265625 ~= 2^-23.0697489411 n=19: 866677 / 19073486328125 ~= 2^-24.3914989097 n=20: 1731421 / 95367431640625 ~= 2^-25.7150367656 ...
UPD:
The fact that $2$ is a primitive root modulo $5^n$ is quite important.
We can use it to optimize search for first powers of 2 which increase the 1-2-4-8 run length (first data in this post). For example, for $n=3$ only $13$ of $5^2*4=100$ values correspond to 1-2-4-8 3-digit endings. For $\mod 1000$, period for powers of 2 is equal to order of the group, namely $100$. It means we need to check only 13 of each 100 values. I managed to build the table for $n=20$ which speeds up the computation roughly by $2^{25}$. Sadly each next $n$ for the table is much harder to compute, so this approach does not scale efficiently.
For arbitrary $n$ we can quite efficiently find some $k$ such that $2^k$ has last $n$ digits-powers-of-two.
Let's assume that for some $n$ we know such $k_0$. Consider $a = 2^{k_0} \mod 10^n$. We want to construct $k'$ for $n+1$. Let's look at $a \mod 2^{n+1}$. It's either $0$ or $2^{n}$. If it's $0$, we can set $(n+1)$'s digit to any from $0,2,4,6,8$, in particular $2,4,8$ will fit our goal. If it's $2^{n}$ then we need to set $(n+1)$'s digit to any from $1,3,5,7,9$, in particular $1$ will be fine for us.
After setting the new digit we have some value $a' < 10^{n+1}$. We now find $k'$ by calculating discrete logarithm of $a'$ base $2$ in the group $(\mathbb{Z}/5^{n+1}\mathbb{Z})^*$. It must exist, because $2$ is primitive root modulo $5^{n+1}$ and $a'$ is not divisible by five (meaning that it falls into the multiplicative group).
Summing up, it's possible to extend any existing 1-2-4-8 tail either with $1$, or with any of $2,4,8$. For example, tail of length 1000, consisting only of 1 and 2:
sage: k
615518781133550927510466866560333743905276469414384071264775976996005261582333424319169262744569107203933909361398767112744041716987032548389396865721149211989700277761744700088281526981978660685104481509534097152083798849174934153949598921020219299137483196605381824600377210207048355959118105502326334547495384673753323864726827644650703466356156319492521379682428275201262134907960967634887658195264018797348236155773958687977059474419550906257366056229915615067527218040720408353328787880060032847746927391316869927283585312014157952623949696812057481086276896651244409107902992111507870787820359137244857060839675634572294938878098506151681269336043213294287160464665102314138635395739226878089
sage: print pow(2, k, 10**1000)
1112221212111222212111211212211112121221111221112211221212222212222111211212111122221111222222211112222211112122111222122222212222111221111112211122121122221212111122212112211122121121212211211221122111111111111121211111211212222212112121222221221122111222221222222122212221212111121111112111211222111111211222222222112222212112211212121122212122222211111121112122122112112122222212121121222221112121221222221121122221121222121112111121221221212211121221122121122122122112112112111222212111111221121211211122222122211122211211222122122211112121121111211222211211212211112111212121212111222221212221211212222121122221211112222211221121221211211221222211112121221222122112122221221221221221222211122222222222222222222111121122221121121212111222211112122112112222112221212111112121221221121211221111121212111111121212222212211222122122212112211221221112222121221212121121112111222221122221221121111212121211211211221121211211121122122211212221112122111122212112212121112121121122111112111211111212122112
Solution 3:
No value less than 2^30,000 bigger than 128 follows this pattern, as I have found through this tool:
http://www.michalpaszkiewicz.co.uk/maths/series/powers-of-two.html
You can use this tool to try and find such a value, but it would probably be easier to prove no such number exists using number theory.
Solution 4:
Every such number is of the form of a sum of f(n,m) = 2^n*10^m where m is an integer and n is 0,1,2,3. You can gain insight into this problem by writing this problem out in binary. Every power of two is a 1 followed by zeros, so 1, 10, 100, 1000 is 1,2,4,8 etc. So multiplying a binary by 2 adds a zero to the right. So lets look at powers of ten:
1 1010 1100100 1111101000 10011100010000
The key point to note is that they are followed by more and more trailing zeros. Lets assume this is true. I knows its true up to 10^22 or so, since its used in algorithms to do fast floating point arithmetic, see e.g. here: http://www.exploringbinary.com/why-powers-of-ten-up-to-10-to-the-22-are-exact-as-doubles/ .
EDIT - This is obviously true, since every power of ten is a power of two since 10 = 2*5. Thus ever power of 10^n must have exactly n trailing zeros. (Since powers of 5 are odd they must end in one.)
I can add up to three zeros (multiply by 8), but i cannot exclude any power of ten. So I have to sum these. Clearly I have to eliminate all the 1's. So to convert 100 to the next power of two I take 1100100 and clearly need to add 0011100 i.e. fill in all the zeros with 1's and put a final one in to make them carry like dominoes. This is similar to making a power of ten, work out what you add to make the number nines followed by zeros then add one to which ever column has the last non zero digit.
so can I make 11100 out of ten and one? yes, 10*2 = 10100 and 1*8 = 1000. So 128 is a perfect power.
Lets look at eliminating the 1s in the last two columns. Clearly all numbers of 100 or greater have no ones so don't matter, so I can have 12. I can also have 48. So any such number must end in 12, 28 or 48. Next try eliminating all the 1's in the last three columns. 128 = 10000 will do the job. So will 112 and 248, but thats it*. Lets follow the 112 chain. That will give us 2112 4112 8112 with 5 trailing zeros.
If we move to six trailing zeros we get 22112 42114 82112 14112 and 18112*. There are, around 1000 numbers with six trailing zeros under 10000. So if there is no deep structure, so we see that this form is extremely restrictive in terms of the sets that you can build.
Its even conceivable that an exhaustive search along these lines would lead to all the branches terminating - i.e. that you couldn't eliminate the last one's any further. In that case you would have proved the statement.
*I offer no guarantees that my inspection was exhaustive!