Detailed mathematical approach

Problem Summary

Let \(p_1=2,p_2=3,p_3=5,\dots\) be the prime numbers, and define

$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$

So the partial quotients of \(x\) begin

$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$

The implementations then study the transformed number

$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$

and the goal is to evaluate

$S=\sum_{k=0}^{10^8-1}\beta_k.$

The difficulty is that neither \(x\) nor \(y\) should be approximated by enormous convergents. Instead, the continued fraction of \(y\) is generated directly from the continued fraction of \(x\) in a single streaming process.

Mathematical Approach

The central idea is to keep track of how the unread tail of \(x\) is transformed, rather than to rebuild the whole number after every new coefficient.

The prime-block continued fraction

After the leading \(2\), the input coefficients come in a very rigid pattern: for each prime \(p_j\), there are exactly \(p_j\) copies of \(1\), followed by another \(2\). The beginning of the stream is therefore

$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$

This matters because the algorithm never forms \(x\) itself. It only requests the next partial quotient when the transformation state cannot yet determine the next output digit of \(y\).

Encoding the unread tail by a linear-fractional map

Let \(z\) denote the unread tail of the original continued fraction. At any moment the remaining task can be written as

$T(z)=\frac{Az+B}{Cz+D},$

with positive integers \(A,B,C,D\). Initially, before any input has been read,

$T(z)=\frac{2z+3}{3z+2},$

so the starting matrix is \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).

If the next input coefficient is \(n\), then the current tail becomes \([n;z]=n+\frac1z\). Substituting this into \(T\) gives

$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$

Therefore one input step updates the matrix by

$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $

This recurrence is exact; no approximation is introduced at any stage.

Why matching floors force the next output coefficient

Because every unread continued-fraction tail is positive, \(z>0\). For the current state \(T(z)=\frac{Az+B}{Cz+D}\), compare \(T(z)\) with the two rational endpoints \(\frac{A}{C}\) and \(\frac{B}{D}\):

$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$

These two differences always have opposite signs, so \(T(z)\) lies between \(\frac{A}{C}\) and \(\frac{B}{D}\) for every admissible tail \(z\). Hence, if

$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$

then the next continued-fraction coefficient of \(y\) is forced to be \(a\), regardless of what the rest of the prime-driven input will be.

After removing that integer part and inverting the remainder,

$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$

So one output step becomes

$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $

This is the mechanism that turns the input continued fraction into the output continued fraction one coefficient at a time.

A small invariant that stays true throughout

The determinant starts at

$AD-BC=2\cdot2-3\cdot3=-5.$

Every input step multiplies the matrix on the right by \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\), whose determinant is \(-1\), and every output step also flips the sign of the determinant. Therefore

$|AD-BC|=5$

for the entire run. This is not the main source of speed, but it is a useful invariant that confirms the transformation remains exact.

Worked example: the first three output digits

Start from

$T(z)=\frac{2z+3}{3z+2}.$

The first input coefficient is \(2\). After one input update,

$T_1(z)=\frac{7z+2}{8z+3}.$

Now

$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$

so the first output coefficient is \(\beta_0=0\). Removing that digit gives

$T_2(z)=\frac{8z+3}{7z+2}.$

Again the two bounds have the same floor, because

$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$

so \(\beta_1=1\). The next unread input digits are \(1,1,2\). Reading those three digits yields

$T_3(z)=\frac{41z+16}{8z+3},$

and now

$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$

Hence \(\beta_2=5\). Continuing in the same manner produces the checked prefix

$0,1,5,6,16,9,1,10,16,11,\dots.$

How the Code Works

Producing the prime-driven input stream

The C++, Python, and Java implementations generate primes incrementally by trial division against the primes already discovered. Those primes determine the input continued fraction of \(x\): one initial \(2\), then prime-length runs of \(1\)'s, each run followed by another \(2\).

Streaming the output and accumulating the sum

The implementation keeps only four integers for the current linear-fractional state, plus a counter for how many output coefficients have been produced and a running total for their sum. Whenever the two rational bounds \(\frac{A}{C}\) and \(\frac{B}{D}\) have the same floor, that floor is appended to the continued fraction of \(y\) and added to the sum. Otherwise the next input coefficient of \(x\) is read and the input recurrence is applied.

This means the continued fraction of \(y=\frac{2x+3}{3x+2}\) is generated directly from the prime-driven input, without reconstructing \(x\) from convergents. The implementations also verify the short prefix \(0,1,5,6,16,9,1,10,16,11\), whose first ten terms sum to \(75\), before processing the full target of \(10^8\) output coefficients.

Complexity Analysis

Let \(M\) be the number of requested output coefficients and let \(N\) be the number of input coefficients that must be read before those \(M\) outputs become determined. The linear-fractional transducer performs \(O(M+N)\) fixed-width arithmetic updates, because every loop iteration is exactly one input update or one output update.

The only auxiliary structure that grows is the list of primes needed to delimit the blocks of ones. With the straightforward trial-division prime generator used here, prime production has the usual incremental primality-testing cost up to the largest prime block encountered. Memory usage is therefore \(O(\pi(P))\) for the cached primes up to the largest generated prime \(P\), plus \(O(1)\) for the four-state transducer, the counters, and the running sum.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=946
2. Continued fractions: Wikipedia - Continued fraction
3. Möbius transformations and linear-fractional maps: Wikipedia - Möbius transformation
4. Prime numbers: Wikipedia - Prime number