Detailed mathematical approach

Problem Summary

Let \(T_n=\dfrac{n(n+1)}{2}\). On a clock with \(s\) positions, taking successive steps of lengths \(1,2,3,\dots\) lands on the residues \(T_n \pmod{s}\). Define

$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$

The whole problem is driven by these forced residue sets. For each modulus \(s\), the triangular walk determines the mandatory positions \(R_s\); larger clock sequences are obtained by adjoining extra positions that the walk never visits. The target quantity is the primitive cumulative count \(C(10000)\) modulo \(1111211113\).

A direct search over all moduli and all candidate sequences would be wasteful. The implementations instead derive an explicit multiplicative formula for \(U(s)\), enumerate only the moduli with \(U(s)\le n\), and then assemble the final count through binomial contributions and Möbius inversion.

Mathematical Approach

The solution has two genuinely different parts. First, determine how many triangular residues each modulus has. Second, convert that arithmetic information into a count of primitive clock sequences.

The Residue Set Forced by the Triangular Walk

Fix a modulus \(s\). The set \(R_s\) is forced: every admissible sequence attached to this modulus must contain all residues reached by the triangular walk. If the final sequence has size \(p\), then exactly \(p-U(s)\) additional residues must be chosen from the \(s-U(s)\) positions outside \(R_s\). Therefore a single modulus contributes

$\binom{s-U(s)}{p-U(s)}$

to the number of sequences of exact size \(p\). Summing over all moduli with \(U(s)\le p\) gives the exact-size count

$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$

The implementations then prefix-sum these exact counts:

$A(n)=\sum_{p=1}^{n} B(p).$

What the problem asks for is the primitive version, extracted at the end by Möbius inversion:

$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$

This is the place where repeated copies of a shorter clock sequence are removed.

Odd Prime Powers Become a Square-Residue Problem

The key identity is

$8T_n+1=(2n+1)^2.$

For an odd prime power \(p^e\), multiplication by \(8\) and addition of \(1\) are bijections modulo \(p^e\). So a residue \(x\) is triangular modulo \(p^e\) exactly when \(8x+1\) is a square modulo \(p^e\). Counting triangular residues is therefore the same as counting square residues.

Every nonzero square modulo \(p^e\) has even \(p\)-adic valuation \(2t\). After factoring out \(p^{2t}\), the remaining unit must be a square modulo \(p^{e-2t}\). For odd \(p\), exactly half of the units modulo \(p^m\) are squares, so the contribution of valuation \(2t\) is

$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$

Including the zero residue gives

$U(p^e)=1+\sum_{t=0}^{\lfloor (e-1)/2\rfloor}\frac{p^{e-2t}-p^{e-2t-1}}{2}\qquad(p \text{ odd}).$

From this one gets the prime-power rules used by the implementations:

$U(p)=\frac{p+1}{2},$

$U(p^e)=p\,U(p^{e-1})-\begin{cases} p-1, & e \text{ even},\\[4pt] \dfrac{p-1}{2}, & e \text{ odd}, \end{cases} \qquad (p \text{ odd},\ e\ge 2),$

together with the equivalent closed form

$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd}).$

Powers of Two Cover Every Residue

The \(2\)-power case is different. Here the triangular walk is actually surjective: \(U(2^e)=2^e\). A clean proof is to look at the first \(2^e\) triangular numbers. If \(0\le a<b<2^e\) and \(T_a\equiv T_b \pmod{2^e}\), then

$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$

is divisible by \(2^e\), so \((b-a)(a+b+1)\) is divisible by \(2^{e+1}\). But the two factors have opposite parity, and both are strictly smaller than \(2^{e+1}\). The only way their product can contain \(2^{e+1}\) is the trivial case \(a=b\), which is impossible. Hence \(T_0,T_1,\dots,T_{2^e-1}\) are distinct modulo \(2^e\), so every residue class occurs exactly once.

Multiplicativity Across Coprime Moduli

