Project Euler Problem 318

Solution

Answer: 709313889

Let

$$\alpha=\sqrt p+\sqrt q,\qquad \beta=\sqrt q-\sqrt p$$

with $p<q$, $p,q\in \mathbb Z_{>0}$.

We are studying

$$\alpha^{2n}.$$

The key observation is that $\alpha\beta=q-p$, and

$$(\sqrt p+\sqrt q)^{2n}+(\sqrt q-\sqrt p)^{2n}$$

is always an integer.

Indeed, since the odd irrational terms cancel in the binomial expansion,

$$A_n=\alpha^{2n}+\beta^{2n}\in \mathbb Z.$$

Thus

$$\alpha^{2n}=A_n-\beta^{2n}.$$

Since $0<\beta<1$ (this condition will matter), the fractional part is

$${\alpha^{2n}}=1-\beta^{2n}.$$

Hence the fractional part approaches $1$ iff

$$\beta<1.$$

Because $\beta=\sqrt q-\sqrt p$, the admissible pairs are exactly those satisfying

$$\sqrt q-\sqrt p<1.$$

We want $C(p,q,n)\ge 2011$, i.e. at least 2011 consecutive nines after the decimal point.

That means

$$1-\beta^{2n}$$

must differ from $1$ by at most $10^{-2011}$:

$$\beta^{2n}\le 10^{-2011}.$$

Taking logs:

$$2n\ln\beta \le -2011\ln 10.$$

Since $\ln\beta<0$,

$$n \ge \frac{2011\ln 10}{-2\ln \beta}.$$

Therefore

$$N(p,q) = \left\lceil \frac{2011\ln 10} {-2\ln(\sqrt q-\sqrt p)} \right\rceil.$$

We sum this over all

$$p<q,\qquad p+q\le 2011,\qquad \sqrt q-\sqrt p<1.$$

Python implementation

from math import sqrt, log, ceil

LIMIT = 2011
K = 2011
LN10 = log(10)

total = 0

for p in range(1, LIMIT):
    # q must satisfy p < q and p + q <= LIMIT
    for q in range(p + 1, LIMIT - p + 1):

        beta = sqrt(q) - sqrt(p)

        # Only these pairs have fractional part -> 1
        if beta < 1:
            n = ceil(K * LN10 / (-2 * log(beta)))
            total += n

print(total)

Code walkthrough

Loop over all integer pairs $(p,q)$ with $p<q$ and $p+q\le 2011$.
Compute

$$\beta=\sqrt q-\sqrt p.$$

Keep only $\beta<1$, since otherwise $\beta^{2n}$ does not tend to $0$, so the fractional part cannot approach $1$.
Compute

$$N(p,q)= \left\lceil \frac{2011\ln 10} {-2\ln \beta} \right\rceil.$$

Add all values.

Small check: $(p,q)=(2,3)$

$$\beta=\sqrt3-\sqrt2\approx0.317837$$

Then:

$n=2$: $\beta^{4}\approx0.0102$, giving $0.9897\ldots$ → one leading 9.
$n=3$: $\beta^{6}\approx0.00103$, giving $0.9989\ldots$ → two leading 9s.

This matches the problem statement.

The full computation gives:

Answer: 709313889