Detailed mathematical approach

Problem Summary

For every non-square integer \(2 \le n \le 100000\), the task is to find the reduced fraction \(\frac{p}{q}\) with \(1 \le q \le 10^{12}\) that minimizes the error \( \left| \sqrt{n} - \frac{p}{q} \right| \), and then sum all winning denominators \(q\).

Because \(\sqrt{n}\) is irrational whenever \(n\) is not a square, there is no tie: exactly one reduced fraction is closest for each such \(n\). The difficulty is the denominator limit \(10^{12}\). A direct search over all denominators is impossible, so the solution uses the continued fraction of \(\sqrt{n}\) and turns the choice into an exact integer comparison between two final candidates.

Mathematical Approach

The whole argument rests on one classical fact: once a denominator bound is imposed, the best rational approximation to an irrational number must come from the continued-fraction ladder, namely from a convergent or from an intermediate fraction between two consecutive convergents. For \(\sqrt{n}\), the code never leaves exact integer arithmetic while it walks that ladder.

Continued fractions of \(\sqrt{n}\)

Let \(a_0 = \lfloor \sqrt{n} \rfloor\). For a non-square \(n\), the continued fraction of \(\sqrt{n}\) is periodic after the first term, and the standard quadratic-irrational state can be written as

$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$

The next state is obtained entirely with integers:

$m_{k+1} = d_k a_k - m_k,$

$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$

$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$

This recurrence is exactly what the implementations maintain. It generates the partial quotients of \(\sqrt{n}\) without ever approximating \(\sqrt{n}\) numerically.

Convergents and the only fractions that matter

If

$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$

then the convergents satisfy

$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$

with initial values \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\). These convergents are the principal best approximations.

Between two consecutive convergents there are also semiconvergents, sometimes called intermediate fractions:

$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$

When a denominator cap \(D\) is present, the optimum fraction under \(q \le D\) must be either the last convergent whose denominator still fits, or one of these semiconvergents for the next continued-fraction digit. Nothing else can beat them.

Stopping at the first denominator that exceeds the bound

Let \(k\) be the first index for which \(q_k > D\). Then \(q_{k-1} \le D\), so the previous convergent is admissible, while the next full convergent is already too large.

Every admissible semiconvergent on that last edge has denominator

$q_t = t q_{k-1} + q_{k-2}.$

The largest allowed choice is therefore

$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$

which gives the boundary semiconvergent \(q_t \le D < q_{t+1}\). Because \(q_k = a_k q_{k-1} + q_{k-2} > D\), this \(t\) automatically satisfies \(0 \le t < a_k\).

Among semiconvergents on the same edge, larger \(t\) means a larger denominator and also a smaller error. In other words, once the bound has cut the edge, only the boundary semiconvergent needs to be compared with the last admissible convergent.

An exact comparison with no floating point

The key identity is

$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$

From this one obtains the exact errors

$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$

and for the semiconvergent with parameter \(t\),

$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$

So the semiconvergent is better exactly when

$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$

Substituting \(x_k = \frac{\sqrt{n} + m_k}{d_k}\) turns that into

$q_{k-1} \sqrt{n} < R,$

where

$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$

This is the integer test used by the implementations. If \(R \le 0\), the semiconvergent cannot win. If \(R > q_{k-1}(a_0+1)\), then it definitely wins because \(\sqrt{n} < a_0 + 1\). Otherwise both sides are positive, so the comparison becomes the exact square test

$R^2 > n q_{k-1}^2.$

No floating-point approximation is needed at any stage.

Worked example: \(\sqrt{13}\)

The continued fraction is

$\sqrt{13} = [3; 1,1,1,1,6,\dots].$

The convergents begin

$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$

Suppose first that \(D=20\). The last admissible convergent is \(\frac{18}{5}\), because the next denominator \(33\) is too large. At this cutoff stage the quadratic-irrational state is \(m_k=3\), \(d_k=1\), and \(q_{k-1}=5\), \(q_{k-2}=3\). The boundary parameter is

$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$

so the boundary semiconvergent has denominator \(q_t = 3 \cdot 5 + 3 = 18\), namely \(\frac{65}{18}\). The comparison value is

$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$

Since \(5 \sqrt{13} \approx 18.0278\), we have \(R < 5\sqrt{13}\), so \(\frac{65}{18}\) is worse than \(\frac{18}{5}\). The winning denominator is therefore \(5\).

Now change the bound to \(D=30\). Then

$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$

so the boundary semiconvergent is \(\frac{101}{28}\). This time

$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$

and \(38 > 5\sqrt{13}\), so \(\frac{101}{28}\) beats \(\frac{18}{5}\). The winning denominator becomes \(28\). This is exactly the behavior checked by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline: skip perfect squares, generate the continued fraction of each \(\sqrt{n}\) with the integer recurrence above, stop at the first convergent whose denominator exceeds \(10^{12}\), and then decide between the previous convergent and the single boundary semiconvergent.

Maintaining the continued-fraction state

For each non-square \(n\), the implementation starts from \(a_0=\lfloor \sqrt{n} \rfloor\) and updates the quadratic-irrational state \((m_k,d_k,a_k)\) together with the convergent numerators and denominators. The recurrence for \((p_k,q_k)\) is synchronized with the recurrence for \((m_k,d_k,a_k)\), so when the denominator first crosses the bound, all data needed for the final comparison is already available.

Choosing the winning denominator

Once the first oversized convergent appears, the implementation sets the provisional answer to the previous denominator \(q_{k-1}\). If the denominator bound still leaves room beyond \(q_{k-1}\), it computes the boundary value \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) and forms the corresponding semiconvergent denominator \(t q_{k-1} + q_{k-2}\).

The final decision is made with the exact criterion above. The C++ and Java implementations use wider integer arithmetic for intermediate values, while Python relies on arbitrary-precision integers automatically. The C++ implementation also performs small exact validations against brute force before launching the full computation, which confirms the continued-fraction logic on tiny cases.

Accumulating the global sum

After the winning denominator for one \(n\) is known, it is added to the running total. The C++ implementation distributes different \(n\)-values across several worker threads; the Python and Java implementations execute the same logic serially. The mathematical decision rule is identical in all three languages.

Complexity Analysis

For one fixed \(n\), the loop continues until a convergent denominator exceeds \(D\). Since every partial quotient satisfies \(a_k \ge 1\), the denominators obey \(q_k \ge q_{k-1} + q_{k-2}\), so they grow at least as fast as Fibonacci numbers. Therefore the number of continued-fraction steps is \(O(\log D)\).

Each step performs only a constant amount of integer arithmetic, so over all non-squares \(n \le N\) the total work is \(O(N \log D)\), with \(N=100000\) and \(D=10^{12}\) in this problem. Memory usage is \(O(1)\) per worker aside from the running total. The practical speed comes from replacing a hopeless scan over \(10^{12}\) denominators by a very short continued-fraction walk for each \(n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=192
2. Continued fractions: Wikipedia - Continued fraction
3. Convergents and semiconvergents: Wikipedia - Convergents of continued fractions
4. Quadratic irrationals and periodic expansions: Wikipedia - Periodic continued fraction
5. Diophantine approximation: Wikipedia - Diophantine approximation