Project Euler Problem 656

Solution

Answer: 888873503555187

Let

$$S_\alpha(n)=\lfloor \alpha n\rfloor-\lfloor \alpha(n-1)\rfloor.$$

For $\alpha=\sqrt{\beta}$, write

$$\alpha = a+\theta, \qquad a=\lfloor \alpha\rfloor,\quad 0<\theta<1.$$

Then

$$S_\alpha(n) = a+\Bigl(\lfloor \theta n\rfloor-\lfloor \theta(n-1)\rfloor\Bigr).$$

Since adding the constant $a$ to every term does not affect whether a finite word is a palindrome, the problem reduces to the binary Sturmian word

$$c_\theta(n)=\lfloor \theta n\rfloor-\lfloor \theta(n-1)\rfloor.$$

For characteristic Sturmian words, a classical result states:

The palindromic prefixes occur exactly at the central-word lengths, which are the semiconvergent denominators of the continued fraction of $\theta$.

$$\theta=[0;a_1,a_2,a_3,\ldots]$$

and $q_n$ are the convergent denominators

$$q_{-1}=0,\qquad q_0=1,\qquad q_{n+1}=a_{n+1}q_n+q_{n-1},$$

then the palindromic prefix lengths are

$$tq_n+q_{n-1}, \qquad n\ \text{even},\quad 1\le t\le a_{n+1}.$$

For $\sqrt{31}$,

$$\sqrt{31}-5=[0;1,1,3,5,3,1,1,10,\ldots]$$

giving denominator sequence

$$1,1,2,7,37,118,155,273,2885,3158,\ldots$$

and therefore palindromic lengths

$$1,; 3,5,7,; 44,81,118,; 273,; 3158,; 9201,15244,21287,\ldots$$

exactly matching the problem statement. Summing the first 20 gives

$$H_{20}(\sqrt{31})=150243655,$$

confirming correctness.

A direct implementation iterates over all non-square $\beta\le1000$, computes the periodic continued fraction of $\sqrt{\beta}-\lfloor\sqrt{\beta}\rfloor$, generates the first $100$ palindromic lengths via the semiconvergent formula above, sums them, and finally takes the last $15$ digits.

The resulting value is:

Answer: 888873503555187