Detailed mathematical approach

Problem Summary

For each nonsquare integer \(\beta\), the problem associates a sequence of positive integers derived from the simple continued fraction of \(\sqrt{\beta}\). If that sequence is written as \(h_1,h_2,h_3,\dots\), then the quantity for one fixed \(\beta\) is

$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$

The final task is to evaluate this quantity for every nonsquare \(\beta\) between \(2\) and \(1000\), always with \(g=100\), and add the results modulo \(10^{15}\):

$S=\sum H(\beta,100)\pmod{10^{15}},$

where the sum runs over all nonsquare integers \(2\le \beta\le 1000\). The C++, Python, and Java implementations all compute the same object by combining continued-fraction coefficients, convergent denominators, and arithmetic blocks coming from odd indices only.

Mathematical Approach

The key observation is that the required sequence is not built from the convergents themselves, but from blocks of semiconvergent denominators determined by the continued fraction of \(\sqrt{\beta}\).

Step 1: Build the Continued Fraction of \(\sqrt{\beta}\)

For a nonsquare integer \(\beta\), write

$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$

The tail is periodic because \(\sqrt{\beta}\) is a quadratic irrational. The standard recurrence used to generate the coefficients is

$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$

$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$

This recurrence is exactly what the implementations maintain while they lazily request more coefficients.

Step 2: Generate the Convergent Denominators

Let \(q_n\) denote the denominators of the convergents of the continued fraction. They satisfy

$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$

Only these denominators are needed for the target sequence. Since the final answer is required modulo \(10^{15}\), the implementations reduce every newly generated denominator modulo \(10^{15}\) immediately. This is safe because the recurrence uses only addition and multiplication, so modular reduction commutes with every later update.

Step 3: Form the Odd-Index Arithmetic Blocks

For each odd index \(i=2b+1\), the sequence contributes the block

$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$

This is an arithmetic progression with base \(q_{i-2}\), common difference \(q_{i-1}\), and length \(a_i\). Concatenating the odd blocks

$B_1,\ B_3,\ B_5,\ B_7,\dots$

produces the infinite sequence \(h_1,h_2,h_3,\dots\) required by the problem. Even indices do not contribute, so the implementations skip them entirely.

Step 4: Turn the Blocks into the Prefix Sum \(H(\beta,g)\)

Suppose the current odd block is \(B_i\), but only its first \(t\) terms are needed, where \(1\le t\le a_i\). Then those \(t\) terms sum to

$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$

Therefore \(H(\beta,g)\) can be viewed as a prefix sum across consecutive arithmetic blocks: consume whole blocks while their entire length fits inside the first \(g\) terms, and truncate the final block when necessary. The implementations follow this same logic, but they emit the terms one by one so that every intermediate value stays reduced modulo \(10^{15}\).

Step 5: Sum Over All Nonsquare \(\beta\)

Once \(H(\beta,100)\) is known for one nonsquare \(\beta\), it is added into the global total. Perfect squares are skipped from the start because their square roots are rational and do not belong to the periodic quadratic-irrational case used here.

So the full computation is simply

$S=\sum H(\beta,100)\pmod{10^{15}},$

with the sum taken over all nonsquare integers \(2\le \beta\le 1000\).

Worked Example: \(\beta=2,\ g=8\)

For \(\beta=2\), we have

$\sqrt{2}=[1;\overline{2}],$

so every tail coefficient equals \(2\). The denominator recurrence gives

$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$

The odd blocks are therefore

$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$

Taking the first eight terms gives

$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$

hence

$H(2,8)=1+2+7+12+41+70+239+408=780.$

This matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. For each nonsquare \(\beta\), they keep the current quadratic-irrational state \((m,d,a)\), extend the continued-fraction coefficients only when a new denominator is needed, and build the denominator list lazily from the initial values \(q_{-1}=0\) and \(q_0=1\).

Each time the next odd block is requested, the implementation reads the corresponding continued-fraction coefficient to get the block length, uses the previous two convergent denominators as the block's base and step, and emits exactly as many terms as are still needed for the prefix of length \(g\).

Every arithmetic update is reduced modulo \(10^{15}\): while generating denominators, while advancing through a block, and while adding the contribution of one \(\beta\) into the overall total. That keeps the numbers bounded without changing the final residue.

Finally, the outer loop scans \(\beta=2,3,\dots,1000\), skips perfect squares, evaluates \(H(\beta,100)\), and prints the accumulated result as a 15-digit zero-padded decimal string.

Complexity Analysis

For one fixed pair \((\beta,g)\), the implementation emits exactly \(g\) sequence terms. Each emitted term costs \(O(1)\) amortized time once the occasional continued-fraction coefficient and denominator extension are accounted for, so the total running time is \(O(g)\).

The arrays of continued-fraction coefficients and convergent denominators also grow only as far as needed to cover those \(g\) emitted terms. Since every block has length at least \(1\), this requires \(O(g)\) stored values, so the auxiliary memory usage is \(O(g)\).

For the complete problem, the upper bound \(1000\) is fixed. In a generalized form with upper limit \(B\), the total cost would be \(O(Bg)\) time and \(O(g)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=656
2. Quadratic irrationals and periodic continued fractions: Wikipedia - Periodic continued fraction
3. Continued fractions and convergents: Wikipedia - Continued fraction
4. Best rational approximations and semiconvergents: Wikipedia - Best rational approximations