Detailed mathematical approach

Problem Summary

Let

$T(x)=x-\frac{1}{x},\qquad x\neq 0.$

For each exact period \(m\) with \(2\le m\le p\), the problem considers real periodic sequences generated by repeated application of \(T\). If one period of the sequence is \((x_0,x_1,\dots,x_{m-1})\), its range is

$\max_{0\le i\lt m} x_i-\min_{0\le i\lt m} x_i.$

The target quantity \(S(p)\) is the sum of these ranges over all primitive periodic sequences of lengths up to \(p\), counting different cyclic starting positions separately. Directly searching real periodic sequences is not practical, so the implementation re-encodes each orbit by inverse branches and solves one fixed-point problem per primitive orbit.

Mathematical Approach

The solver converts the periodic-sequence problem into a combinatorial enumeration of primitive binary necklaces, followed by a numerical fixed-point solve for each necklace.

Step 1: Write the Two Inverse Branches

If \(y=T(x)\), then \(x\) satisfies

$x^2-yx-1=0.$

So every value \(y\) has two real preimages, namely

$g_{\pm}(y)=\frac{y\pm\sqrt{y^2+4}}{2}.$

A periodic orbit can therefore be reconstructed backward by choosing, at each step, either the \(+\) branch or the \(-\) branch. A binary word \(\sigma=(s_0,s_1,\dots,s_{m-1})\) with \(s_i\in\{-1,+1\}\) determines the composition

$G_\sigma=g_{s_{m-1}}\circ g_{s_{m-2}}\circ \cdots \circ g_{s_0}.$

A period-\(m\) orbit appears when some starting value \(x_0\) satisfies the fixed-point equation

$x_0=G_\sigma(x_0).$

Step 2: Why Primitive Necklaces Are the Right Objects

Two binary words that differ only by a cyclic rotation describe the same orbit, just started at different points of the cycle. So the natural combinatorial object is not a raw binary word but a binary necklace.

If a word is a repetition of a shorter block, then the corresponding orbit has a smaller fundamental period. Therefore exact period \(m\) is represented by primitive binary necklaces of length \(m\). Their number is

$P_m=\frac{1}{m}\sum_{d\mid m}\mu(d)\,2^{m/d},$

where \(\mu\) is the Möbius function. This count is also used as a structural check before the numerical stage begins.

Step 3: Show That Each Branch Word Has a Unique Real Fixed Point

For \(s\in\{-1,+1\}\), differentiating one inverse branch gives

$g_s'(y)=\frac{1}{2}\left(1+s\frac{y}{\sqrt{y^2+4}}\right).$

Because

$-1\lt\frac{y}{\sqrt{y^2+4}}\lt 1,$

we obtain

$0\lt g_s'(y)\lt 1.$

So each inverse branch is an increasing contraction on \(\mathbb{R}\), and any finite composition \(G_\sigma\) is again a contraction. By the contraction mapping principle, every branch word \(\sigma\) has a unique real fixed point. That is why a fixed-point iteration converges reliably and why each primitive necklace corresponds to exactly one real primitive orbit.

Step 4: Recover the Orbit and Its Range

Once the fixed point \(x_0\) of \(G_\sigma\) is known, the orbit itself is obtained by applying the inverse branches in the chosen order:

$x_{i+1}=g_{s_i}(x_i)\qquad (0\le i\le m-2).$

The final branch returns from \(x_{m-1}\) to \(x_0\), closing the cycle. The range attached to \(\sigma\) is

$R(\sigma)=\max_{0\le i\lt m} x_i-\min_{0\le i\lt m} x_i.$

A primitive necklace represents one orbit up to rotation, but the original sum counts all \(m\) cyclic starting positions as distinct periodic sequences. Therefore one primitive necklace contributes

$m\,R(\sigma),$

and the full target becomes

$S(p)=\sum_{m=2}^{p}\ \sum_{\sigma\in\mathcal{N}_m^{\mathrm{prim}}} m\,R(\sigma),$

where \(\mathcal{N}_m^{\mathrm{prim}}\) denotes the primitive binary necklaces of length \(m\).

Step 5: Worked Example for \(m=2\)

There is exactly one primitive binary necklace of length \(2\): one \(+\) branch and one \(-\) branch, up to rotation. Its orbit is a 2-cycle \(\{x,-x\}\). Indeed, the condition \(T(x)=-x\) gives

$x-\frac{1}{x}=-x,$

so

$2x=\frac{1}{x},\qquad x^2=\frac{1}{2}.$

Thus the orbit points are

$x=\pm\frac{1}{\sqrt{2}}.$

The range is therefore

$\frac{1}{\sqrt{2}}-\left(-\frac{1}{\sqrt{2}}\right)=\sqrt{2},$

and because there are two cyclic starting positions, the total contribution is

$2\sqrt{2}=2.8284271247\ldots$

This matches the smallest validation value used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same mathematical pipeline. For each \(m=2,3,\dots,p\), they generate all primitive binary necklaces of length \(m\) using a recursive necklace generator. Before any real-valued computation is performed, the generated count is compared with the Möbius-inversion formula above to confirm that only primitive representatives are present.

For each representative, the implementation starts from \(0\) and repeatedly applies the full inverse-branch composition \(G_\sigma\). This provides a stable initial approximation to the fixed point. It then refines that approximation with Newton's method applied to

$\Phi(x)=G_\sigma(x)-x.$

During this refinement, the derivative of the composition is accumulated by the chain rule while traversing the chosen branches, so the Newton correction uses the exact derivative of the composed inverse map.

After the fixed point is obtained, the implementation unfolds the orbit one branch at a time, tracks the minimum and maximum values encountered, computes \(R(\sigma)\), and adds \(mR(\sigma)\) to the running total. Compensated summation is used to reduce floating-point cancellation. The C++ and Python implementations distribute independent necklace blocks across workers, while the Java implementation delegates the numerical evaluation to the same underlying computation and returns the resulting decimal value.

Complexity Analysis

Let

$P_m=\frac{1}{m}\sum_{d\mid m}\mu(d)\,2^{m/d}$

be the number of primitive binary necklaces of length \(m\). Processing one necklace requires \(O(mI)\) arithmetic operations, where \(I\) is the small number of fixed-point and Newton iterations. Hence the total running time is

$O\!\left(\sum_{m=2}^{p} P_m\,m\,I\right).$

Since \(P_m\sim 2^m/m\), the growth is essentially exponential in \(p\), with the largest periods dominating the cost. Memory usage for a single length is \(O(P_m)\) to store the necklace representatives, plus \(O(1)\) orbit data and a small amount of worker-local accumulation state.

Footnotes and References

1. Problem page: Project Euler 729
2. Necklace counting: Wikipedia - Necklace (combinatorics)
3. Möbius inversion: Wikipedia - Möbius inversion formula
4. Contraction mapping principle: Wikipedia - Banach fixed-point theorem
5. Newton's method: Wikipedia - Newton's method
6. Compensated summation: Wikipedia - Kahan summation algorithm