Project Euler Problem 721

Solution

Answer: 700792959

Let

$$m=\lceil \sqrt a\rceil,\qquad \alpha=m+\sqrt a,\qquad \beta=m-\sqrt a.$$

Then

$$\alpha+\beta=2m,\qquad \alpha\beta=m^2-a.$$

For non-square $a$, we have $0<\beta<1$. Define

$$S_n=\alpha^n+\beta^n.$$

Because $S_n$ satisfies the integer recurrence

$$S_n=(2m)S_{n-1}-(m^2-a)S_{n-2},$$

with integer initial values $S_0=2,\ S_1=2m$, every $S_n$ is an integer.

Since $0<\beta<1$,

$$0<\beta^n<1,$$

hence

$$\lfloor \alpha^n\rfloor = S_n-1.$$

Therefore, for non-square $a$,

$$f(a,n)=\alpha^n+\beta^n-1.$$

For perfect squares $a=k^2$,

$$f(k^2,n)=(2k)^n.$$

Using fast linear-recurrence exponentiation modulo

$$M=999999937,$$

and summing

$$G(n)=\sum_{a=1}^n f(a,a^2)$$

up to $n=5{,}000{,}000$, one obtains

$$G(5{,}000{,}000)\equiv 700792959 \pmod{999999937}.$$

This matches the published Project Euler result dataset.

Answer: 700792959