# Powers of $2$ starting with $123$...Does a pattern exist?

I'm currently working on Project Euler problem #686 "Powers of Two". The first power of $$2$$ which starts with $$123$$... is $$2^{90}$$. I noticed that the next powers of $$2$$ that start with $$123$$... seem to follow a pattern. The exponent is always increased by either $$196$$, $$289$$ or $$485$$ (which is $$196 + 289$$). But I'm not able to figure out what the pattern actually is. Any hint is highly welcome.

If a power of 2 starts with 123, then it must be between $$1.23\times 10^n$$ and $$1.24\times 10^n$$ for some $$n$$.

So you want $$k$$ and $$n$$ for which $$1.23\times 10^n\leq 2^k < 1.24\times 10^n$$.

This is easier to deal with if we take logs (base 10). Then you want

$$\log(1.23) + n\leq k\log(2) < \log(1.24)+n$$

That is, the fractional part $$\lfloor k\log(2)\rfloor$$ satistfies $$\log(1.23)\leq \lfloor k\log(2)\rfloor < \log(1.24),$$

that is, writing these as decimals,

$$0.0899051143939792\leq \lfloor 0.3010299956639811 k\rfloor < 0.09342168516223505.$$

Note that $$0.0899051143939792$$ and $$0.09342168516223505$$ don't differ by much. If you've found $$k_1$$ and $$k_2$$ that satisfy the above inequalities, then $$0.3010299956639811 (k_1-k_2)$$ is pretty close to an integer.

We could find example differences $$\Delta k$$ by looking for rational approximations of $$\log(2)$$, which we can do using the continued fraction expansion of $$\log(2)$$:

$$\log(2)=\frac{1}{3+\frac{1}{3+\frac1{9+...}}}$$

The numbers in that expresison are $$3,3,9,2,2,4,6,2,1,...$$ with no discernible pattern. If we cut the fraction off at various places we get "best rational approximations" of $$\log(2)$$. The first few are:

$$\log(2)\approx\frac{1}{3}$$ $$\log(2)\approx\frac{1}{3+\frac{1}{3}}=\frac{3}{10}$$ $$\log(2)\approx\frac{1}{3+\frac{1}{3+\frac1{9}}}=\frac{28}{93}$$ $$\log(2)\approx\frac{59}{196}$$

The errors in these are, respectively, $$0.0323033...$$, $$0.001029996...$$, $$0.00045273..$$ and $$0.0000095875...$$.

If you have a fraction $$\frac{p}{q}$$ which is within $$\epsilon$$ of $$\log(2)$$, then $$q$$ will sometimes work as $$\Delta k$$, because it means that multiplying $$2^k$$ by $$2^q$$ will change $$\lfloor\log(2)k\rfloor$$ by $$q\epsilon$$. If $$2^k$$ starts with 123, then as long as $$q\epsilon$$ is less than $$\log(1.24) - \log(1.23)$$, we have a chance that $$2^{k+q}$$ also will.

$$\log(1.24)-\log(1.23)=0.0035167...$$. Multiplying the errors above by the denominators, we get

• $$\frac13$$ obviously won't work: $$0.0323033\times3=0.0969...$$ which is way bigger than $$0.0035167$$
• $$\frac3{10}$$ won't work: $$0.001029996\times10=0.0102999..$$, which is also bigger than $$0.0035167$$
• $$\frac{28}{93}$$ won't work, but only just: $$0.00045273\times93=0.0042104...$$. You probably found some "near misses" 93 apart.
• $$\frac{59}{196}$$ works! $$0.0000095875\times 196 = 0.0018791$$, which is less than $$0.0035167$$. So it's possible to have $$2^k$$ and $$2^{k+196}$$ both starting with 123 - but not all of $$2^k$$, $$2^{k+196}$$ and $$2^{k+2\times196}$$, since $$2\times 0.0018791=0.003758$$, which is (just) too big.

The next continued fractions for $$\log(2)$$ are $$\frac{146}{485}$$ (recognise anything there?), $$\frac{643}{2136}$$ and $$\frac{4004}{13301}$$.

You'll notice this method missed your 289. That's because the continued fraction method gives the best rational approximations. It's true that $$\log(2)\approx\frac{87}{289}$$, but that's not as good an approximation as $$\frac{59}{196}$$.

In general, you're looking for numbers $$q$$ for which $$q\log(2)$$ is within $$0.0035167$$ of an integer. Finding those will be easier than finding powers of 2, perhaps :)

The property of 196 and 485 that makes them give rise to patterns in the powers of 2 that start with 123 is just "$$q\times\log(2)$$ is nearly an integer". That's got nothing much to do with the specific prefix you chose. If you look for powers of 2 starting with, say, 234, you'll probably see some of the exact same numbers popping up - but not 196, alas, since $$\log(2.35/2.34)=0.00185...$$ is a tighter requirement, and $$196\times0.0000095875=0.00187$$ is now too big. 485 will still work, for any starting three digits (though only just for 999), as will 2136, 13301, etc.

see if this helps: \begin{align*} 2^k&= 123\dots\\ 2^k&= 1.23\dots\times 10^{p}\\ log_{10}[2^k] &= log_10[1.23\dots\times 10^{p}]\\ k\cdot log_{10} &= log_{10}[1.23]+p\\ \end{align*} where $$p\in\mathbb{Z}_+$$

Now the algorithm is straightforward. Iterate over k and multiply by $$log_{10} = 0.30103$$ until you reach a k that has fractional value between $$log_{10}[1.23]=0.08990$$ and $$log_{10}[1.24]=0.09342$$. The reason for the pattern you observe is also that the log multiples may be close to some integer values.

For example: $$196 \times log(2) = 59.001$$, $$289 \times log(2) = 86.99$$ and $$485 \times log(2) = 145.9995$$