1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.