Detailed mathematical approach

Problem Summary

For each integer \(n\in\{0,1,\dots,50\}\), the problem defines an exceptional continued-fraction constant \(K_n\) coming from a dyadic truncation built out of powers of two. The final target is not one particular \(K_n\), but the geometric mean of all fifty-one constants.

The solution files make an important distinction between validation and production. The continued fraction is used only to confirm the limiting behavior numerically. The actual answer is obtained from explicit formulas for \(\log K_n\), followed by

$G=\left(\prod_{n=0}^{50} K_n\right)^{1/51}=\exp\left(\frac{1}{51}\sum_{n=0}^{50}\log K_n\right).$

So the computational problem is reduced to evaluating a short logarithmic sum accurately.

Mathematical Approach

Two concrete mathematical objects appear in the implementations. The first is a finite truncation whose continued fraction gives an empirical approximation to the exceptional constant. The second is a closed form for the limiting value, and that closed form is organized by where \(n\) sits relative to neighboring powers of two.

The Finite Truncation Used for Validation

For a truncation depth \(m\), set \(M=2^m\) and define

$S_m=\sum_{i=0}^{m}2^{M-2^i}.$

For a fixed \(n\), the validation experiment then forms

$Q_{n,m}=2^{M-n},\qquad R_{n,m}=S_m \bmod Q_{n,m}.$

The ratio actually fed into the continued-fraction expansion is

$\frac{Q_{n,m}}{R_{n,m}}=[a_1;a_2,\dots,a_L],$

and the empirical logarithmic mean of its partial quotients is

$E_{n,m}=\frac{1}{L}\sum_{j=1}^{L}\log a_j.$

This \(E_{n,m}\) is not the final quantity requested by the problem. Instead, it is a finite-size observable used to check that the limiting value really is \(\log K_n\). The C++ implementation evaluates this model only for selected sample values of \(n\), precisely as a consistency check.

The Closed Form Is Organized by Dyadic Position

The production path starts from the Mersenne-type number

$b=2^n-1.$

From there, the formula for \(\log K_n\) depends on which dyadic region contains \(n\).

For the base case \(n=0\), the implementations use

$\log K_0=\frac{\log 2+2\log 4+\log 6}{4},$

so \(K_0=192^{1/4}\).

If \(n=2^t-1\) for some \(t\ge 1\), then

$\log K_n=\frac{\log 2+2\log b}{5},$

equivalently \(K_n=(2b^2)^{1/5}\).

If \(n=2^t\), then

$\log K_n=\frac{\log b}{2}+\frac{\log(b-1)+\log(b+1)}{12},$

equivalently \(K_n=b^{1/2}(b^2-1)^{1/12}\).

For the interior of a dyadic interval, let

$p=2^{\lfloor\log_2 n\rfloor},\qquad q=2p,\qquad e=q-n,\qquad c=2^e-1.$

Then the remaining branch is

$\log K_n=\frac{\log b}{3}+\frac{\log c}{6}+\frac{\log(c-1)+\log(c+1)}{12},$

or \(K_n=b^{1/3}c^{1/6}(c^2-1)^{1/12}\).

This shows the real structure of the problem: outside the base case, the exceptional constant is determined by one Mersenne-type factor attached to \(n\) itself and, in the general dyadic interval, a second Mersenne-type factor attached to the distance from \(n\) to the next power of two.

Why the Boundary Cases Need Their Own Branches

The general interior formula contains the factors \(\log(c-1)\) and \(\log(c+1)\). If \(n=q-1=2^t-1\), then \(e=1\) and \(c=1\), so \(c-1=0\) and the term \(\log(c-1)\) breaks down. That is exactly why the “one less than a power of two” case is separated in the code.

The exact power-of-two case is cleaner. When \(n=2^t\), the dyadic interval begins at \(p=n\), hence \(q=2n\), \(e=n\), and therefore

$c=2^e-1=2^n-1=b.$

Substituting \(c=b\) into the general expression gives

$\frac{\log b}{3}+\frac{\log b}{6}+\frac{\log(b-1)+\log(b+1)}{12}=\frac{\log b}{2}+\frac{\log(b-1)+\log(b+1)}{12},$

which is exactly the power-of-two branch. So one boundary creates a genuine singularity, while the other collapses to a simpler identity. The branch structure is therefore a direct reflection of the dyadic geometry encoded by the formulas.

Worked Examples Near a Dyadic Boundary

Take \(n=20\). It lies in the dyadic interval from \(16\) to \(32\), so

$p=16,\qquad q=32,\qquad e=12,\qquad b=2^{20}-1=1048575,\qquad c=2^{12}-1=4095.$

Therefore

$\log K_{20}=\frac{\log 1048575}{3}+\frac{\log 4095}{6}+\frac{\log 4094+\log 4096}{12}.$

Now move to \(n=31=2^5-1\). Here the distance to the next power of two is only \(1\), so the interior formula would produce \(c=1\) and \(\log(c-1)=\log 0\). The separate boundary formula avoids that problem and gives

$\log K_{31}=\frac{\log 2+2\log(2^{31}-1)}{5}.$

At the next point, \(n=32=2^5\), the exact-power formula applies instead:

$\log K_{32}=\frac{\log(2^{32}-1)}{2}+\frac{\log(2^{32}-2)+\log(2^{32})}{12}.$

The same logic also explains the small checkpoint used by the validation code: for \(n=2\), the exact-power branch gives \(\exp(\log K_2)\approx 2.059767\).

How the Code Works

Closed-Form Evaluation Path

The C++, Python, and Java implementations all use the same production algorithm. They iterate over \(n=0,1,\dots,50\), determine whether \(n\) is \(0\), a power of two, one less than a power of two, or an interior point of a dyadic interval, and then evaluate the corresponding closed formula for \(\log K_n\).

Those logarithms are accumulated in floating-point arithmetic, divided by \(51\), and converted back with one final exponential. This is both mathematically natural and numerically stable, because the requested result is a geometric mean. For the actual range \(0\le n\le 50\), every integer appearing in the closed formulas fits comfortably in ordinary 64-bit arithmetic.

Validation by Continued Fractions

The C++ implementation adds an explicit validation layer. It constructs the finite truncation for \(m=16\) using arbitrary-precision integers, reduces \(S_m\) modulo \(Q_{n,m}\), applies the Euclidean algorithm to extract the partial quotients of \(Q_{n,m}/R_{n,m}\), and averages their logarithms.

That empirical mean is compared against the closed formula for the sample values \(n\in\{0,1,2,5,20,31,32,50\}\), using small relative tolerances. The Python and Java implementations omit this verification path and keep only the closed-form computation needed for the final answer.

Complexity Analysis

The production computation takes \(O(51)\) time and \(O(1)\) memory, because each of the fifty-one values of \(n\) is processed in constant time. If the same method were extended to \(0\le n\le N\), the cost would be \(O(N)\).

The validation layer in the C++ implementation uses arbitrary-precision arithmetic and a continued-fraction expansion, but it still contributes only fixed overhead here: the truncation depth is fixed at \(m=16\), and only eight sample values are checked.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=911
2. Khinchin's constant: Wikipedia - Khinchin's constant
3. Continued fractions: Wikipedia - Continued fraction
4. Euclidean algorithm: Wikipedia - Euclidean algorithm
5. Geometric mean: Wikipedia - Geometric mean
6. Mersenne numbers: Wikipedia - Mersenne number