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.
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.
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.
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}).$$
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.
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.
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\).
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.
The C++, Python, and Java implementations all follow the same arithmetic pipeline. The differences are mostly in engineering details, not in the underlying mathematics.
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.
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\).
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.
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.
Sei \(T_n=\dfrac{n(n+1)}{2}\). Auf einer Uhr mit \(s\) Positionen landet man bei Schritten der Längen \(1,2,3,\dots\) genau auf den Resten \(T_n \pmod{s}\). Wir definieren
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
Die gesamte Aufgabe wird durch diese erzwungenen Restmengen bestimmt. Für jedes Modul \(s\) legt der Dreieckszahlgang die Pflichtpositionen \(R_s\) fest; größere Uhrfolgen entstehen dadurch, dass man zusätzliche nie besuchte Positionen hinzunimmt. Gesucht ist die primitive kumulative Anzahl \(C(10000)\) modulo \(1111211113\).
Eine naive Suche über alle Moduli und alle Kandidatenfolgen wäre unnötig teuer. Stattdessen leiten die Implementierungen eine explizite multiplikative Formel für \(U(s)\) her, erzeugen nur die Moduli mit \(U(s)\le n\) und setzen die Endsumme anschließend aus Binomialbeiträgen und Möbius-Inversion zusammen.
Die Lösung hat zwei klar getrennte Teile. Zuerst muss man verstehen, wie viele Dreieckszahlreste ein Modul überhaupt besitzt. Danach wird diese arithmetische Information in eine Zählung primitiver Uhrfolgen übersetzt.
Fixiere ein Modul \(s\). Die Menge \(R_s\) ist vollständig vorgegeben: Jede zulässige Folge zu diesem Modul muss alle vom Dreieckszahlgang erreichten Reste enthalten. Hat die Endfolge Größe \(p\), dann müssen also genau \(p-U(s)\) weitere Reste aus den \(s-U(s)\) Positionen außerhalb von \(R_s\) gewählt werden. Ein einzelnes Modul trägt daher
$$\binom{s-U(s)}{p-U(s)}$$
zur Anzahl der Folgen exakter Größe \(p\) bei. Summiert man über alle Moduli mit \(U(s)\le p\), so erhält man
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$$
Die Implementierungen verwenden anschließend die kumulative Version
$$A(n)=\sum_{p=1}^{n} B(p).$$
Die gesuchte primitive Größe entsteht erst im letzten Schritt durch Möbius-Inversion:
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Genau hier werden Folgen entfernt, die lediglich aus der Wiederholung einer kürzeren Uhrfolge bestehen.
Die entscheidende Identität lautet
$$8T_n+1=(2n+1)^2.$$
Für eine ungerade Primzahlpotenz \(p^e\) sind Multiplikation mit \(8\) und Addition von \(1\) modulo \(p^e\) bijektiv. Ein Rest \(x\) ist also genau dann triangular modulo \(p^e\), wenn \(8x+1\) ein Quadrat modulo \(p^e\) ist. Dreieckszahlreste zu zählen ist deshalb dasselbe wie Quadratrestmengen zu zählen.
Jedes von \(0\) verschiedene Quadrat modulo \(p^e\) hat eine gerade \(p\)-adische Bewertung \(2t\). Nach dem Ausklammern von \(p^{2t}\) muss der verbleibende Einheitenteil ein Quadrat modulo \(p^{e-2t}\) sein. Für ungerades \(p\) ist genau die Hälfte der Einheiten modulo \(p^m\) quadratisch, also liefert die Bewertung \(2t\) den Beitrag
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$$
Mit dem Nullrest ergibt sich
$$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}).$$
Daraus folgen die in den Implementierungen benutzten Regeln
$$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),$$
sowie die äquivalente geschlossene Form
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd}).$$
Der Fall \(2^e\) verhält sich anders. Hier ist der Dreieckszahlgang sogar surjektiv: \(U(2^e)=2^e\). Betrachte dazu die ersten \(2^e\) Dreieckszahlen. Wenn \(0\le a<b<2^e\) und \(T_a\equiv T_b \pmod{2^e}\), dann ist
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
durch \(2^e\) teilbar, also \((b-a)(a+b+1)\) durch \(2^{e+1}\). Die beiden Faktoren haben jedoch entgegengesetzte Parität und sind beide strikt kleiner als \(2^{e+1}\). Das geht nur im trivialen Fall \(a=b\), der ausgeschlossen ist. Also sind \(T_0,T_1,\dots,T_{2^e-1}\) paarweise verschieden modulo \(2^e\), und jede Restklasse tritt genau einmal auf.
Sind \(a\) und \(b\) teilerfremd, so identifiziert der chinesische Restsatz einen Rest modulo \(ab\) mit einem Rest modulo \(a\) und einem Rest modulo \(b\). Auf ungeraden Primzahlpotenzen sind die triangularen Reste genau affine Bilder von Quadratrestmengen; auf dem Zweieranteil ist jeder Rest erlaubt. Damit zerfällt die Triangular-Bedingung unabhängig über teilerfremde Faktoren, also gilt
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$$
Für eine Zerlegung
$$s=\prod_i p_i^{e_i}$$
folgt daher die multiplikative Formel
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$$
Das ist der arithmetische Kern der ganzen Methode: Sind die Primzahlpotenzen verstanden, dann folgen alle zusammengesetzten Moduli automatisch.
Für einen bekannten Zustand \((s,U(s))\) setzen wir
$$f=s-U(s).$$
Die verfügbaren Zusatzpositionen sind genau diese \(f\) nie besuchten Reste. Das Modul liefert also die Binomialzeile
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$$
zu den Größen \(U(s),U(s)+1,\dots\). Nachdem alle Moduli verarbeitet wurden, macht eine Präfixsumme aus \(B\) die Funktion \(A\), und die Möbius-Inversion macht aus \(A\) die primitive Zählfunktion \(C\).
Die Moduli mit \(U(s)\le 4\) sind
$$s\in\{1,2,3,4,5,6,7,9\}.$$
Die zugehörigen Werte lauten
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$$
Zwei Beispiele zeigen die Herkunft dieser Zahlen. Erstens gilt modulo \(5\)
$$R_5=\{0,1,3\},$$
also \(U(5)=3\). Zweitens liefert die Primzahlpotenzrekurrenz für \(9\)
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$$
Für \(s=5\) gibt es \(5-3=2\) unberührte Reste, also trägt dieses Modul
$$\binom{2}{0}=1$$
zur Größe \(3\) und
$$\binom{2}{1}=2$$
zur Größe \(4\) bei. Über alle Moduli zusammen ergibt das
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
und damit
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$$
Nun folgt die 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.$$
Genau dieser Wert dient als kleiner Konsistenztest für die Lösung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe arithmetische Pipeline. Die Unterschiede liegen fast nur in technischen Details, nicht in der Mathematik.
Zuerst werden die Primzahlliste für die multiplikative Zustandsgenerierung und die Möbius-Tabelle für die finale Inversion aufgebaut. Danach werden Zustände der Form \((s,U(s))\) erzeugt, aber nur dann, wenn \(U(s)\le n\), denn größere Werte können zu \(C(n)\) nichts beitragen.
Die Zweierpotenzen sind die natürlichen Startzustände, weil \(U(2^e)=2^e\) sofort feststeht. Ausgehend von einem Zustand mit Wert \(u=U(s)\) lohnt sich ein neuer ungerader Primfaktor \(p\) nur, wenn sein kleinster möglicher Beitrag
$$U(p)=\frac{p+1}{2}\le \frac{n}{u}$$
erfüllt, also
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
Höhere Potenzen \(p^e\) werden so lange angehängt, wie das neue Produkt \(u\,U(p^e)\) innerhalb der Schranke bleibt. Weil ungerade Primzahlen in aufsteigender Reihenfolge ergänzt werden, entsteht jede zulässige Faktorisierung genau einmal.
Für jeden Zustand ist \(f=s-U(s)\) die Zahl der freien Reste. Dieser Zustand liefert einen ganzen Lauf von Binomialkoeffizienten in die Tabelle der exakten Größen. Aufeinanderfolgende Werte werden über
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1}$$
modulo \(1111211113\) aktualisiert. Da der Modul prim ist, existieren die benötigten Inversen von \(1,2,\dots,n+1\) und werden einmal vorab berechnet. Nach allen Zustandsbeiträgen wird das Exakt-Array per Präfixsumme in das kumulative Array \(A\) verwandelt.
Im letzten Schritt wird
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}$$
ausgewertet. Die C++- und Java-Implementierungen verteilen die teure Zustandsakkumulation auf mehrere Worker, während die Python-Implementierung dieselbe Rechnung sequenziell ausführt. Zusätzlich wird die Strategie an kleinen Fällen geprüft: Die Formel für \(U(s)\) stimmt mit direkter Residuenzählung auf kleinen Moduli überein, und die Werte \(C(3)=3\), \(C(4)=7\) und \(C(10)=561\) passen zur Herleitung.
Sei \(S(n)\) die Zahl der erzeugten Zustände \((s,U(s))\) mit \(U(s)\le n\). Das Primzahlsieb bis \(2n\) und die Möbius-Tabelle bis \(n\) kosten \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher.
Die Zustandsgenerierung selbst kostet \(O(S(n))\). Ein Zustand \((s,u)\) liefert
$$1+\min(s-u,n-u)$$
Binomialupdates, also insgesamt
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right)$$
Zeit. Der Speicherbedarf beträgt \(O(n+S(n))\). Für \(n=10000\) dominiert die Akkumulationsphase, weshalb die nebenläufigen Implementierungen genau diesen Teil parallelisieren.
\(T_n=\dfrac{n(n+1)}{2}\) olsun. \(s\) konumlu bir saat üzerinde uzunlukları \(1,2,3,\dots\) olan adımlar atıldığında ulaşılan yerler tam olarak \(T_n \pmod{s}\) kalıntılarıdır. Şunu tanımlayalım:
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
Tüm problem bu zorunlu kalıntı kümeleri etrafında şekillenir. Her modül \(s\) için üçgensel yürüyüşün mecbur bıraktığı konumlar \(R_s\)'dir; daha büyük saat dizileri ise hiç ziyaret edilmeyen ek konumlar seçilerek oluşur. İstenen nicelik, \(1111211113\) modunda hesaplanan ilkel kümülatif sayı \(C(10000)\)'dir.
Bütün modülleri ve bütün aday dizileri doğrudan taramak gereksiz derecede pahalı olurdu. Bunun yerine uygulamalar önce \(U(s)\) için açık bir çarpımsal formül kurar, yalnızca \(U(s)\le n\) olan modülleri üretir ve son sayımı binom katkıları ile Möbius terslemesi üzerinden toplar.
Çözümün iki ayrı katmanı vardır. Önce her modülün kaç farklı üçgensel kalıntı ürettiğini anlamak gerekir. Sonra bu aritmetik bilgi ilkel saat dizilerinin sayısına dönüştürülür.
Sabit bir \(s\) modülü seçelim. \(R_s\) tamamen zorunlu bir kümedir: bu modüle bağlı her geçerli dizi, üçgensel yürüyüşün gördüğü bütün kalıntıları içermek zorundadır. Son dizinin boyutu \(p\) ise, \(R_s\) dışında kalan \(s-U(s)\) konum arasından tam \(p-U(s)\) tane ek kalıntı seçilmelidir. Dolayısıyla tek bir modülün tam boyut \(p\)'ye katkısı
$$\binom{s-U(s)}{p-U(s)}$$
olur. \(U(s)\le p\) koşulunu sağlayan bütün modüller toplanınca
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}$$
elde edilir. Uygulamalar daha sonra bunun kümülatif hâlini kullanır:
$$A(n)=\sum_{p=1}^{n} B(p).$$
Problemin istediği ilkel nicelik ise en sonda Möbius terslemesi ile çıkarılır:
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Bu adım, daha kısa bir saat dizisinin tekrarından ibaret olan yapıları temizler.
Temel özdeşlik
$$8T_n+1=(2n+1)^2$$
şeklindedir. Tek asal kuvvet \(p^e\) için \(8\) ile çarpma ve \(1\) ekleme işlemleri modulo \(p^e\) bire birdir. Bu yüzden bir \(x\) kalıntısı ancak ve ancak \(8x+1\) modulo \(p^e\)'de kare ise üçgensel kalıntıdır. Yani üçgensel kalıntıları saymak, kare kalıntıları saymakla aynıdır.
Modulo \(p^e\)'de sıfır olmayan her kare, çift \(p\)-adik değerleme \(2t\) taşır. \(p^{2t}\) çarpanı dışarı alınca kalan birim kısmın modulo \(p^{e-2t}\)'de kare olması gerekir. Tek \(p\) için modulo \(p^m\)'deki birimlerin tam yarısı karedir; dolayısıyla değerleme \(2t\)'nin katkısı
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}$$
olur. Sıfır kalıntısını da ekleyince
$$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})$$
bulunur. Buradan uygulamaların kullandığı asal-kuvvet kuralları çıkar:
$$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),$$
ayrıca eşdeğer kapalı form da vardır:
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd}).$$
\(2^e\) durumu farklı davranır. Burada üçgensel yürüyüş gerçekten sürjektiftir: \(U(2^e)=2^e\). Bunun kısa kanıtı şudur. Eğer \(0\le a<b<2^e\) ve \(T_a\equiv T_b \pmod{2^e}\) ise
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
\(2^e\)'ye bölünür, dolayısıyla \((b-a)(a+b+1)\) sayısı \(2^{e+1}\)'e bölünür. Ama bu iki çarpan zıt paritye sahiptir ve ikisi de \(2^{e+1}\)'den küçüktür. Bu durumda çarpımın \(2^{e+1}\) içermesi ancak anlamsız durum \(a=b\) ile mümkündür. O hâlde \(T_0,T_1,\dots,T_{2^e-1}\) modulo \(2^e\) birbirinden farklıdır; yani her kalıntı sınıfı tam bir kez görülür.
\(a\) ve \(b\) aralarında asal ise, Çin kalan teoremi modulo \(ab\) bir kalıntıyı modulo \(a\) ve modulo \(b\) kalıntılarının bir çiftiyle özdeşleştirir. Tek asal kuvvet bileşenlerinde üçgensel kalıntılar, kare kalıntılarının afin görüntüleridir; \(2\)-kısmında ise bütün kalıntılar serbesttir. Dolayısıyla üçgensel olma koşulu aralarında asal bileşenler boyunca bağımsız ayrışır ve
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1)$$
sonucu çıkar. Böylece
$$s=\prod_i p_i^{e_i}$$
çarpanlaması için
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right)$$
yazılır. Algoritmanın sayı kuramsal omurgası tam olarak budur.
Bir \((s,U(s))\) durumu biliniyorsa
$$f=s-U(s)$$
tanımlanır. Eklenebilecek boş konumlar tam olarak bu \(f\) tane kalıntıdır. Bu nedenle modül,
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$$
binom satırını \(U(s),U(s)+1,\dots\) boyutlarına katkı olarak verir. Bütün modüller işlendiğinde önce \(B\) dizisi prefix toplamıyla \(A\)'ya dönüşür, sonra Möbius terslemesi \(A\)'dan ilkel sayım \(C\)'yi üretir.
\(U(s)\le 4\) olan modüller
$$s\in\{1,2,3,4,5,6,7,9\}$$
kümesidir. Bunların değerleri
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4$$
şeklindedir. Bu sayıların nereden geldiğini iki örnek gösterir. Birincisi, modulo \(5\) için
$$R_5=\{0,1,3\}$$
olduğundan \(U(5)=3\). İkincisi, modulo \(9\) için asal-kuvvet bağıntısı
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4$$
sonucunu verir. \(s=5\) için \(5-3=2\) tane boş kalıntı olduğundan bu modül, boyut \(3\)'e
$$\binom{2}{0}=1$$
ve boyut \(4\)'e
$$\binom{2}{1}=2$$
katkısı yapar. Tüm modüller toplandığında
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
dolayısıyla
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11$$
elde edilir. Son adım Möbius terslemesidir:
$$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$$
Bu, çözümün küçük doğrulama noktalarından biridir.
C++, Python ve Java uygulamaları aynı aritmetik hattı izler. Aralarındaki farkların çoğu mühendislik ayrıntılarıdır; matematik aynıdır.
Önce çarpımsal durum üretimi için asal tablosu, son tersleme için de Möbius tablosu hazırlanır. Ardından yalnızca \(U(s)\le n\) olan \((s,U(s))\) durumları üretilir; çünkü daha büyük değerler \(C(n)\)'ye katkı veremez.
\(2\)'nin kuvvetleri doğal başlangıç durumlarıdır, çünkü \(U(2^e)=2^e\) doğrudan bilinir. Değeri \(u=U(s)\) olan bir mevcut durumdan hareketle yeni bir tek asal \(p\) ancak
$$U(p)=\frac{p+1}{2}\le \frac{n}{u}$$
ise anlamlıdır; yani
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
Daha yüksek \(p^e\) kuvvetleri de yeni çarpım \(u\,U(p^e)\) sınırın altında kaldığı sürece denenir. Tek asallar artan sırayla eklendiği için her geçerli çarpanlama tam bir kez üretilir.
Her durumda serbest kalıntı sayısı \(f=s-U(s)\)'dir. O durum, tam boyut tablosuna bir dizi binom katsayısı ekler. Ardışık değerler
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1}$$
bağıntısıyla \(1111211113\) modunda güncellenir. Modül asal olduğu için \(1,2,\dots,n+1\) sayılarının tersleri vardır ve bunlar bir kez önceden hesaplanır. Bütün durumlar işlendiğinde tam boyut dizisi prefix toplamıyla kümülatif \(A\) dizisine dönüştürülür.
Son aşamada
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}$$
hesaplanır. C++ ve Java uygulamaları pahalı durum-birikim aşamasını birden fazla işçiye böler; Python uygulaması aynı hesabı sıralı olarak yapar. Strateji küçük örneklerde de sınanır: \(U(s)\) formülü küçük modüllerde doğrudan kalıntı sayımıyla uyuşur ve \(C(3)=3\), \(C(4)=7\), \(C(10)=561\) değerleri türetilen formüllerle tutarlıdır.
\(U(s)\le n\) olan üretilmiş \((s,U(s))\) durumlarının sayısına \(S(n)\) diyelim. \(2n\)'ye kadar asal süzgeci ve \(n\)'ye kadar Möbius tablosu \(O(n\log\log n)\) zaman ve \(O(n)\) bellek ister.
Durum üretiminin kendisi \(O(S(n))\) maliyetlidir. Bir \((s,u)\) durumu
$$1+\min(s-u,n-u)$$
adet binom güncellemesi yapar; dolayısıyla toplam süre
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right)$$
olur. Bellek kullanımı \(O(n+S(n))\)'dir. \(n=10000\) için baskın bölüm bu birikim aşamasıdır; paralel sürümler de tam olarak bu kısmı hızlandırır.
Sea \(T_n=\dfrac{n(n+1)}{2}\). En un reloj con \(s\) posiciones, avanzar con pasos de longitudes \(1,2,3,\dots\) lleva exactamente a los residuos \(T_n \pmod{s}\). Definimos
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
Todo el problema gira alrededor de estos conjuntos forzados de residuos. Para cada módulo \(s\), el recorrido triangular fija las posiciones obligatorias \(R_s\); las secuencias de reloj más grandes se obtienen añadiendo posiciones extra que el recorrido nunca toca. La cantidad buscada es el conteo acumulado primitivo \(C(10000)\) módulo \(1111211113\).
Una búsqueda directa sobre todos los módulos y todas las secuencias candidatas sería innecesariamente costosa. Las implementaciones, en cambio, derivan una fórmula multiplicativa explícita para \(U(s)\), enumeran solo los módulos con \(U(s)\le n\) y luego ensamblan la cuenta final mediante contribuciones binomiales e inversión de Möbius.
La solución tiene dos piezas bien diferenciadas. Primero hay que entender cuántos residuos triangulares tiene cada módulo. Después esa información aritmética se traduce en un conteo de secuencias primitivas.
Fijemos un módulo \(s\). El conjunto \(R_s\) está completamente determinado: cualquier secuencia válida asociada a ese módulo debe contener todos los residuos alcanzados por el recorrido triangular. Si la secuencia final tiene tamaño \(p\), entonces hay que elegir exactamente \(p-U(s)\) residuos adicionales entre las \(s-U(s)\) posiciones que quedan fuera de \(R_s\). Por tanto, un solo módulo aporta
$$\binom{s-U(s)}{p-U(s)}$$
al número de secuencias de tamaño exacto \(p\). Sumando sobre todos los módulos con \(U(s)\le p\), obtenemos
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$$
Luego las implementaciones usan la versión acumulada
$$A(n)=\sum_{p=1}^{n} B(p).$$
La cantidad primitiva que pide el problema aparece solo al final, mediante la inversión de Möbius:
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Ese último paso elimina las secuencias que no son nuevas, sino repeticiones de una secuencia de reloj más corta.
La identidad central es
$$8T_n+1=(2n+1)^2.$$
Para una potencia prima impar \(p^e\), multiplicar por \(8\) y sumar \(1\) son transformaciones biyectivas módulo \(p^e\). Así, un residuo \(x\) es triangular módulo \(p^e\) si y solo si \(8x+1\) es un cuadrado módulo \(p^e\). Contar residuos triangulares equivale entonces a contar residuos cuadráticos.
Cada cuadrado no nulo módulo \(p^e\) tiene valoración \(p\)-ádica par \(2t\). Tras extraer \(p^{2t}\), la parte unitaria restante debe ser un cuadrado módulo \(p^{e-2t}\). Para \(p\) impar, exactamente la mitad de las unidades módulo \(p^m\) son cuadrados, de modo que la contribución del nivel \(2t\) es
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$$
Incluyendo el residuo cero se llega a
$$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}).$$
De ahí salen las reglas de potencia prima usadas por las implementaciones:
$$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),$$
junto con la forma cerrada equivalente
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd}).$$
El caso de \(2^e\) es distinto. Aquí el recorrido triangular es sobreyectivo: \(U(2^e)=2^e\). La prueba breve es esta. Si \(0\le a<b<2^e\) y \(T_a\equiv T_b \pmod{2^e}\), entonces
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
es divisible por \(2^e\), por lo que \((b-a)(a+b+1)\) es divisible por \(2^{e+1}\). Pero esos dos factores tienen paridades opuestas y ambos son estrictamente menores que \(2^{e+1}\). La única forma de que su producto contenga \(2^{e+1}\) sería el caso trivial \(a=b\), imposible aquí. Así, \(T_0,T_1,\dots,T_{2^e-1}\) son todos distintos módulo \(2^e\), y por tanto aparecen todas las clases residuales.
Si \(a\) y \(b\) son coprimos, el teorema chino del resto identifica un residuo módulo \(ab\) con un residuo módulo \(a\) y otro módulo \(b\). En los factores de potencia prima impar, los residuos triangulares son imágenes afines de los residuos cuadráticos; en la parte de \(2\), todos los residuos están permitidos. Por eso la condición de ser triangular se separa independientemente sobre factores coprimos, y se obtiene
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$$
En consecuencia, para una factorización
$$s=\prod_i p_i^{e_i},$$
se tiene la fórmula multiplicativa
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$$
Ese es el núcleo aritmético del algoritmo completo: una vez entendidas las potencias primas, los módulos compuestos quedan resueltos automáticamente.
Cuando el estado \((s,U(s))\) ya se conoce, escribimos
$$f=s-U(s).$$
Las posiciones extra disponibles son exactamente esos \(f\) residuos no visitados. Por tanto, el módulo aporta la fila binomial
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$$
a los tamaños \(U(s),U(s)+1,\dots\). Después de procesar todos los módulos, una suma prefija convierte \(B\) en \(A\), y la inversión de Möbius convierte \(A\) en el conteo primitivo \(C\).
Los módulos con \(U(s)\le 4\) son
$$s\in\{1,2,3,4,5,6,7,9\}.$$
Sus valores son
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$$
Dos ejemplos muestran de dónde salen estos números. Primero, módulo \(5\),
$$R_5=\{0,1,3\},$$
de modo que \(U(5)=3\). Segundo, para \(9\), la recurrencia de potencia prima da
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$$
En \(s=5\) quedan \(5-3=2\) residuos libres, así que este módulo aporta
$$\binom{2}{0}=1$$
al tamaño \(3\), y
$$\binom{2}{1}=2$$
al tamaño \(4\). Sumando todos los módulos se obtiene
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
y por tanto
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$$
Ahora aplicamos la inversión de Möbius:
$$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$$
Ese es precisamente uno de los controles pequeños de la solución.
Las implementaciones en C++, Python y Java siguen la misma tubería aritmética. Las diferencias importantes son de ingeniería, no de matemáticas.
Primero se construyen la tabla de primos necesaria para la generación multiplicativa de estados y la tabla de Möbius necesaria para la inversión final. Después se enumeran estados de la forma \((s,U(s))\), pero solo cuando \(U(s)\le n\), porque valores mayores ya no pueden contribuir a \(C(n)\).
Las potencias de \(2\) son el punto de partida natural, ya que \(U(2^e)=2^e\) es inmediato. Desde un estado con valor \(u=U(s)\), un nuevo primo impar \(p\) solo merece la pena si su menor factor posible cumple
$$U(p)=\frac{p+1}{2}\le \frac{n}{u},$$
es decir,
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
Las potencias superiores \(p^e\) se siguen extendiendo mientras el nuevo producto \(u\,U(p^e)\) permanezca dentro del límite. Como los primos impares se añaden en orden creciente, cada factorización admisible se genera exactamente una vez.
Para cada estado, el número de residuos libres es \(f=s-U(s)\). Ese estado aporta una tira completa de coeficientes binomiales a la tabla de tamaños exactos. Los términos consecutivos se actualizan con
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1},$$
todo ello módulo \(1111211113\). Como el módulo es primo, existen los inversos necesarios de \(1,2,\dots,n+1\) y se precalculan una sola vez. Cuando todos los estados han contribuido, la tabla exacta se convierte en la tabla acumulada \(A\) mediante una suma prefija.
La etapa final evalúa
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Las implementaciones de C++ y Java reparten la acumulación costosa de estados entre varios trabajadores; la implementación de Python hace la misma suma de forma secuencial. La estrategia también se verifica en casos pequeños: la fórmula de \(U(s)\) coincide con la enumeración directa de residuos en módulos pequeños, y los valores \(C(3)=3\), \(C(4)=7\) y \(C(10)=561\) concuerdan con la derivación.
Sea \(S(n)\) el número de estados enumerados \((s,U(s))\) con \(U(s)\le n\). Construir la criba de primos hasta \(2n\) y la tabla de Möbius hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria.
La generación de estados cuesta \(O(S(n))\). Un estado \((s,u)\) produce
$$1+\min(s-u,n-u)$$
actualizaciones binomiales, de modo que el tiempo total es
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right).$$
La memoria usada es \(O(n+S(n))\). Para \(n=10000\), la fase dominante es la acumulación, por eso las versiones paralelas se concentran precisamente en esa parte.
设 \(T_n=\dfrac{n(n+1)}{2}\)。在一个有 \(s\) 个刻度的位置系统上，依次走 \(1,2,3,\dots\) 步，落到的正是 \(T_n \pmod{s}\) 这些剩余类。定义
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
整道题的核心就是这些被三角数步进强制出来的剩余类集合。对每个模数 \(s\) 来说，三角步进先固定了必须出现的位置 \(R_s\)；更大的时钟序列则通过补上那些从未被访问过的位置得到。题目真正要求的是原始累计计数 \(C(10000)\) 在模 \(1111211113\) 下的值。
如果直接枚举所有模数、再枚举所有候选序列，代价会非常高。三份实现采取的是另一条路线：先为 \(U(s)\) 推出一个显式的乘法性公式，只枚举满足 \(U(s)\le n\) 的模数状态，然后再用二项式贡献和 Möbius 反演把最终答案一次性拼出来。
这个解法有两个真正不同的层次。第一层是搞清楚每个模数到底有多少个三角数剩余类。第二层是把这些算术信息转成原始时钟序列的计数。
先固定一个模数 \(s\)。集合 \(R_s\) 是完全被问题本身强制出来的：凡是和这个模数相关的合法序列，都必须包含三角步进实际到达过的所有剩余类。如果最终序列大小是 \(p\)，那么除了 \(R_s\) 里的 \(U(s)\) 个位置以外，还必须从外面的 \(s-U(s)\) 个未访问位置中再选出恰好 \(p-U(s)\) 个。因此，单个模数对“大小恰好等于 \(p\)”的序列数贡献为
$$\binom{s-U(s)}{p-U(s)}.$$
对所有满足 \(U(s)\le p\) 的模数求和，就得到精确大小计数
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$$
实现随后对它做前缀求和：
$$A(n)=\sum_{p=1}^{n} B(p).$$
而题目要的原始计数并不是 \(A(n)\)，而是通过 Möbius 反演得到的
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
这一层的含义是：先把所有可能的序列都算进去，再把那些只是更短序列重复若干次得到的结构剔除掉。
最关键的恒等式是
$$8T_n+1=(2n+1)^2.$$
对于奇素数幂 \(p^e\)，模 \(p^e\) 下“乘以 \(8\)”和“再加 \(1\)”都是双射。所以一个剩余类 \(x\) 是三角数剩余类，当且仅当 \(8x+1\) 是模 \(p^e\) 的平方剩余。于是，数三角数剩余类和数平方剩余类完全等价。
模 \(p^e\) 的非零平方剩余都有偶数的 \(p\)-进赋值 \(2t\)。把 \(p^{2t}\) 提出来以后，剩下的单位部分必须是模 \(p^{e-2t}\) 的平方。对奇素数 \(p\) 来说，模 \(p^m\) 的单位中恰好有一半是平方，因此赋值层 \(2t\) 的贡献是
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$$
再把零剩余加进去，就得到
$$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 prime}).$$
从这里可以直接整理出实现中真正使用的素数幂公式：
$$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 prime},\ e\ge 2),$$
以及与之等价的闭式
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd prime}).$$
\(2^e\) 的情况完全不同。在这里三角步进实际上会覆盖全部剩余类，也就是 \(U(2^e)=2^e\)。一个简洁证明如下。若 \(0\le a<b<2^e\) 且 \(T_a\equiv T_b \pmod{2^e}\)，则
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
能被 \(2^e\) 整除，于是 \((b-a)(a+b+1)\) 必须能被 \(2^{e+1}\) 整除。但这两个因子奇偶性相反，而且都严格小于 \(2^{e+1}\)。在这种情况下，它们的乘积不可能含有 \(2^{e+1}\)，除非出现平凡情形 \(a=b\)，这与 \(a<b\) 矛盾。所以 \(T_0,T_1,\dots,T_{2^e-1}\) 模 \(2^e\) 两两不同，于是所有剩余类都恰好出现一次。
如果 \(a\) 和 \(b\) 互素，中国剩余定理把模 \(ab\) 的一个剩余类与模 \(a\) 和模 \(b\) 的一对剩余类对应起来。在奇素数幂部分，三角数剩余类就是平方剩余经过仿射变换后的像；在 \(2\)-幂部分，所有剩余类都允许。因此，“是否为三角数剩余类”这个条件会在互素因子之间独立分解，于是有
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$$
所以当
$$s=\prod_i p_i^{e_i}$$
时，立刻得到乘法公式
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$$
这一步就是整个算法的数论核心：一旦素数幂情况被彻底搞清楚，合数模数就不再是新问题。
一旦某个状态 \((s,U(s))\) 已知，记
$$f=s-U(s).$$
这 \(f\) 个位置就是可以自由补进去的未访问剩余类。因此，该模数会向大小 \(U(s),U(s)+1,\dots\) 贡献一整行二项式系数：
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}.$$
把所有模数的贡献累加以后，先对 \(B\) 做前缀和得到 \(A\)，再对 \(A\) 做 Möbius 反演得到原始计数 \(C\)。
满足 \(U(s)\le 4\) 的模数为
$$s\in\{1,2,3,4,5,6,7,9\}.$$
对应的值是
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$$
其中两个例子最能说明来源。第一，模 \(5\) 时
$$R_5=\{0,1,3\},$$
所以 \(U(5)=3\)。第二，模 \(9\) 时，由素数幂递推式可得
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$$
对于 \(s=5\)，未访问位置有 \(5-3=2\) 个，因此它对大小 \(3\) 的贡献是
$$\binom{2}{0}=1,$$
对大小 \(4\) 的贡献是
$$\binom{2}{1}=2.$$
把所有模数加起来，得到
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
于是
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$$
最后做 Möbius 反演：
$$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$$
这正是实现用来做小规模核对的结果之一。
C++、Python 和 Java 三份实现遵循的是同一条算术流程。差异主要在工程层面，而不在数学层面。
实现首先建立用于乘法性状态生成的素数表，以及用于最终反演的 Möbius 表。随后只枚举满足 \(U(s)\le n\) 的状态 \((s,U(s))\)，因为更大的值根本不可能对 \(C(n)\) 产生贡献。
\(2\) 的幂是天然的起点，因为 \(U(2^e)=2^e\) 立刻可得。若当前状态的值是 \(u=U(s)\)，那么一个新的奇素数 \(p\) 只有在
$$U(p)=\frac{p+1}{2}\le \frac{n}{u}$$
时才值得尝试，也就是
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
更高次幂 \(p^e\) 也会继续扩展，只要新的乘积 \(u\,U(p^e)\) 不超过上界。由于奇素数按递增顺序加入，每个可行分解都会且只会生成一次。
对每个状态来说，自由剩余类的个数是 \(f=s-U(s)\)。该状态会向精确大小表贡献一整段二项式系数。相邻项通过
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1}$$
在模 \(1111211113\) 下递推。由于模数是素数，\(1,2,\dots,n+1\) 的逆元都存在，可以预处理一次后反复使用。所有状态处理完成后，对精确大小表做一次前缀和，就得到累计表 \(A\)。
最后一步计算
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
C++ 和 Java 实现把最重的状态累加阶段分给多个工作线程；Python 实现则按同样的数学顺序串行完成。解法还会在小规模例子上做一致性检查：\(U(s)\) 的公式与小模数上的直接枚举吻合，而 \(C(3)=3\)、\(C(4)=7\)、\(C(10)=561\) 也都与推导结果一致。
记 \(S(n)\) 为满足 \(U(s)\le n\) 的已枚举状态 \((s,U(s))\) 数量。建立到 \(2n\) 的素数筛和到 \(n\) 的 Möbius 表需要 \(O(n\log\log n)\) 时间与 \(O(n)\) 空间。
状态生成本身需要 \(O(S(n))\) 步。一个状态 \((s,u)\) 会产生
$$1+\min(s-u,n-u)$$
次二项式更新，因此总时间为
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right).$$
总空间复杂度是 \(O(n+S(n))\)。对 \(n=10000\) 来说，真正占主导的是累加阶段，所以并行版本重点优化的也是这一部分。
Пусть \(T_n=\dfrac{n(n+1)}{2}\). На часах с \(s\) делениями последовательные шаги длины \(1,2,3,\dots\) попадают ровно в остатки \(T_n \pmod{s}\). Обозначим
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
Вся задача строится вокруг этих принудительных множеств остатков. Для каждого модуля \(s\) треугольный ход фиксирует обязательные позиции \(R_s\); более крупные часовые последовательности получаются добавлением тех позиций, которые ход никогда не посещает. Требуется найти первичный накопленный счет \(C(10000)\) по модулю \(1111211113\).
Прямой перебор всех модулей и всех кандидатных последовательностей был бы слишком дорогим. Реализации идут другим путем: выводят явную мультипликативную формулу для \(U(s)\), перечисляют только модули с \(U(s)\le n\), а затем собирают итог через биномиальные вклады и инверсию Мёбиуса.
У решения есть две разные части. Сначала нужно понять, сколько треугольных остатков дает каждый модуль. Затем эта арифметика превращается в счет первичных часовых последовательностей.
Зафиксируем модуль \(s\). Множество \(R_s\) задано полностью: любая допустимая последовательность, связанная с этим модулем, обязана содержать все остатки, которых достигает треугольный ход. Если итоговый размер равен \(p\), то нужно выбрать ровно \(p-U(s)\) дополнительных остатков из \(s-U(s)\) позиций вне \(R_s\). Поэтому один модуль дает вклад
$$\binom{s-U(s)}{p-U(s)}$$
в число последовательностей точного размера \(p\). Суммирование по всем модулям с условием \(U(s)\le p\) дает
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$$
Далее реализации используют накопленную функцию
$$A(n)=\sum_{p=1}^{n} B(p).$$
А уже искомая первичная величина извлекается в самом конце через инверсию Мёбиуса:
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Именно этот шаг вычитает структуры, которые являются просто повторением более короткой часовой последовательности.
Ключевое тождество имеет вид
$$8T_n+1=(2n+1)^2.$$
Для нечетной простой степени \(p^e\) умножение на \(8\) и сдвиг на \(1\) по модулю \(p^e\) являются биекциями. Поэтому остаток \(x\) является треугольным по модулю \(p^e\) тогда и только тогда, когда \(8x+1\) является квадратом по модулю \(p^e\). Значит, подсчет треугольных остатков полностью сводится к подсчету квадратичных вычетов.
Каждый ненулевой квадрат по модулю \(p^e\) имеет четную \(p\)-адическую оценку \(2t\). После вынесения множителя \(p^{2t}\) оставшаяся единичная часть должна быть квадратом по модулю \(p^{e-2t}\). Для нечетного \(p\) ровно половина единиц по модулю \(p^m\) являются квадратами, так что вклад уровня \(2t\) равен
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$$
С учетом нулевого остатка получаем
$$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 prime}).$$
Отсюда выводятся формулы для простых степеней, которые и используют реализации:
$$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 prime},\ e\ge 2),$$
а также эквивалентная закрытая форма
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd prime}).$$
Случай \(2^e\) устроен иначе. Здесь треугольный ход сюръективен: \(U(2^e)=2^e\). Доказательство короткое. Если \(0\le a<b<2^e\) и \(T_a\equiv T_b \pmod{2^e}\), то
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
делится на \(2^e\), а значит \((b-a)(a+b+1)\) делится на \(2^{e+1}\). Но эти два множителя имеют разную четность и оба строго меньше \(2^{e+1}\). Их произведение не может содержать \(2^{e+1}\), кроме тривиального случая \(a=b\), который исключен. Следовательно, \(T_0,T_1,\dots,T_{2^e-1}\) попарно различны по модулю \(2^e\), то есть каждая остаточная класс появляется ровно один раз.
Если \(a\) и \(b\) взаимно просты, китайская теорема об остатках отождествляет остаток по модулю \(ab\) с парой остатков по модулям \(a\) и \(b\). На нечетных простых степенях треугольные остатки являются аффинными образами квадратичных вычетов; на \(2\)-части допустим любой остаток. Поэтому условие треугольности раскладывается независимо по взаимно простым множителям, и получается
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$$
Значит, для разложения
$$s=\prod_i p_i^{e_i}$$
имеем мультипликативную формулу
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$$
Это и есть главный числовой каркас алгоритма: поняв простые степени, мы автоматически понимаем и все составные модули.
Для известного состояния \((s,U(s))\) положим
$$f=s-U(s).$$
Именно эти \(f\) остатков являются свободными позициями, которые можно добавить. Поэтому модуль дает в точные размеры биномиальную строку
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$$
для размеров \(U(s),U(s)+1,\dots\). После обработки всех модулей префиксная сумма превращает \(B\) в \(A\), а инверсия Мёбиуса превращает \(A\) в первичный счет \(C\).
Модули с \(U(s)\le 4\) таковы:
$$s\in\{1,2,3,4,5,6,7,9\}.$$
Соответствующие значения равны
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$$
Два примера показывают источник этих чисел. Во-первых, по модулю \(5\)
$$R_5=\{0,1,3\},$$
поэтому \(U(5)=3\). Во-вторых, для \(9\) рекуррентная формула по простой степени дает
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$$
Для \(s=5\) свободных остатков \(5-3=2\), поэтому этот модуль вносит
$$\binom{2}{0}=1$$
в размер \(3\), и
$$\binom{2}{1}=2$$
в размер \(4\). После суммирования по всем модулям получаем
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
следовательно,
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$$
Теперь применяем инверсию Мёбиуса:
$$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$$
Именно это значение служит одним из малых тестов корректности.
Реализации на C++, Python и Java следуют одной и той же арифметической схеме. Различия между ними в основном инженерные, а не математические.
Сначала строится таблица простых чисел для мультипликативного перечисления состояний и таблица Мёбиуса для финальной инверсии. Затем перечисляются состояния вида \((s,U(s))\), но только при \(U(s)\le n\), потому что большие значения уже не могут дать вклад в \(C(n)\).
Степени двойки являются естественными начальными состояниями, поскольку \(U(2^e)=2^e\) известно сразу. Если текущее значение равно \(u=U(s)\), то новый нечетный простой множитель \(p\) имеет смысл пробовать лишь при условии
$$U(p)=\frac{p+1}{2}\le \frac{n}{u},$$
то есть
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
Более высокие степени \(p^e\) продолжают добавляться, пока новое произведение \(u\,U(p^e)\) не выходит за пределы ограничения. Поскольку нечетные простые присоединяются в порядке возрастания, каждая допустимая факторизация порождается ровно один раз.
Для каждого состояния число свободных остатков равно \(f=s-U(s)\). Это состояние добавляет в таблицу точных размеров целую последовательность биномиальных коэффициентов. Соседние члены обновляются по формуле
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1},$$
выполняемой по модулю \(1111211113\). Так как модуль прост, все необходимые обратные к \(1,2,\dots,n+1\) существуют и заранее вычисляются один раз. После вкладов всех состояний массив точных размеров превращается префиксной суммой в накопленный массив \(A\).
На последнем шаге вычисляется
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
Реализации на C++ и Java распараллеливают дорогой этап накопления состояний на несколько рабочих потоков; реализация на Python выполняет ту же сумму последовательно. Стратегия также проверяется на малых примерах: формула для \(U(s)\) совпадает с прямым перечислением остатков на небольших модулях, а значения \(C(3)=3\), \(C(4)=7\) и \(C(10)=561\) соответствуют выведенным формулам.
Обозначим через \(S(n)\) число перечисленных состояний \((s,U(s))\), для которых \(U(s)\le n\). Построение решета простых чисел до \(2n\) и таблицы Мёбиуса до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти.
Само перечисление состояний стоит \(O(S(n))\). Одно состояние \((s,u)\) дает
$$1+\min(s-u,n-u)$$
биномиальных обновлений, поэтому полное время работы равно
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right).$$
Память составляет \(O(n+S(n))\). При \(n=10000\) доминирует именно стадия накопления, поэтому параллельные реализации ускоряют прежде всего ее.
لتكن \(T_n=\dfrac{n(n+1)}{2}\). على ساعة فيها \(s\) مواضع، فإن السير بخطوات أطوالها \(1,2,3,\dots\) يصل بالضبط إلى البواقي \(T_n \pmod{s}\). نعرّف
$$R_s=\left\{T_n \bmod s : n \ge 0\right\}, \qquad U(s)=|R_s|.$$
جوهر المسألة كلها هو هذه المجموعات القسرية من البواقي. فلكل معيار \(s\) يفرض المسار المثلثي مجموعة المواضع التي لا بد من وجودها وهي \(R_s\)، ثم تُبنى التسلسلات الأكبر بإضافة مواضع أخرى لم يزرها المسار أصلاً. الكمية المطلوبة هي العد التراكمي الأولي \(C(10000)\) بترديد \(1111211113\).
التعداد المباشر لكل المعايير وكل التسلسلات المرشحة سيكون مكلفاً جداً. لذلك تستخرج التطبيقات أولاً صيغة ضربية صريحة لـ \(U(s)\)، ثم تعد فقط المعايير التي تحقق \(U(s)\le n\)، وبعد ذلك تجمع الجواب النهائي عبر مساهمات ثنائية الحدين وعكس Möbius.
يتألف الحل من مرحلتين مختلفتين فعلاً. الأولى هي فهم عدد البواقي المثلثية لكل معيار. والثانية هي تحويل هذه المعلومة العددية إلى عد للتسلسلات الأولية على الساعة.
لنثبت معياراً \(s\). إن المجموعة \(R_s\) محددة بالكامل: فأي تسلسل صالح مرتبط بهذا المعيار يجب أن يحتوي على كل البواقي التي يصل إليها المسار المثلثي. وإذا كان حجم التسلسل النهائي هو \(p\)، فيجب اختيار \(p-U(s)\) بواقي إضافية بالضبط من بين \(s-U(s)\) مواضع خارج \(R_s\). لذلك فإن مساهمة معيار واحد في عدد التسلسلات ذات الحجم الدقيق \(p\) هي
$$\binom{s-U(s)}{p-U(s)}.$$
وبالجمع على جميع المعايير التي تحقق \(U(s)\le p\) نحصل على
$$B(p)=\sum_{s:\,U(s)\le p}\binom{s-U(s)}{p-U(s)}.$$
ثم تستخدم التطبيقات النسخة التراكمية
$$A(n)=\sum_{p=1}^{n} B(p).$$
أما الكمية الأولية المطلوبة فيستخرجها الحل في النهاية بواسطة عكس Möbius:
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
وهذه هي الخطوة التي تزيل التسلسلات الناتجة فقط عن تكرار تسلسل ساعة أقصر.
الهوية المفتاحية هي
$$8T_n+1=(2n+1)^2.$$
بالنسبة إلى قوة أولية فردية \(p^e\)، فإن الضرب في \(8\) ثم الإزاحة بمقدار \(1\) عمليتان تقابليتان modulo \(p^e\). لذلك يكون الباقي \(x\) مثلثياً modulo \(p^e\) إذا وفقط إذا كان \(8x+1\) مربعاً modulo \(p^e\). وهكذا يصبح عد البواقي المثلثية مساوياً تماماً لعد البواقي التربيعية.
كل مربع غير صفري modulo \(p^e\) يملك تقييماً \(p\)-أدياً زوجياً من الشكل \(2t\). وبعد استخراج العامل \(p^{2t}\)، يجب أن يكون الجزء الوحدي الباقي مربعاً modulo \(p^{e-2t}\). وعندما يكون \(p\) فردياً، فإن نصف الوحدات تماماً modulo \(p^m\) تكون مربعات، لذا تكون مساهمة المستوى \(2t\) هي
$$\frac{p^{e-2t}-p^{e-2t-1}}{2}.$$
وبإضافة الباقي الصفري نحصل على
$$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 prime}).$$
ومن هذا تنبثق قواعد القوى الأولية التي تعتمدها التطبيقات:
$$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 prime},\ e\ge 2),$$
ومعها الصيغة المغلقة المكافئة
$$U(p^e)=\left\lfloor\frac{p^{e+1}}{2p+2}+1\right\rfloor \qquad (p \text{ odd prime}).$$
حالة \(2^e\) مختلفة تماماً. هنا يكون المسار المثلثي شاملاً لكل البواقي، أي \(U(2^e)=2^e\). والدليل القصير هو الآتي. إذا كان \(0\le a<b<2^e\) و\(T_a\equiv T_b \pmod{2^e}\)، فإن
$$T_b-T_a=\frac{(b-a)(a+b+1)}{2}$$
يقبل القسمة على \(2^e\)، ومن ثم يجب أن يكون \((b-a)(a+b+1)\) قابلاً للقسمة على \(2^{e+1}\). لكن العاملين لهما فردية متعاكسة، وكلاهما أصغر تماماً من \(2^{e+1}\). لذا لا يمكن أن يحتوي حاصل ضربهما على \(2^{e+1}\) إلا في الحالة التافهة \(a=b\)، وهي مرفوضة. إذن فإن \(T_0,T_1,\dots,T_{2^e-1}\) متمايزة جميعاً modulo \(2^e\)، وبذلك يظهر كل صنف باقٍ مرة واحدة بالضبط.
إذا كان \(a\) و\(b\) متباينين أولياً، فإن مبرهنة الباقي الصيني تعرّف الباقي modulo \(ab\) على أنه زوج من بواقٍ modulo \(a\) وmodulo \(b\). وعلى أجزاء القوى الأولية الفردية تكون البواقي المثلثية صوراً خطية-إزاحية للبواقي التربيعية، أما على جزء \(2\) فكل البواقي مسموحة. لذلك ينفصل شرط كون الباقي مثلثياً بصورة مستقلة على العوامل المتباينة أولياً، ومن ثم
$$U(ab)=U(a)U(b)\qquad(\gcd(a,b)=1).$$
وبالتالي إذا كان
$$s=\prod_i p_i^{e_i},$$
فإننا نحصل على الصيغة الضربية
$$U(s)=\prod_i U\!\left(p_i^{e_i}\right).$$
وهذا هو القلب العددي للخوارزمية كلها: ما إن تُفهم القوى الأولية حتى تصبح المعايير المركبة نتيجة مباشرة.
عندما تصبح الحالة \((s,U(s))\) معروفة نضع
$$f=s-U(s).$$
وهذه \(f\) هي بالضبط المواضع الحرة التي يمكن إضافتها. لذلك يساهم المعيار بصف معاملات ثنائي الحدين
$$\binom{f}{0},\binom{f}{1},\binom{f}{2},\dots,\binom{f}{\min(f,n-U(s))}$$
في الأحجام \(U(s),U(s)+1,\dots\). وبعد معالجة جميع المعايير، يحول الجمع السابق \(B\) إلى \(A\)، ثم يحول عكس Möbius \(A\) إلى العد الأولي \(C\).
المعايير التي تحقق \(U(s)\le 4\) هي
$$s\in\{1,2,3,4,5,6,7,9\}.$$
وقيمها تساوي
$$U(1)=1,\ U(2)=2,\ U(3)=2,\ U(4)=4,\ U(5)=3,\ U(6)=4,\ U(7)=4,\ U(9)=4.$$
وهناك مثالان يوضحان أصل هذه القيم. أولاً، modulo \(5\) نجد
$$R_5=\{0,1,3\},$$
ومن ثم \(U(5)=3\). وثانياً، بالنسبة إلى \(9\)، تعطي علاقة القوى الأولية
$$U(9)=3\,U(3)-(3-1)=3\cdot 2-2=4.$$
وبالنسبة إلى \(s=5\) يبقى \(5-3=2\) بقايا حرة، ولذلك يسهم هذا المعيار بالمقدار
$$\binom{2}{0}=1$$
في الحجم \(3\)، وبالمقدار
$$\binom{2}{1}=2$$
في الحجم \(4\). وعند جمع جميع المعايير نحصل على
$$B(1)=1,\qquad B(2)=2,\qquad B(3)=2,\qquad B(4)=6,$$
ومن ثم
$$A(1)=1,\qquad A(2)=3,\qquad A(3)=5,\qquad A(4)=11.$$
والآن نطبق عكس Möbius:
$$C(4)=\mu(1)A(4)+\mu(2)A(2)+\mu(3)A(1)+\mu(4)A(1)=11-3-1+0=7.$$
وهذا هو بالضبط أحد اختبارات الصحة الصغيرة للحل.
تسير تطبيقات C++ وPython وJava وفق الخطة الحسابية نفسها. الاختلافات الأساسية بينها هندسية أكثر منها رياضية.
تبدأ التطبيقات ببناء جدول الأعداد الأولية اللازم لتوليد الحالات الضربية، وجدول Möbius اللازم للانعكاس النهائي. ثم تعد الحالات من الشكل \((s,U(s))\)، ولكن فقط عندما \(U(s)\le n\)، لأن القيم الأكبر لا يمكن أن تسهم في \(C(n)\).
قوى \(2\) هي نقطة البداية الطبيعية لأن \(U(2^e)=2^e\) معروف مباشرة. وإذا كانت لدينا حالة حالية قيمتها \(u=U(s)\)، فإن تجربة عدد أولي فردي جديد \(p\) لا تكون مفيدة إلا إذا حقق أصغر عامل ممكن الشرط
$$U(p)=\frac{p+1}{2}\le \frac{n}{u},$$
أي
$$p\le 2\left\lfloor\frac{n}{u}\right\rfloor-1.$$
ثم تمتد القوى الأعلى \(p^e\) ما دام حاصل الضرب الجديد \(u\,U(p^e)\) لا يتجاوز الحد المطلوب. وبما أن الأعداد الأولية الفردية تضاف بترتيب تصاعدي، فإن كل تحليل أولي مسموح يُولد مرة واحدة فقط.
في كل حالة يكون عدد البواقي الحرة هو \(f=s-U(s)\). وهذه الحالة تضيف سلسلة كاملة من معاملات ثنائي الحدين إلى جدول الأحجام الدقيقة. وتُحدَّث الحدود المتتالية بالعلاقة
$$\binom{f}{k+1}=\binom{f}{k}\cdot\frac{f-k}{k+1},$$
وذلك modulo \(1111211113\). وبما أن الترديد عدد أولي، فإن المعكوسات اللازمة للأعداد \(1,2,\dots,n+1\) موجودة وتُحسب مسبقاً مرة واحدة. وبعد أن تسهم جميع الحالات، يتحول جدول الأحجام الدقيقة إلى الجدول التراكمي \(A\) بواسطة جمع سابق.
في المرحلة الأخيرة يُحسب
$$C(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\pmod{1111211113}.$$
وتوزع نسختا C++ وJava مرحلة تجميع الحالات المكلفة على عدة عمّال، بينما تنفذ نسخة Python الجمع نفسه بصورة تسلسلية. كما تُفحَص الاستراتيجية على أمثلة صغيرة: صيغة \(U(s)\) تطابق التعداد المباشر للبواقي في المعايير الصغيرة، والقيم \(C(3)=3\) و\(C(4)=7\) و\(C(10)=561\) تنسجم مع الاشتقاق الرياضي.
لنرمز بـ \(S(n)\) إلى عدد الحالات المعدودة \((s,U(s))\) التي تحقق \(U(s)\le n\). إن بناء غربال الأعداد الأولية حتى \(2n\) وجدول Möbius حتى \(n\) يكلف \(O(n\log\log n)\) زمناً و\(O(n)\) ذاكرة.
أما توليد الحالات نفسه فيكلف \(O(S(n))\). وتعطي الحالة \((s,u)\)
$$1+\min(s-u,n-u)$$
تحديثات ثنائية الحدين، لذا يكون الزمن الكلي
$$O\!\left(n\log\log n + S(n) + \sum_{(s,u)}\bigl(1+\min(s-u,n-u)\bigr)\right).$$
واستهلاك الذاكرة هو \(O(n+S(n))\). وعندما \(n=10000\)، تكون مرحلة التجميع هي الجزء المسيطر، ولذلك توازيها النسخ متعددة العمّال.