If \(a\) and \(b\) are coprime, the Chinese remainder theorem identifies a residue modulo \(ab\) with one residue modulo \(a\) and one residue modulo \(b\). On odd prime-power factors, triangular residues are precisely the affine images of square residues; on the \(2\)-part, every residue is allowed. So the condition of being triangular splits independently across coprime factors, which implies

$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$

Therefore, for a factorization

$s=\prod_i p_i^{e_i},$

we have the multiplicative formula

$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$

This is the number-theoretic core of the entire algorithm: once prime powers are understood, all composite moduli follow immediately.

From \(U(s)\) to the Primitive Count

For a known state \((s,U(s))\), write

$f=s-U(s).$

The available extra positions are exactly these \(f\) untouched residues, so the modulus contributes the binomial row

$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$

to the exact sizes \(U(s),U(s)+1,\dots\). After all moduli have been processed, a prefix sum turns \(B\) into \(A\), and Möbius inversion turns \(A\) into the primitive count \(C\).

Worked Example: \(n=4\)

The moduli with \(U(s)\le 4\) are

$s\in\{1,2,3,4,5,6,7,9\}.$

Their triangular-residue counts are

$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$

Two samples explain where these numbers come from. First, modulo \(5\),

$R_5=\{0,1,3\},$

so \(U(5)=3\). Second, modulo \(9\), the prime-power recurrence gives

$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$

For \(s=5\), there are \(5-3=2\) untouched residues, so this modulus contributes

$\binom{2}{0}=1$

to size \(3\), and

$\binom{2}{1}=2$

to size \(4\). Summing all moduli yields

$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$

hence

$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$

Now apply Möbius inversion:

$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$

This is exactly one of the sanity checks used by the solution.

How the Code Works

The C++, Python, and Java implementations all follow the same arithmetic pipeline. The differences are mostly in engineering details, not in the underlying mathematics.

Enumerating Only Relevant States

The implementations first build the prime table needed for multiplicative state generation and the Möbius table needed for the final inversion. They then enumerate states of the form \((s,U(s))\), but only when \(U(s)\le n\), because larger values can never contribute to \(C(n)\).

Powers of \(2\) are the natural starting states since \(U(2^e)=2^e\) is immediate. From a current state with value \(u=U(s)\), a new odd prime \(p\) is worth trying only if its smallest possible factor satisfies

$U(p)=\frac{p+1}{2}\le \frac{n}{u},$

that is,

$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$

Higher powers \(p^e\) are extended as long as the new product \(u\,U(p^e)\) stays within the bound. Because odd primes are appended in increasing order, every admissible factorization is generated exactly once.

Accumulating the Exact-Size Contributions

For each state, the number of free residues is \(f=s-U(s)\). That state contributes a whole run of binomial coefficients to the exact-size table. Consecutive terms are updated by

$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1},$

performed modulo \(1111211113\). Since the modulus is prime, the needed inverses of \(1,2,\dots,n+1\) exist and are precomputed once. After all states have contributed, the exact-size array is prefix-summed into the cumulative array \(A\).

Final Primitive Extraction and Checks

The last stage evaluates

$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$

The C++ and Java implementations split the expensive state-accumulation work across several workers; the Python implementation performs the same arithmetic sequentially. The solution strategy is also sanity-checked on small cases: the triangular-residue formula matches direct enumeration on small moduli, and the counts \(C(3)=3\), \(C(4)=7\), and \(C(10)=561\) agree with the derived formulas.

Complexity Analysis

Let \(S(n)\) be the number of enumerated states \((s,U(s))\) with \(U(s)\le n\). Building the prime sieve up to \(2n\) and the Möbius array up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory.

State generation itself costs \(O(S(n))\). A state \((s,u)\) contributes

$1+\min(s-u,n-u)$

binomial updates, so the total running time is

$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right).$

The memory usage is \(O(n+S(n))\). For \(n=10000\), the accumulation phase dominates, which is why the threaded implementations parallelize it.

Footnotes and References

1. Problem page: Project Euler 908
2. Triangular numbers: Wikipedia - Triangular number
3. Quadratic residues: Wikipedia - Quadratic residue
4. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
5. Möbius inversion: Wikipedia - Möbius inversion formula