Detailed mathematical approach

Problem Summary

The puzzle is governed by three step sizes

$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}},$

applied cyclically to a point on the unit interval. For each triple \(9 \le a < b < c\), we seek the least positive number of steps \(T(a,b,c)\) for which the full three-phase system is synchronized again. The overall quantity is

$\sum_{9\le a < b < c \le n} T(a,b,c).$

A brute-force simulation is hopeless because the synchronization time can be very large, so the solution converts the continuous process into a finite automaton and then solves the resulting congruence conditions exactly.

Mathematical Approach

The key observation is that each phase uses the same piecewise map with a different step size. For \(0<s<1\), define

$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$

The dynamics applies \(\Phi_{s_0}\), then \(\Phi_{s_1}\), then \(\Phi_{s_2}\), and repeats this three-phase cycle forever. Each branch either reflects the interval orientation or preserves it, so every transition naturally carries one binary flip bit.

Step 1: Turn the Continuous Process into a State Graph

In each phase, the relevant breakpoints are the discontinuity \(s_\phi\), the endpoint \(0\), and all of their backward images under earlier phases. Once those breakpoints are known, every open interval between consecutive breakpoints behaves uniformly: every point in that interval goes to the same next interval and experiences the same orientation change.

Therefore one state is simply

$\text{state}=(\text{phase},\ \text{interval}).$

Because every state has exactly one successor, the entire system becomes a directed graph in which every component eventually lies on a cycle. The whole problem is then reduced to analyzing those cycles and determining when their orientation constraints can hold simultaneously.

Step 2: The Square Case Gives a Rational Grid

If \(c=k^2\), then \(s_2=1/k\) is rational. In that case all breakpoints lie on the common grid with denominator

$D=\operatorname{lcm}(a,b,k).$

Write

$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$

Each phase is partitioned into the \(D\) cells

$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$

For phase \(\phi\), the map is explicit:

$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$

The first branch is a reflection and contributes flip bit \(1\); the second branch is a translation and contributes flip bit \(0\). Thus the square case produces a finite automaton with exactly \(3D\) states.

Step 3: The Non-square Case Lives in a Quadratic Field

If \(c\) is not a square, then \(1/\sqrt{c}\) is irrational, so a simple rational grid no longer exists. The implementations instead represent every breakpoint exactly in the form

$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$

This works because the three step sizes are

$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c},$

so every backward image remains in the same lattice generated by \(1/(ab)\) and \(\sqrt{c}/c\).

For each phase we begin with the seed set \(\{0,s_\phi\}\). If \(y\) is already a breakpoint in phase \(\phi\), then its preimages under the previous phase are

$x=y+s_{\phi-1}\qquad\text{when } y<1-s_{\phi-1},$

and

$x=1-y\qquad\text{when } y>1-s_{\phi-1}.$

Repeating this predecessor closure until no new points appear yields three finite breakpoint sets. They are then sorted exactly by comparing the sign of expressions of the form

$A+B\sqrt{c},$

which avoids floating-point ambiguity. Adjacent breakpoints again define intervals, so the non-square branch also becomes a finite deterministic automaton.

Step 4: Every Cycle Produces a Flip Word

Because phases advance \(0\to1\to2\to0\), every directed cycle has length \(3m\) for some \(m\). Along that cycle the automaton records a binary word

$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\},$

where \(f_i=1\) means that step used the reflecting branch. Group the bits by phase:

$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$

The orientation change over one full three-step round is

$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$

If the total parity of the whole cycle is even, returning to the same place also returns to the same orientation after one geometric lap. If it is odd, one extra lap is needed to restore orientation. Therefore the natural modulus attached to that cycle is

$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$

Step 5: Convert a Cycle into Admissible Residue Classes

Suppose the desired synchronization time has the form

$N=3q+R,\qquad R\in\{0,1,2\}.$

The partial phase offset \(R\) contributes its own correction word. For each \(i\), define

$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$

Then the corrected round word is

$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$

A residue class is valid exactly when this corrected word is a cyclic rotation of \(w\) and the initial orientation parity is also consistent. The implementations find all such rotations with Knuth-Morris-Pratt on the doubled word \(w\,w\), then verify the start-parity condition with prefix xors. The result of one cycle is therefore a finite set

$N\equiv r \pmod{P},\qquad r\in R_{\text{cycle}}.$

Step 6: Merge All Cycle Constraints with CRT

Different connected components of the state graph impose independent congruence conditions on the same unknown \(N\). If one cycle allows residues \(R_1\) modulo \(P_1\) and another allows residues \(R_2\) modulo \(P_2\), then every compatible pair is merged by the generalized Chinese Remainder Theorem.

After processing all cycles, the surviving residue classes describe every synchronized time. The least positive one is exactly \(T(a,b,c)\).

Worked Example: The Square Triple \((10,14,16)\)

Here \(c=16=4^2\), so the rational-grid branch applies. We obtain

$D=\operatorname{lcm}(10,14,4)=140,$

hence

$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$

So each phase has \(140\) cells and the automaton has \(420\) states in total. In phase \(0\), cells \(0\) through \(13\) reflect to cells \(139\) down to \(126\), while cells \(14\) through \(139\) translate to cells \(0\) through \(125\). The same rule is repeated with thresholds \(10\) and \(35\) in the next two phases.

Decomposing that automaton into directed cycles, extracting the admissible congruence classes from each cycle, and merging them with CRT yields the least positive synchronization time

$T(10,14,16)=506,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan. First they distinguish the square and non-square cases. In the square case they build the \(3D\)-state automaton directly from explicit cell formulas. In the non-square case they build exact breakpoint sets in quadratic-field coordinates, sort them with exact comparisons, and then form the corresponding interval automaton.

Next the implementation walks through every connected component, extracts its directed cycle, records the flip word, and converts that word into allowed residue classes by a combination of prefix-xor bookkeeping, rotation matching, and generalized CRT. The smallest positive residue surviving all cycle merges is the answer for that triple. Finally the outer loops sum these values for all \(9\le a<b<c\le n\), using arbitrary-precision integer arithmetic for the final total. The Python implementation delegates the heavy numerical work to the same compiled core, so all three languages share the same underlying algorithm.

Complexity Analysis

For one triple, let \(m\) be the number of intervals per phase after discretization. The resulting automaton has \(3m\) states. Building the square-case automaton is \(O(m)\). In the non-square case, predecessor closure and exact sorting dominate, giving roughly \(O(m \log m)\) work once the breakpoint set is known. Cycle extraction is linear in the number of states, and the word analysis for a cycle of length \(\ell\) is \(O(\ell)\) because both prefix-xor processing and KMP are linear.

The CRT stage depends on how many residue classes survive after each merge; in practice those sets stay modest, so the dominant cost is constructing and scanning the automaton. Memory usage is \(O(m)\) per triple. The overall computation for the final sum is the sum of these costs over all \(\binom{n-8}{3}\) triples, and the outer parameter loop is parallelized in the compiled implementations.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=566
2. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
3. Knuth-Morris-Pratt algorithm: Wikipedia - Knuth-Morris-Pratt algorithm
4. Quadratic field: Wikipedia - Quadratic field
5. Symbolic dynamics: Wikipedia - Symbolic dynamics