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

Question

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.

Answer 1

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.

Answer 2

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}[2] &= 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}[2] = 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$