For a positive integer \(n\), define \(\operatorname{streak}(n)=k\) to be the smallest positive integer \(k\) such that \(n+k\) is not divisible by \(k+1\). Equivalently, the divisibility tests succeed for \(2,3,\dots,k\) and then fail at the next one.
The function \(P(s,N)\) counts how many integers \(n\) satisfy
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$$
The goal is to compute
$$\sum_{i=1}^{31} P(i,4^i).$$
A direct scan up to \(4^{31}\) would be hopeless, so the solution must convert the divisibility streak into a small number of arithmetic formulas.
The key observation is that the whole streak condition collapses into a single congruence modulo a least common multiple.
If \(\operatorname{streak}(n)\ge s\), then the first \(s-1\) tests all succeed. That means
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
For a fixed divisor \(m\in\{2,3,\dots,s\}\), the relevant condition is
$$n+(m-1)\equiv 0\pmod m.$$
Since \(m-1\equiv -1\pmod m\), this is equivalent to
$$n-1\equiv 0\pmod m,$$
or simply
$$n\equiv 1\pmod m.$$
So a streak of length at least \(s\) means that \(n\) is congruent to \(1\) modulo every integer from \(2\) through \(s\).
Let
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
Including \(1\) changes nothing numerically, but it keeps the notation tidy. Because \(L_s\) is divisible by every \(m\le s\), the condition
$$n\equiv 1\pmod{L_s}$$
immediately implies
$$n\equiv 1\pmod m\qquad\text{for all }2\le m\le s.$$
The converse is also true: if \(n\equiv 1\pmod m\) for every \(m=2,3,\dots,s\), then \(n-1\) is a common multiple of all those integers, hence a multiple of their least common multiple. Therefore
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
This is the central compression step of the whole problem.
Now we want \(\operatorname{streak}(n)=s\), not merely \(\ge s\). That means the first \(s-1\) divisibility tests succeed, but the next test fails. In congruence language:
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ and }\operatorname{streak}(n)\not\ge s+1.$$
Using the previous step, this becomes
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ and }n\not\equiv 1\pmod{L_{s+1}}.$$
So the desired count is the number of integers congruent to \(1\) modulo \(L_s\), minus the number of integers congruent to \(1\) modulo the stronger modulus \(L_{s+1}\).
Suppose we want to count integers in the open interval \(1 \lt n \lt N\) such that
$$n\equiv 1\pmod L.$$
Every such integer has the form
$$n=1+kL$$
for some integer \(k\ge 1\). The upper bound \(n\lt N\) is equivalent to
$$1+kL\le N-1,$$
so
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
Hence the number of admissible \(n\) is exactly
$$\left\lfloor \frac{N-2}{L}\right\rfloor.$$
Applying this to the two moduli \(L_s\) and \(L_{s+1}\) yields the closed formula
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
The problem asks for
$$\sum_{i=1}^{31} P(i,4^i).$$
Substituting the formula above gives
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
So once the lcm table \(L_1,L_2,\dots,L_{32}\) is precomputed, each term is just two integer divisions and one subtraction.
The small checkpoint \(P(3,14)=1\) falls out immediately. We have
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
Therefore
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
Indeed, the integers congruent to \(1\) modulo \(6\) inside \(1 \lt n \lt 14\) are \(7\) and \(13\), but \(13\equiv 1\pmod{12}\) as well, so only \(7\) has streak exactly \(3\).
A larger checkpoint is
$$L_6=60,\qquad L_7=420,$$
hence
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
These examples match the arithmetic used by the implementation.
The C++, Python, and Java implementations all follow the same plan. First, they precompute the least common multiples \(L_0,L_1,\dots,L_{32}\), where \(L_0=1\) and each next value is obtained from the previous one by the identity
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
This avoids repeated factorization and builds exactly the moduli needed for the queries \(P(i,4^i)\).
Next, the implementation uses a small arithmetic routine for the count of integers congruent to \(1\) modulo \(L\) in the open interval \(1 \lt n \lt N\). That routine returns
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
with a trivial zero result when the modulus is already larger than \(N-2\).
Then each term \(P(s,N)\) is computed by subtracting the count for \(L_{s+1}\) from the count for \(L_s\). Finally, the program iterates through \(i=1,2,\dots,31\), updates the current power \(4^i\), and accumulates the resulting terms. No search over candidate values of \(n\) is performed at any stage.
If we write \(S\) for the largest streak length being queried, precomputing \(L_1,\dots,L_{S+1}\) takes \(S\) gcd/lcm updates. With the Euclidean algorithm for gcd, that is \(O(S\log S)\) arithmetic time in the usual machine-integer model and \(O(S)\) memory to store the table. After that, each query \(P(s,N)\) is \(O(1)\).
For the actual problem, \(S=31\). Therefore the real running time and memory usage are both effectively constant.
Für eine positive ganze Zahl \(n\) sei \(\operatorname{streak}(n)=k\) das kleinste positive \(k\), für das \(n+k\) nicht mehr durch \(k+1\) teilbar ist. Anders gesagt: Die Teilbarkeitstests für \(2,3,\dots,k\) funktionieren noch, der nächste Test schlägt fehl.
Die Funktion \(P(s,N)\) zählt alle Zahlen \(n\) mit
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$$
Gesucht ist also
$$\sum_{i=1}^{31} P(i,4^i).$$
Da die obere Grenze bis \(4^{31}\) reicht, ist vollständiges Durchprobieren ausgeschlossen. Man muss die Bedingung in reine Kongruenzrechnung umformen.
Der entscheidende Schritt besteht darin, die ganze Folge von Teilbarkeitsbedingungen auf eine einzige Kongruenz modulo eines kgV zu reduzieren.
Aus \(\operatorname{streak}(n)\ge s\) folgt, dass die ersten \(s-1\) Tests erfolgreich sind. Also gilt
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
Für einen festen Divisor \(m\in\{2,3,\dots,s\}\) lautet die entsprechende Bedingung
$$n+(m-1)\equiv 0\pmod m.$$
Da \(m-1\equiv -1\pmod m\), ist das äquivalent zu
$$n-1\equiv 0\pmod m,$$
also schlicht zu
$$n\equiv 1\pmod m.$$
Eine Streak-Länge von mindestens \(s\) bedeutet somit: \(n\) ist zu \(1\) kongruent modulo jeder Zahl von \(2\) bis \(s\).
Setze
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
Die \(1\) zu notieren ist nur eine bequeme Schreibweise; numerisch ändert sie nichts. Weil \(L_s\) durch jedes \(m\le s\) teilbar ist, impliziert
$$n\equiv 1\pmod{L_s}$$
automatisch
$$n\equiv 1\pmod m\qquad\text{für alle }2\le m\le s.$$
Umgekehrt gilt: Wenn \(n\equiv 1\pmod m\) für alle \(m=2,3,\dots,s\), dann ist \(n-1\) ein gemeinsames Vielfaches all dieser Zahlen und damit ein Vielfaches ihres kleinsten gemeinsamen Vielfachen. Also
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
Damit ist die gesamte Bedingung auf genau eine Kongruenz verdichtet.
Gesucht ist \(\operatorname{streak}(n)=s\). Das bedeutet: Die ersten \(s-1\) Teilbarkeitstests gelten, aber der nächste nicht. In Symbolen:
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ und }\operatorname{streak}(n)\not\ge s+1.$$
Mit dem Ergebnis aus Schritt 2 wird daraus
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ und }n\not\equiv 1\pmod{L_{s+1}}.$$
Man zählt also alle Zahlen \(n\equiv 1\pmod{L_s}\) und zieht diejenigen ab, die bereits die stärkere Bedingung modulo \(L_{s+1}\) erfüllen.
Betrachte allgemein die Kongruenz
$$n\equiv 1\pmod L.$$
Jede Lösung hat die Form
$$n=1+kL$$
mit einem ganzzahligen \(k\ge 1\). Die obere Schranke \(n\lt N\) ist gleichbedeutend mit
$$1+kL\le N-1,$$
also
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
Damit gibt es genau
$$\left\lfloor \frac{N-2}{L}\right\rfloor$$
zulässige Werte. Auf \(L_s\) und \(L_{s+1}\) angewendet ergibt das die geschlossene Formel
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
Die Aufgabe fordert
$$\sum_{i=1}^{31} P(i,4^i).$$
Mit der eben hergeleiteten Formel wird daraus
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
Sobald die Folge \(L_1,L_2,\dots,L_{32}\) bekannt ist, benötigt jeder Summand also nur noch zwei ganzzahlige Divisionen und eine Subtraktion.
Ein kleiner Prüfwert ist \(P(3,14)=1\). Hier gilt
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
Daher
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
Die zu \(1\) modulo \(6\) kongruenten Zahlen im Bereich \(1 \lt n \lt 14\) sind \(7\) und \(13\). Davon ist aber \(13\equiv 1\pmod{12}\), sodass nur \(7\) genau die Streak-Länge \(3\) besitzt.
Ein größerer Kontrollwert ist
$$L_6=60,\qquad L_7=420,$$
und damit
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
Auch dieser Wert stimmt genau mit der implementierten Rechnung überein.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Schema. Zuerst werden die Werte \(L_0,L_1,\dots,L_{32}\) vorab berechnet, wobei \(L_0=1\) ist und jeder nächste Wert mit der Identität
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$
aus dem vorherigen entsteht. So erhält man genau die Moduli, die für die Abfragen \(P(i,4^i)\) gebraucht werden.
Anschließend verwendet die Implementierung eine kleine arithmetische Zählroutine für Zahlen \(n\equiv 1\pmod L\) im offenen Intervall \(1 \lt n \lt N\). Diese liefert den Wert
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
bzw. sofort \(0\), wenn der Modulus bereits größer als \(N-2\) ist.
Danach wird \(P(s,N)\) jeweils als Differenz der beiden Zählwerte für \(L_s\) und \(L_{s+1}\) gebildet. Zum Schluss läuft das Programm durch \(i=1,2,\dots,31\), aktualisiert die aktuelle Potenz \(4^i\) und addiert die berechneten Beiträge. Eine direkte Iteration über Kandidaten \(n\) findet nirgendwo statt.
Bezeichnet \(S\) die größte abgefragte Streak-Länge, dann benötigt die Vorberechnung von \(L_1,\dots,L_{S+1}\) genau \(S\) ggT-/kgV-Aktualisierungen. Mit dem euklidischen Algorithmus für den ggT ergibt das im üblichen Maschinenmodell \(O(S\log S)\) arithmetische Zeit und \(O(S)\) Speicher für die Tabelle. Jede einzelne Anfrage \(P(s,N)\) kostet danach \(O(1)\).
Im konkreten Problem ist \(S=31\). Laufzeit und Speicherbedarf sind daher praktisch konstant.
Pozitif bir \(n\) için \(\operatorname{streak}(n)=k\), \(n+k\) sayısının \(k+1\)'e bölünmediği ilk pozitif \(k\) değeridir. Başka bir deyişle, \(2,3,\dots,k\) testleri başarılı olur ve bir sonraki test başarısız olur.
\(P(s,N)\) fonksiyonu,
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s$$
koşullarını sağlayan \(n\) sayılarının adedini verir. Hesaplanması istenen toplam
$$\sum_{i=1}^{31} P(i,4^i)$$
olduğundan, \(4^{31}\) büyüklüğüne kadar tek tek deneme yapmak mümkün değildir. Asıl fikir, streak koşulunu EKOK tabanlı bir kongruans problemine çevirmektir.
Ana gözlem şudur: görünüşte uzun bir bölünebilme zinciri, aslında tek bir modül altında tek bir kongruansa indirgenir.
Eğer \(\operatorname{streak}(n)\ge s\) ise ilk \(s-1\) testin hepsi geçer. Yani
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
Burada \(m\in\{2,3,\dots,s\}\) için ilgili koşul
$$n+(m-1)\equiv 0\pmod m$$
şeklindedir. Çünkü \(m-1\equiv -1\pmod m\), bu ifade
$$n-1\equiv 0\pmod m$$
ile aynıdır; yani
$$n\equiv 1\pmod m.$$
Demek ki en az \(s\) uzunluğunda bir streak, \(n\)'in \(2\)'den \(s\)'ye kadar her sayıya göre \(1\) kalanını vermesi anlamına gelir.
Şimdi
$$L_s=\operatorname{lcm}(1,2,\dots,s)$$
tanımını yapalım. Burada \(1\)'i yazmak sadece notasyonu düzgünleştirir. \(L_s\), \(s\)'ye kadar olan her sayının katı olduğu için
$$n\equiv 1\pmod{L_s}$$
olması otomatik olarak
$$n\equiv 1\pmod m\qquad\text{tüm }2\le m\le s\text{ için}$$
sonucunu verir. Tersi de doğrudur: eğer \(n\equiv 1\pmod m\) tüm \(m=2,3,\dots,s\) için sağlanıyorsa, \(n-1\) bu sayıların hepsinin ortak katıdır; dolayısıyla EKOK'larının da katıdır. Böylece
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}$$
elde edilir. Problemin özü tam olarak bu sıkıştırmadır.
Bizim aradığımız şey \(\operatorname{streak}(n)=s\) koşuludur. Bu da ilk \(s-1\) testin geçip bir sonraki testin kalması demektir. Yani
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ ve }\operatorname{streak}(n)\not\ge s+1.$$
Bir önceki adımdaki eşdeğerliği kullanırsak
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ ve }n\not\equiv 1\pmod{L_{s+1}}.$$
Dolayısıyla tam \(s\) streak sayısı, \(L_s\) modunda \(1\) olanların sayısından, daha güçlü \(L_{s+1}\) koşulunu sağlayanların sayısını çıkarmaktır.
Genel olarak
$$n\equiv 1\pmod L$$
şartını sağlayan tüm sayılar
$$n=1+kL$$
biçimindedir ve burada \(k\ge 1\) olmalıdır; çünkü \(n>1\). Üst sınır \(n\lt N\) ise
$$1+kL\le N-1$$
anlamına gelir. Buradan
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor$$
çıkar. O halde çözüm sayısı tam olarak
$$\left\lfloor \frac{N-2}{L}\right\rfloor$$
olur. Bunu \(L_s\) ve \(L_{s+1}\) için uygulayınca kapalı formül elde edilir:
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
İstenen toplam
$$\sum_{i=1}^{31} P(i,4^i)$$
olduğundan, yerine koyma ile
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i)$$
yazılır. Yani \(L_1,L_2,\dots,L_{32}\) bir kez hazırlandıktan sonra her terim iki tamsayı bölmesi ve bir çıkarma ile bulunur.
Küçük doğrulama örneği \(P(3,14)=1\) değeridir. Çünkü
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
Buna göre
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
\(1 \lt n \lt 14\) aralığında \(6\) modunda \(1\) kalanını veren sayılar \(7\) ve \(13\)'tür; fakat \(13\), \(12\) modunda da \(1\) verdiği için tam streak değeri \(3\) olan tek sayı \(7\)'dir.
Daha büyük bir kontrol örneği de
$$L_6=60,\qquad L_7=420$$
ile
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286$$
hesabıdır. Bu sonuç da uygulamanın kullandığı aritmetik ile tam uyumludur.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(L_0,L_1,\dots,L_{32}\) EKOK tablosu oluşturulur; burada \(L_0=1\) alınır ve her yeni değer
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$
özdeşliğiyle bir önceki değerden türetilir. Böylece gereken tüm modüller tekrar tekrar çarpanlara ayırma yapmadan hazırlanmış olur.
Sonra uygulama, \(1 \lt n \lt N\) aralığında \(n\equiv 1\pmod L\) olan sayıların miktarını hesaplayan küçük bir aritmetik yordam kullanır. Bu yordam
$$\left\lfloor\frac{N-2}{L}\right\rfloor$$
değerini döndürür; eğer modül \(N-2\)'den büyükse sonuç doğrudan sıfırdır.
Ardından her \(P(s,N)\) değeri, \(L_s\) için bulunan sayıdan \(L_{s+1}\) için bulunan sayının çıkarılmasıyla elde edilir. Son aşamada program \(i=1,2,\dots,31\) için ilerler, o andaki \(4^i\) değerini günceller ve terimleri toplamda biriktirir. Hiçbir aşamada aday \(n\) değerleri tek tek taranmaz.
\(S\) en büyük streak uzunluğu olsun. \(L_1,\dots,L_{S+1}\) tablosunu kurmak \(S\) adet EBOB/EKOK güncellemesi gerektirir. EBOB için Öklid algoritması kullanılırsa, standart makine tamsayı modeli altında aritmetik süre \(O(S\log S)\), bellek kullanımı ise \(O(S)\) olur. Tek bir \(P(s,N)\) sorgusu bundan sonra \(O(1)\) maliyetlidir.
Gerçek problemde \(S=31\) olduğundan zaman ve bellek gereksinimi pratikte sabit kabul edilir.
Para un entero positivo \(n\), se define \(\operatorname{streak}(n)=k\) como el menor entero positivo \(k\) tal que \(n+k\) ya no es divisible por \(k+1\). Dicho de otra manera, las pruebas de divisibilidad para \(2,3,\dots,k\) funcionan, y la siguiente falla.
La función \(P(s,N)\) cuenta cuántos enteros \(n\) cumplen
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$$
Lo que se pide es
$$\sum_{i=1}^{31} P(i,4^i).$$
Como el límite superior llega hasta \(4^{31}\), no se puede recorrer \(n\) uno por uno. La solución correcta consiste en transformar la racha de divisibilidad en una condición de congruencia muy compacta.
La observación central es que toda la cadena de divisibilidades se resume en una sola congruencia módulo un mínimo común múltiplo.
Si \(\operatorname{streak}(n)\ge s\), entonces las primeras \(s-1\) pruebas tienen éxito. Por tanto, se cumple
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
Para un divisor fijo \(m\in\{2,3,\dots,s\}\), la condición correspondiente es
$$n+(m-1)\equiv 0\pmod m.$$
Como \(m-1\equiv -1\pmod m\), esto equivale a
$$n-1\equiv 0\pmod m,$$
es decir, simplemente a
$$n\equiv 1\pmod m.$$
Así, tener una racha de longitud al menos \(s\) significa que \(n\) deja residuo \(1\) al dividirlo por todos los enteros de \(2\) a \(s\).
Definamos
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
Escribir el \(1\) no cambia el valor, pero hace la notación más limpia. Como \(L_s\) es múltiplo de todos los enteros hasta \(s\), la congruencia
$$n\equiv 1\pmod{L_s}$$
implica automáticamente
$$n\equiv 1\pmod m\qquad\text{para todo }2\le m\le s.$$
La implicación inversa también vale: si \(n\equiv 1\pmod m\) para todos los \(m=2,3,\dots,s\), entonces \(n-1\) es múltiplo común de todos ellos, y por lo tanto es múltiplo de su mínimo común múltiplo. Concluimos que
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
Este es el paso que reduce el problema a una aritmética muy simple.
Nos interesa \(\operatorname{streak}(n)=s\), no solo \(\ge s\). Eso significa que las primeras \(s-1\) divisibilidades se cumplen, pero la siguiente ya no. En símbolos:
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ y }\operatorname{streak}(n)\not\ge s+1.$$
Usando el resultado anterior, esto se convierte en
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ y }n\not\equiv 1\pmod{L_{s+1}}.$$
Por tanto, el valor exacto se obtiene restando los casos que también satisfacen el siguiente nivel de la racha.
Consideremos ahora la congruencia general
$$n\equiv 1\pmod L.$$
Toda solución se escribe como
$$n=1+kL$$
con \(k\ge 1\). La cota superior \(n\lt N\) equivale a
$$1+kL\le N-1,$$
de donde se obtiene
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
Así, el número de soluciones es exactamente
$$\left\lfloor \frac{N-2}{L}\right\rfloor.$$
Aplicando esto a \(L_s\) y \(L_{s+1}\), se llega a la fórmula cerrada
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
El problema pide
$$\sum_{i=1}^{31} P(i,4^i).$$
Entonces
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
Una vez calculada la tabla \(L_1,L_2,\dots,L_{32}\), cada término requiere solo dos divisiones enteras y una resta.
El pequeño punto de control \(P(3,14)=1\) se obtiene enseguida. Se tiene
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
Por lo tanto,
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
Los números congruentes con \(1\) módulo \(6\) dentro de \(1 \lt n \lt 14\) son \(7\) y \(13\), pero \(13\equiv 1\pmod{12}\) también, así que solo \(7\) tiene racha exacta \(3\).
Otro control útil es
$$L_6=60,\qquad L_7=420,$$
de modo que
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
Este valor coincide con la cuenta realizada por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero precalculan los mínimos comunes múltiplos \(L_0,L_1,\dots,L_{32}\), empezando con \(L_0=1\) y actualizando cada nuevo valor con la identidad
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
Así se obtienen todos los módulos necesarios sin volver a factorizar desde cero.
Después, la implementación usa una rutina aritmética muy pequeña para contar cuántos enteros del intervalo \(1 \lt n \lt N\) satisfacen \(n\equiv 1\pmod L\). Esa cuenta es
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
o \(0\) si el módulo ya es mayor que \(N-2\).
Con esa pieza, cada valor \(P(s,N)\) se calcula restando la cuenta asociada a \(L_{s+1}\) de la cuenta asociada a \(L_s\). Finalmente, el programa recorre \(i=1,2,\dots,31\), actualiza la potencia actual \(4^i\) y acumula todos los términos. Nunca se prueban los valores de \(n\) de forma individual.
Si \(S\) es la mayor longitud de racha consultada, construir \(L_1,\dots,L_{S+1}\) requiere \(S\) actualizaciones de mcd/mcm. Usando el algoritmo de Euclides para el mcd, el coste aritmético es \(O(S\log S)\) en el modelo usual de enteros de máquina, y la memoria necesaria para la tabla es \(O(S)\). Cada consulta \(P(s,N)\) posterior es \(O(1)\).
En el problema real, \(S=31\), así que tanto el tiempo como la memoria son efectivamente constantes.
对正整数 \(n\)，定义 \(\operatorname{streak}(n)=k\) 为最小的正整数 \(k\)，使得 \(n+k\) 不能被 \(k+1\) 整除。换句话说，关于 \(2,3,\dots,k\) 的整除测试全部成功，而下一步第一次失败。
\(P(s,N)\) 表示满足
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s$$
的整数 \(n\) 的个数。题目要求计算
$$\sum_{i=1}^{31} P(i,4^i).$$
由于上界达到 \(4^{31}\)，显然不能逐个枚举 \(n\)。真正可行的方法是把 streak 条件改写成关于最小公倍数的同余条件，然后直接计数。
这道题的核心在于：看起来是一长串不同模数下的整除要求，但它们最终可以压缩成一个单独的同余式。
如果 \(\operatorname{streak}(n)\ge s\)，那么前 \(s-1\) 次测试全部通过，因此必须有
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
对任意固定的 \(m\in\{2,3,\dots,s\}\)，对应的条件是
$$n+(m-1)\equiv 0\pmod m.$$
因为 \(m-1\equiv -1\pmod m\)，所以上式等价于
$$n-1\equiv 0\pmod m,$$
也就是
$$n\equiv 1\pmod m.$$
因此，“streak 至少为 \(s\)” 的含义就是：\(n\) 对 \(2,3,\dots,s\) 这些所有模数都满足余数为 \(1\)。
定义
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
把 \(1\) 写进去只是为了记号统一，数值上并不会产生变化。由于 \(L_s\) 是从 \(1\) 到 \(s\) 每个整数的倍数，所以一旦
$$n\equiv 1\pmod{L_s}$$
成立，就必然有
$$n\equiv 1\pmod m\qquad\text{对所有 }2\le m\le s.$$
反过来，如果 \(n\equiv 1\pmod m\) 对全部 \(m=2,3,\dots,s\) 都成立，那么 \(n-1\) 就是这些整数的公共倍数，因此一定也是它们最小公倍数的倍数。于是得到完全等价的结论
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
这一步把原题从“很多个整除条件”压缩成了“一个模数条件”，是整个解法的关键。
题目要求的是 \(\operatorname{streak}(n)=s\)，而不是 \(\operatorname{streak}(n)\ge s\)。这意味着前 \(s-1\) 个整除条件成立，但再往后一项不成立。用逻辑式写出来就是
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ 且 }\operatorname{streak}(n)\not\ge s+1.$$
结合上一步的等价关系，可以立刻化成
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ 且 }n\not\equiv 1\pmod{L_{s+1}}.$$
也就是说，恰好为 \(s\) 的个数，就是满足模 \(L_s\) 余 \(1\) 的个数，减去那些连模 \(L_{s+1}\) 余 \(1\) 也同时满足的个数。
现在考虑一般问题：在开区间 \(1 \lt n \lt N\) 内，有多少整数满足
$$n\equiv 1\pmod L?$$
所有这样的整数都可以写成
$$n=1+kL$$
其中 \(k\) 是正整数，因为 \(n\) 必须严格大于 \(1\)。上界 \(n\lt N\) 等价于
$$1+kL\le N-1,$$
因此
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
所以满足条件的 \(k\) 的个数正好是
$$\left\lfloor \frac{N-2}{L}\right\rfloor.$$
把这里的 \(L\) 分别替换成 \(L_s\) 和 \(L_{s+1}\)，就得到
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
这就是程序真正使用的闭式公式。
题目所求为
$$\sum_{i=1}^{31} P(i,4^i).$$
于是可以直接写成
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
这说明只要先把 \(L_1,L_2,\dots,L_{32}\) 预处理出来，后面的每一项都只是两个整除和一个减法，不需要任何暴力搜索。
题目中的小检验值 \(P(3,14)=1\) 很容易验证。先算出
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
因此
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
如果把区间 \(1 \lt n \lt 14\) 中模 \(6\) 余 \(1\) 的整数列出来，就是 \(7\) 和 \(13\)。其中 \(13\) 同时也满足模 \(12\) 余 \(1\)，所以它的 streak 至少是 \(4\)，不能算在恰好为 \(3\) 的集合里，于是只剩下 \(7\) 一个数。
再看一个更大的检查点：
$$L_6=60,\qquad L_7=420,$$
所以
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
这和实现中的算术结果完全一致。
C++、Python 和 Java 实现都采用同样的流程。首先预计算 \(L_0,L_1,\dots,L_{32}\)，其中 \(L_0=1\)，每一步都利用公式
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$
从前一个最小公倍数递推出下一个。这样就避免了对每个阶段重新做完整分解。
接着，实现会调用一个很小的计数过程，用来计算在开区间 \(1 \lt n \lt N\) 中满足 \(n\equiv 1\pmod L\) 的整数个数。这个数量正是
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
如果模数已经大于 \(N-2\)，那么结果自然就是 \(0\)。
然后每个 \(P(s,N)\) 都通过“模 \(L_s\) 的计数减去模 \(L_{s+1}\) 的计数”得到。最后，程序按 \(i=1,2,\dots,31\) 依次推进，维护当前的 \(4^i\)，并把每个项累加到总和中。整个过程中从来不会对候选 \(n\) 逐一检查。
设最大的 streak 长度为 \(S\)。预处理 \(L_1,\dots,L_{S+1}\) 需要做 \(S\) 次 gcd/lcm 更新；如果 gcd 使用欧几里得算法，那么在通常的机器整数模型下，算术时间为 \(O(S\log S)\)，存储这些最小公倍数需要 \(O(S)\) 空间。之后每次查询 \(P(s,N)\) 都是 \(O(1)\)。
在本题中 \(S=31\)，所以时间和空间消耗实际上都可以看成常数量级。
Для положительного целого \(n\) величина \(\operatorname{streak}(n)=k\) определяется как наименьшее положительное \(k\), при котором число \(n+k\) уже не делится на \(k+1\). Иначе говоря, проверки делимости для \(2,3,\dots,k\) проходят, а следующая впервые ломается.
Функция \(P(s,N)\) считает количество целых \(n\), удовлетворяющих условиям
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$$
Нужно вычислить сумму
$$\sum_{i=1}^{31} P(i,4^i).$$
Так как верхняя граница доходит до \(4^{31}\), прямой перебор невозможен. Поэтому решение переводит условие о streak в язык сравнений по модулю и затем считает их напрямую.
Главная идея состоит в том, что длинная цепочка условий делимости эквивалентна всего одному сравнению по модулю некоторого НОК.
Если \(\operatorname{streak}(n)\ge s\), то первые \(s-1\) проверок обязаны выполняться. Значит, имеем
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
Для фиксированного \(m\in\{2,3,\dots,s\}\) соответствующее условие выглядит так:
$$n+(m-1)\equiv 0\pmod m.$$
Поскольку \(m-1\equiv -1\pmod m\), это то же самое, что
$$n-1\equiv 0\pmod m,$$
или просто
$$n\equiv 1\pmod m.$$
Следовательно, streak длины хотя бы \(s\) означает, что число \(n\) дает остаток \(1\) по модулю каждого целого от \(2\) до \(s\).
Обозначим
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
Включение единицы ничего не меняет численно, но делает запись аккуратнее. Так как \(L_s\) кратно каждому \(m\le s\), из сравнения
$$n\equiv 1\pmod{L_s}$$
сразу следует
$$n\equiv 1\pmod m\qquad\text{для всех }2\le m\le s.$$
Обратное тоже верно: если \(n\equiv 1\pmod m\) для всех \(m=2,3,\dots,s\), то \(n-1\) является общим кратным этих чисел, а значит, делится и на их наименьшее общее кратное. Итак, получаем точную эквивалентность
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
Именно этот шаг превращает задачу в короткую арифметическую формулу.
Нам нужно не условие \(\ge s\), а точное значение \(\operatorname{streak}(n)=s\). Это означает: первые \(s-1\) делимостей выполняются, но следующая уже нет. То есть
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ и }\operatorname{streak}(n)\not\ge s+1.$$
Подставляя результат предыдущего шага, получаем
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ и }n\not\equiv 1\pmod{L_{s+1}}.$$
Значит, нужно взять количество чисел, дающих остаток \(1\) по модулю \(L_s\), и вычесть те, которые удовлетворяют уже более сильному условию по модулю \(L_{s+1}\).
Рассмотрим общее сравнение
$$n\equiv 1\pmod L.$$
Все его решения имеют вид
$$n=1+kL$$
при \(k\ge 1\). Условие \(n\lt N\) равносильно неравенству
$$1+kL\le N-1,$$
откуда следует
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
Следовательно, число допустимых \(n\) равно
$$\left\lfloor \frac{N-2}{L}\right\rfloor.$$
Применяя это сначала к \(L_s\), а затем к \(L_{s+1}\), получаем закрытую формулу
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
Задача просит найти
$$\sum_{i=1}^{31} P(i,4^i).$$
Поэтому итоговое выражение имеет вид
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
После предварительного вычисления \(L_1,L_2,\dots,L_{32}\) каждый член суммы сводится к двум целочисленным делениям и одному вычитанию.
Малый контрольный пример \(P(3,14)=1\) получается сразу. Имеем
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
Следовательно,
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
В интервале \(1 \lt n \lt 14\) числа, сравнимые с \(1\) по модулю \(6\), это \(7\) и \(13\). Но \(13\equiv 1\pmod{12}\) тоже, значит его streak уже не меньше \(4\), и остается только \(7\).
Более крупная проверка:
$$L_6=60,\qquad L_7=420,$$
откуда
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
Этот результат совпадает с вычислением, реализованным в программе.
Реализации на C++, Python и Java устроены одинаково. Сначала они предвычисляют значения \(L_0,L_1,\dots,L_{32}\), начиная с \(L_0=1\), а каждый следующий НОК получают из предыдущего по формуле
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
Это дает все нужные модули без повторной полной факторизации на каждом шаге.
Затем используется маленькая арифметическая процедура, которая считает количество чисел из открытого интервала \(1 \lt n \lt N\), удовлетворяющих сравнению \(n\equiv 1\pmod L\). Она возвращает значение
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
а если модуль уже больше, чем \(N-2\), результат сразу равен нулю.
После этого каждое \(P(s,N)\) вычисляется как разность подсчетов для \(L_s\) и \(L_{s+1}\). Наконец, программа проходит по \(i=1,2,\dots,31\), поддерживает текущую степень \(4^i\) и накапливает сумму. Никакого перебора кандидатов \(n\) не требуется.
Пусть \(S\) обозначает максимальную длину streak, для которой выполняются запросы. Построение таблицы \(L_1,\dots,L_{S+1}\) требует \(S\) обновлений через gcd/lcm. При использовании алгоритма Евклида для gcd это дает \(O(S\log S)\) арифметического времени в стандартной модели машинных целых и \(O(S)\) памяти на хранение таблицы. Каждый последующий запрос \(P(s,N)\) выполняется за \(O(1)\).
В реальной задаче \(S=31\), поэтому и время, и память фактически постоянны.
لعدد صحيح موجب \(n\)، نعرّف \(\operatorname{streak}(n)=k\) على أنه أصغر عدد موجب \(k\) بحيث يصبح \(n+k\) غير قابل للقسمة على \(k+1\). وبصياغة أخرى: اختبارات القسمة الخاصة بـ \(2,3,\dots,k\) تنجح، ثم يفشل الاختبار التالي لأول مرة.
الدالة \(P(s,N)\) تحسب عدد القيم \(n\) التي تحقق
$$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$$
والمطلوب هو حساب
$$\sum_{i=1}^{31} P(i,4^i).$$
وبما أن الحد الأعلى يصل إلى \(4^{31}\)، فلا يمكن فحص القيم واحدة واحدة. لذلك يعتمد الحل على تحويل تعريف streak إلى صيغة توافقات عددية يمكن عدّها مباشرة.
الفكرة الأساسية هي أن سلسلة شروط القسمة الطويلة يمكن ضغطها كلها في توافق وحيد بترديد يساوي المضاعف المشترك الأصغر.
إذا كان \(\operatorname{streak}(n)\ge s\)، فهذا يعني أن أول \(s-1\) اختبارات ناجحة. وبالتالي يجب أن يكون
$$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$$
ولعدد ثابت \(m\in\{2,3,\dots,s\}\)، يصبح الشرط الموافق هو
$$n+(m-1)\equiv 0\pmod m.$$
وبما أن \(m-1\equiv -1\pmod m\)، فهذا يكافئ
$$n-1\equiv 0\pmod m,$$
أي ببساطة
$$n\equiv 1\pmod m.$$
إذن امتلاك streak بطول لا يقل عن \(s\) يعني أن \(n\) يعطي الباقي \(1\) عند القسمة على كل عدد من \(2\) حتى \(s\).
لنعرّف
$$L_s=\operatorname{lcm}(1,2,\dots,s).$$
إدخال العدد \(1\) هنا لا يغيّر القيمة، لكنه يجعل الترميز أوضح. وبما أن \(L_s\) مضاعف لكل عدد حتى \(s\)، فإن الشرط
$$n\equiv 1\pmod{L_s}$$
يستتبع مباشرة
$$n\equiv 1\pmod m\qquad\text{for all }2\le m\le s.$$
والعكس صحيح أيضًا: إذا تحقق \(n\equiv 1\pmod m\) لكل \(m=2,3,\dots,s\)، فإن \(n-1\) يكون مضاعفًا مشتركًا لهذه الأعداد جميعًا، وبالتالي يكون مضاعفًا للمضاعف المشترك الأصغر لها. ومن هنا نحصل على التكافؤ الدقيق
$$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$$
هذه هي الخطوة التي تختصر بنية المسألة بالكامل.
المطلوب ليس فقط \(\operatorname{streak}(n)\ge s\)، بل القيمة الدقيقة \(\operatorname{streak}(n)=s\). وهذا يعني أن أول \(s-1\) شروط تنجح، لكن الشرط التالي يفشل. أي أن
$$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ and }\operatorname{streak}(n)\not\ge s+1.$$
وباستخدام نتيجة الخطوة السابقة يصبح هذا
$$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ and }n\not\equiv 1\pmod{L_{s+1}}.$$
إذن عدد القيم ذات streak الدقيقة \(s\) يساوي عدد القيم الموافقة لـ \(1\) modulo \(L_s\)، مطروحًا منه عدد القيم التي تحقق أيضًا الشرط الأقوى modulo \(L_{s+1}\).
لنأخذ التوافق العام
$$n\equiv 1\pmod L.$$
كل حل يمكن كتابته على الصورة
$$n=1+kL$$
حيث \(k\ge 1\)، لأن \(n\) يجب أن يكون أكبر من \(1\) تمامًا. أما الشرط \(n\lt N\) فيكافئ
$$1+kL\le N-1,$$
ومن ثم
$$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$$
وبالتالي فإن عدد الحلول يساوي تمامًا
$$\left\lfloor \frac{N-2}{L}\right\rfloor.$$
وعند تطبيق هذه الصيغة على \(L_s\) و\(L_{s+1}\) نحصل على العلاقة المغلقة
$$P(s,N)=\left\lfloor\frac{N-2}{L_s}\right\rfloor-\left\lfloor\frac{N-2}{L_{s+1}}\right\rfloor.$$
المسألة تطلب
$$\sum_{i=1}^{31} P(i,4^i).$$
وبالتعويض نحصل على
$$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$$
أي أنه بعد بناء الجدول \(L_1,L_2,\dots,L_{32}\) مسبقًا، يصبح كل حد في المجموع مجرد قسمتين صحيحتين وعملية طرح واحدة.
فحص صغير مفيد هو القيمة \(P(3,14)=1\). لدينا
$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=\operatorname{lcm}(1,2,3,4)=12.$$
إذًا
$$P(3,14)=\left\lfloor\frac{14-2}{6}\right\rfloor-\left\lfloor\frac{14-2}{12}\right\rfloor=2-1=1.$$
والأعداد الموافقة لـ \(1\) modulo \(6\) داخل المجال \(1 \lt n \lt 14\) هي \(7\) و\(13\)، لكن \(13\equiv 1\pmod{12}\) أيضًا، لذلك لا يبقى سوى \(7\) كعدد يملك streak تساوي \(3\) بالضبط.
وفحص أكبر قليلًا هو
$$L_6=60,\qquad L_7=420,$$
ومن ثم
$$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$$
وهذه القيمة تطابق ما تعتمده الخوارزمية الحسابية في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولًا يُبنى جدول القيم \(L_0,L_1,\dots,L_{32}\)، مع أخذ \(L_0=1\)، ثم يُحسب كل حد جديد من الحد السابق باستخدام العلاقة
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
وهذا يوفر جميع الترديدات المطلوبة من دون إعادة تحليل كل مرحلة من البداية.
بعد ذلك تستخدم الخوارزمية روتينًا حسابيًا صغيرًا لعدّ الأعداد داخل المجال \(1 \lt n \lt N\) التي تحقق \(n\equiv 1\pmod L\). هذا الروتين يعيد القيمة
$$\left\lfloor\frac{N-2}{L}\right\rfloor,$$
ويعيد صفرًا مباشرة إذا كان الترديد أكبر أصلًا من \(N-2\).
ثم يُحسب كل \(P(s,N)\) على أنه الفرق بين العدّ الموافق لـ \(L_s\) والعدّ الموافق لـ \(L_{s+1}\). وفي النهاية يمر البرنامج على \(i=1,2,\dots,31\)، ويحدّث القوة الحالية \(4^i\)، ويضيف كل حد إلى المجموع الكلي. لا يوجد في أي مرحلة فحص مباشر لكل قيمة مرشحة لـ \(n\).
إذا رمزنا بأكبر طول streak مطلوب له بالرمز \(S\)، فإن بناء الجدول \(L_1,\dots,L_{S+1}\) يحتاج إلى \(S\) تحديثات من نوع gcd/lcm. ومع استخدام خوارزمية إقليدس لحساب gcd، تكون الكلفة الحسابية \(O(S\log S)\) في نموذج الأعداد الصحيحة المعتاد، بينما تحتاج المصفوفة إلى \(O(S)\) من الذاكرة. بعد ذلك تصبح كل قيمة \(P(s,N)\) عملية \(O(1)\).
وفي هذه المسألة تحديدًا لدينا \(S=31\)، لذا فالزمن والذاكرة عمليًا من رتبة ثابتة.