Let \(G(N)\) be the number of increasing positive-integer sequences
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
such that every interior triple is almost geometric in the sense that
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1).$$
The required answer is \(G(10^{18})\bmod (10^9+7)\). Direct enumeration is hopeless, so the implementations rely on a structural classification: every admissible sequence belongs either to a simple infinite family or to a short finite exception list.
The quantity
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
measures how far a triple is from being exactly geometric. True geometric progressions have \(\Delta_i=0\), while the pseudo-geometric condition only allows the five values \(-2,-1,0,1,2\).
For a sequence to be admissible, every interior index must satisfy
$$\Delta_i\in\{-2,-1,0,1,2\}.$$
This is an extremely rigid condition. The mathematical classification used by the implementations shows that long solutions do not wander arbitrarily: they fall into a few deterministic families. That is why the program counts families, not individual sequences.
Once a maximal family contains \(t\) valid terms, the number of contiguous subsequences of length at least \(5\) is
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
This identity is just the sum
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
because for each allowed length \(\ell\), there are \(t-\ell+1\) windows.
If we take any consecutive run
$$s,s+1,s+2,\dots,s+\ell-1,$$
then for every interior triple we get
$$ (x+1)^2-x(x+2)=1. $$
So every consecutive block is admissible. All such blocks are contained in the master chain
$$1,2,3,\dots,N,$$
which has \(N\) terms, hence its total contribution is simply
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
This explains the quadratic baseline visible in the implementations.
If the defect is always \(0\), then the sequence is an exact geometric progression. Every increasing integer geometric progression of length \(e+1\) can be written uniquely as
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
where
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
For a fixed numerator \(u\), there are exactly \(\varphi(u)\) admissible denominators \(q\) with \(1\le q\lt u\) and \(\gcd(u,q)=1\). The last term is \(c\,u^e\), so the bound \(a_t\le N\) gives
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
Therefore the total geometric contribution is
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
The fourth-root cutoff appears because even the shortest admissible geometric sequence has length \(5\), so its numerator base must satisfy \(u^4\le N\).
After removing the exact geometric case, the remaining long families are generated by second-order recurrences of one of the two forms
$$a_{n+1}=m a_n-a_{n-1},$$
or
$$a_{n+1}=m a_n+a_{n-1}.$$
The generic branches start from \((1,m)\). Two additional branches of the minus type start from \((1,2)\) with coefficient \(3\) and from \((1,3)\) with coefficient \(4\). Two additional branches of the plus type start from \((1,2)\) with coefficient \(1\) and from \((1,3)\) with coefficient \(2\).
Each choice produces one increasing family until the next term either fails to increase or exceeds \(N\). If that family has \(t\) terms, then it contributes \(C(t)\).
Examples include
$$1,2,3,5,8,\dots$$
from the plus branch with coefficient \(1\), and
$$1,m,m^2-1,m^3-2m,\dots$$
from the minus branch with seed \((1,m)\).
Besides the recurrence families, the implementations add one hybrid chain
$$1,2,6,18,54,\dots$$
whose tail is geometric with ratio \(3\). If this chain has \(t\) terms up to \(N\), only the subsequences that still contain the leading \(1\) are new, because every later window is already an ordinary geometric progression. Hence the hybrid contribution is
$$t-4$$
rather than \(C(t)\).
Finally there are ten isolated sporadic sequences of length exactly \(5\). Each contributes \(1\) once its last term is at most \(N\). That is why the implementations only need the ten terminal values of those exceptions.
The check value \(G(10)=26\) can be reconstructed directly from the family decomposition.
The consecutive family contributes
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
The geometric block contributes nothing because the shortest possible nontrivial numerator base already gives \(2^4=16\gt 10\).
Among the recurrence families, only
$$1,2,3,5,8$$
reaches length \(5\) under the bound \(10\), so this contributes \(1\).
The hybrid chain starts with \(1,2,6,18,\dots\), so it is still too short at \(N=10\).
Among the ten sporadic exceptions, four have last term at most \(10\). Therefore
$$G(10)=21+0+1+0+4=26,$$
which matches the implementation check exactly.
The C++, Python, and Java implementations all follow the same pipeline. First they compute \(R=\lfloor N^{1/4}\rfloor\) carefully, correcting the floating-point estimate so that \(R^4\le N\lt (R+1)^4\). Next they add the consecutive-family contribution \(C(N)\).
Then they build a totient table up to \(R\) and evaluate the geometric sum
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
After that, they iterate through every admissible recurrence coefficient and seed pair, generate terms until monotonic growth stops or the next term exceeds \(N\), and add \(C(t)\) for the resulting family length \(t\). The hybrid chain and the ten sporadic corrections are appended at the end. All arithmetic is reduced modulo \(10^9+7\) after each accumulation step. The C++ implementation parallelizes the geometric summation across numerator ranges, while the Python and Java implementations evaluate the same formula serially.
Let \(R=\lfloor N^{1/4}\rfloor\). Computing the totient table costs \(O(R\log\log R)\) time and \(O(R)\) memory. The geometric double sum visits all powers \(u^e\le N\), so its total work is also near \(O(R\log\log R)\). The recurrence families are enumerated only for coefficients up to \(R\), and each family grows exponentially, so the total recurrence work is well bounded by \(O(R\log N)\) in practice. The hybrid and sporadic parts are constant-time. Overall the method uses \(O(R)\) memory and runs close to fourth-root complexity rather than depending linearly on \(N\).
Sei \(G(N)\) die Anzahl streng wachsender Folgen positiver ganzer Zahlen
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
für die jedes innere Tripel fast geometrisch ist, also
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1).$$
Gesucht ist \(G(10^{18})\bmod (10^9+7)\). Eine direkte Suche ist unmöglich, daher zerlegen die Implementierungen alle zulässigen Folgen in einige unendliche Familien und eine endliche Liste kurzer Ausnahmen.
Die Größe
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
misst, wie weit ein Tripel von einer exakten geometrischen Progression entfernt ist. Für echte geometrische Folgen gilt \(\Delta_i=0\); hier sind nur die Werte \(-2,-1,0,1,2\) erlaubt.
Eine Folge ist genau dann zulässig, wenn für jeden inneren Index
$$\Delta_i\in\{-2,-1,0,1,2\}$$
gilt. Diese scheinbar schwache Bedingung ist in Wahrheit sehr starr. Die Klassifikation hinter der Lösung zeigt, dass lange Folgen nur in wenigen festen Mustern auftreten. Darum zählt das Programm Familien statt einzelner Folgen.
Hat eine maximale Familie \(t\) gültige Glieder, dann ist die Zahl ihrer zusammenhängenden Teilfolgen der Länge mindestens \(5\)
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
Das ist einfach die Summe
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
denn für jede erlaubte Länge \(\ell\) gibt es \(t-\ell+1\) Fenster.
Für jeden Block
$$s,s+1,s+2,\dots,s+\ell-1$$
gilt in jedem inneren Tripel
$$ (x+1)^2-x(x+2)=1. $$
Also ist jeder zusammenhängende Block aufeinanderfolgender Zahlen zulässig. Alle diese Blöcke liegen in der Masterkette
$$1,2,3,\dots,N,$$
die \(N\) Glieder besitzt. Ihr Gesamtbeitrag ist daher
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
Genau das erzeugt den quadratischen Grundterm der Lösung.
Ist der Defekt überall \(0\), dann haben wir eine exakte geometrische Progression. Jede wachsende ganzzahlige geometrische Folge der Länge \(e+1\) besitzt eindeutig die Form
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
wobei
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
Für festes \(u\) gibt es genau \(\varphi(u)\) zulässige Nenner \(q\) mit \(1\le q\lt u\) und \(\gcd(u,q)=1\). Der letzte Term ist \(c\,u^e\), also folgt aus \(a_t\le N\)
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
Damit ergibt sich der geometrische Gesamtbeitrag zu
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
Die vierte Wurzel tritt auf, weil bereits die kürzeste zulässige geometrische Folge Länge \(5\) hat und somit \(u^4\le N\) gelten muss.
Nach Ausschluss des exakten geometrischen Falls bleiben lange Familien übrig, die durch Rekurrenzen zweiter Ordnung erzeugt werden:
$$a_{n+1}=m a_n-a_{n-1},$$
oder
$$a_{n+1}=m a_n+a_{n-1}.$$
Die generischen Äste beginnen mit \((1,m)\). Zusätzlich gibt es zwei Minus-Äste mit Start \((1,2)\) und Koeffizient \(3\) bzw. mit Start \((1,3)\) und Koeffizient \(4\), sowie zwei Plus-Äste mit Start \((1,2)\) und Koeffizient \(1\) bzw. mit Start \((1,3)\) und Koeffizient \(2\).
Jede Wahl erzeugt genau eine wachsende Familie, bis der nächste Term nicht mehr wächst oder \(N\) überschreitet. Besitzt die Familie \(t\) Glieder, so trägt sie \(C(t)\) bei.
Beispiele sind
$$1,2,3,5,8,\dots$$
aus dem Plus-Zweig mit Koeffizient \(1\), sowie
$$1,m,m^2-1,m^3-2m,\dots$$
aus dem generischen Minus-Zweig.
Neben den Rekurrenzfamilien kommt noch die Hybridkette
$$1,2,6,18,54,\dots$$
hinzu, deren Schwanz eine geometrische Progression mit Quotienten \(3\) ist. Hat diese Kette bis \(N\) genau \(t\) Glieder, dann sind nur diejenigen Teilfolgen neu, die noch die führende \(1\) enthalten, denn jedes spätere Fenster ist bereits eine gewöhnliche geometrische Folge. Deshalb ist ihr Beitrag
$$t-4$$
statt \(C(t)\).
Schließlich gibt es zehn isolierte sporadische Folgen der Länge genau \(5\). Jede davon trägt \(1\) bei, sobald ihr letzter Term höchstens \(N\) ist. Darum genügt in der Implementierung die Liste der zehn Endwerte.
Der Kontrollwert \(G(10)=26\) lässt sich direkt aus der Familienzerlegung gewinnen.
Die Familie der aufeinanderfolgenden Zahlen liefert
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
Der geometrische Block liefert nichts, weil bereits \(2^4=16\gt 10\) ist.
Unter den Rekurrenzfamilien erreicht nur
$$1,2,3,5,8$$
unter der Schranke \(10\) überhaupt Länge \(5\), also kommt \(1\) hinzu.
Die Hybridkette beginnt mit \(1,2,6,18,\dots\) und ist für \(N=10\) noch zu kurz.
Von den zehn sporadischen Ausnahmen haben vier einen Endwert \(\le 10\). Also gilt
$$G(10)=21+0+1+0+4=26,$$
genau wie im Prüfwert der Implementierung.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Pipeline. Zuerst wird \(R=\lfloor N^{1/4}\rfloor\) robust bestimmt, wobei die anfängliche Gleitkomma-Näherung nachkorrigiert wird, bis \(R^4\le N\lt (R+1)^4\) gilt. Danach wird der Beitrag der aufeinanderfolgenden Zahlen \(C(N)\) addiert.
Anschließend wird eine Totiententabelle bis \(R\) aufgebaut und die geometrische Summe
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor$$
ausgewertet. Danach durchläuft das Programm alle zulässigen Rekurrenzkoeffizienten und Startpaare, erzeugt Terme solange die Folge streng wächst und unterhalb von \(N\) bleibt, und addiert für die gefundene Länge \(t\) den Wert \(C(t)\). Zum Schluss kommen die Hybridfamilie und die zehn sporadischen Korrekturen hinzu. Jede Aufsummierung wird sofort modulo \(10^9+7\) reduziert. Die C++-Version parallelisiert nur die geometrische Summe; die zugrunde liegende Mathematik ist in allen drei Sprachen identisch.
Mit \(R=\lfloor N^{1/4}\rfloor\) kostet die Berechnung der Totiententabelle \(O(R\log\log R)\) Zeit und \(O(R)\) Speicher. Die geometrische Doppelsumme besucht alle Potenzen \(u^e\le N\) und bleibt daher ebenfalls in der Größenordnung \(O(R\log\log R)\). Die Rekurrenzfamilien werden nur für Koeffizienten bis \(R\) untersucht, und jede Familie wächst exponentiell, sodass der Gesamtaufwand praktisch gut durch \(O(R\log N)\) begrenzt ist. Hybrid- und Sporadikteil haben konstanten Aufwand. Insgesamt arbeitet die Methode also mit \(O(R)\) Speicher und näherungsweise vierter-Wurzel-Komplexität in \(N\).
\(G(N)\),
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
koşulunu sağlayan ve her iç üçlüsünde
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1)$$
olan artan pozitif tamsayı dizilerinin sayısıdır. İstenen değer \(G(10^{18})\bmod (10^9+7)\) olduğundan doğrudan tarama imkansızdır. Bu yüzden implementasyonlar tek tek dizileri değil, bütün geçerli aileleri sayar.
Burada
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
ifadesi, ilgili üçlünün tam bir geometrik üçlüden ne kadar saptığını ölçer. Gerçek geometrik dizilerde \(\Delta_i=0\) olur; bu problemde yalnızca \(-2,-1,0,1,2\) değerlerine izin verilir.
Bir dizi ancak ve ancak her iç indeks için
$$\Delta_i\in\{-2,-1,0,1,2\}$$
sağlıyorsa uygundur. Bu koşul ilk bakışta gevşek görünse de aslında çok kısıtlayıcıdır. Çözümün dayandığı sınıflandırma, uzun dizilerin sadece birkaç katı kalıba düştüğünü gösterir. Bu nedenle program adayları değil aileleri sayar.
Eğer bir maksimum aile içinde \(t\) geçerli terim varsa, uzunluğu en az \(5\) olan ardışık alt dizilerin sayısı
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5 \end{cases}$$
olur. Bunun nedeni
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1)$$
eşitliğidir; çünkü her \(\ell\) uzunluğu için \(t-\ell+1\) adet pencere vardır.
Herhangi bir
$$s,s+1,s+2,\dots,s+\ell-1$$
bloğu için, iç üçlülerde
$$ (x+1)^2-x(x+2)=1 $$
elde edilir. Yani ardışık sayılardan oluşan her blok uygundur. Bütün bu bloklar
$$1,2,3,\dots,N$$
ana zincirinin içindeki ardışık pencereler olarak görülebilir. Bu zincirin katkısı doğrudan
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5)$$
olur. Koddaki kuadratik temel terim buradan gelir.
Eğer sapma her yerde \(0\) ise elimizde tam bir geometrik ilerleme vardır. Uzunluğu \(e+1\) olan her artan tam sayılı geometrik dizi tekil olarak
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e$$
şeklinde yazılabilir; burada
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
Sabit bir \(u\) için, \(1\le q\lt u\) ve \(\gcd(u,q)=1\) koşullarını sağlayan tam olarak \(\varphi(u)\) farklı payda vardır. Son terim \(c\,u^e\) olduğundan üst sınır
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor$$
olur. Böylece geometrik katkı
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor$$
şeklindedir. Dördüncü dereceden kök sınırı, en kısa uygun geometrik dizinin bile \(5\) terimli olmasından gelir.
Gerçek geometrik durum çıkarıldığında, geriye ikinci dereceden şu iki rekürans tipinden biriyle üretilen uzun aileler kalır:
$$a_{n+1}=m a_n-a_{n-1},$$
veya
$$a_{n+1}=m a_n+a_{n-1}.$$
Genel dallar \((1,m)\) ile başlar. Ayrıca eksi tipinde \((1,2)\) başlangıçlı katsayısı \(3\) olan ve \((1,3)\) başlangıçlı katsayısı \(4\) olan iki özel dal; artı tipinde ise \((1,2)\) başlangıçlı katsayısı \(1\) olan ve \((1,3)\) başlangıçlı katsayısı \(2\) olan iki özel dal daha vardır.
Her seçim, bir sonraki terim artık artmıyorsa ya da \(N\)'yi aşıyorsa durdurulan tek bir artan aile üretir. Aile uzunluğu \(t\) ise katkısı \(C(t)\) olur.
Örneğin
$$1,2,3,5,8,\dots$$
artı tipindeki özel daldan gelir; buna karşılık
$$1,m,m^2-1,m^3-2m,\dots$$
eksi tipindeki genel ailenin kapalı başlangıcıdır.
Rekürans ailelerinin dışında bir de
$$1,2,6,18,54,\dots$$
hibrit zinciri vardır. Bu zincirin kuyruğu oranı \(3\) olan geometrik bir dizidir. Eğer bu zincir \(N\) sınırına kadar \(t\) terim içeriyorsa, yalnızca baştaki \(1\)'i içeren alt diziler yenidir; daha sonra başlayan her pencere zaten geometrik blok içinde sayılmıştır. Bu nedenle hibrit katkı
$$t-4$$
olur; \(C(t)\) değil.
Son olarak tam \(5\) terimli on adet izole sporadik dizi vardır. Bunların her biri, son terimi \(N\)'yi geçmediği anda \(1\) katkı verir. Bu yüzden implementasyonun bu kısım için yalnızca on son değeri saklaması yeterlidir.
Kontrol değeri olan \(G(10)=26\), aile ayrışımından doğrudan elde edilebilir.
Ardışık sayılar ailesi
$$C(10)=\frac{(10-4)(10-3)}{2}=21$$
katkısı verir.
Geometrik blokta katkı yoktur; çünkü mümkün olan en küçük anlamlı taban için bile \(2^4=16\gt 10\).
Rekürans aileleri içinde, \(10\) sınırı altında uzunluğu \(5\)'e ulaşan tek örnek
$$1,2,3,5,8$$
olduğu için buradan \(1\) gelir.
Hibrit zincir \(1,2,6,18,\dots\) şeklinde başladığından \(N=10\) için henüz yeterince uzun değildir.
On sporadik istisnanın dördünün son terimi \(10\) veya daha küçüktür. Dolayısıyla
$$G(10)=21+0+1+0+4=26$$
elde edilir; bu da uygulamadaki kontrol sonucu ile aynıdır.
C++, Python ve Java implementasyonları aynı hesap akışını izler. Önce \(R=\lfloor N^{1/4}\rfloor\) değeri güvenli biçimde bulunur; ilk kayan nokta tahmini, \(R^4\le N\lt (R+1)^4\) kesinleşene kadar düzeltilir. Sonra ardışık tamsayı ailesinin katkısı olan \(C(N)\) eklenir.
Daha sonra \(R\)'ye kadar bir totient tablosu üretilir ve
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor$$
toplamı hesaplanır. Bunun ardından tüm izinli rekürans katsayıları ve başlangıç çiftleri denenir; terimler, sıra artmayı bıraktığında ya da bir sonraki terim \(N\)'yi aştığında durdurulur ve elde edilen aile uzunluğu \(t\) için \(C(t)\) eklenir. Hibrit zincir ve on sporadik düzeltme son aşamada ilave edilir. Her toplama adımında \(10^9+7\) moduna indirgeme yapılır. C++ sürümü geometrik toplamı iş parçacıklarına böler; Python ve Java aynı formülü seri olarak uygular.
\(R=\lfloor N^{1/4}\rfloor\) olsun. Totient tablosu \(O(R\log\log R)\) zamanda ve \(O(R)\) bellekte kurulur. Geometrik çift toplam, \(u^e\le N\) olan tüm kuvvetleri ziyaret ettiği için yine yaklaşık \(O(R\log\log R)\) düzeyindedir. Rekürans aileleri yalnızca \(R\)'ye kadar katsayılarda incelenir ve her aile üstel büyüdüğü için toplam iş yükü pratikte \(O(R\log N)\) ile rahatça sınırlanır. Hibrit ve sporadik bölümler sabit zamanlıdır. Sonuç olarak yöntem \(O(R)\) bellek kullanır ve \(N\)'ye doğrusal değil, yaklaşık dördüncü dereceden kök ölçeğinde çalışır.
Sea \(G(N)\) el número de secuencias crecientes de enteros positivos
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
tales que cada triple interior sea casi geométrico, es decir,
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1).$$
Hay que calcular \(G(10^{18})\bmod (10^9+7)\). Como la enumeración directa es imposible, las implementaciones clasifican todas las secuencias válidas en unas pocas familias infinitas y una lista finita de excepciones cortas.
La cantidad
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
mide cuánto se desvía un triple de una progresión geométrica exacta. En una progresión geométrica real se cumple \(\Delta_i=0\); aquí solo se admiten los valores \(-2,-1,0,1,2\).
Una secuencia es válida exactamente cuando, para todo índice interior,
$$\Delta_i\in\{-2,-1,0,1,2\}.$$
Aunque la cota parece pequeña, impone una rigidez fuerte. La clasificación matemática empleada por la solución muestra que las secuencias largas no aparecen de forma caótica: caen en unas pocas familias deterministas. Por eso el programa cuenta familias completas en lugar de probar candidatos individuales.
Si una familia máxima contiene \(t\) términos válidos, entonces el número de subsecuencias contiguas de longitud al menos \(5\) es
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
Esto no es más que la suma
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
porque para cada longitud \(\ell\) hay \(t-\ell+1\) ventanas posibles.
Para cualquier bloque
$$s,s+1,s+2,\dots,s+\ell-1,$$
cada triple interior satisface
$$ (x+1)^2-x(x+2)=1. $$
Así, cualquier bloque de enteros consecutivos es admisible. Todos esos bloques están contenidos en la cadena maestra
$$1,2,3,\dots,N,$$
que tiene \(N\) términos, de modo que su contribución total es
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
Ese es el término base cuadrático de la solución.
Si el defecto vale siempre \(0\), entonces la secuencia es una progresión geométrica exacta. Toda progresión geométrica creciente de enteros de longitud \(e+1\) puede escribirse de manera única como
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
donde
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
Para un numerador fijo \(u\), hay exactamente \(\varphi(u)\) denominadores \(q\) con \(1\le q\lt u\) y \(\gcd(u,q)=1\). El último término es \(c\,u^e\), así que la restricción \(a_t\le N\) obliga a
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
Por tanto, la contribución geométrica total es
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
El corte en la cuarta raíz aparece porque la secuencia geométrica válida más corta ya tiene longitud \(5\), así que necesariamente \(u^4\le N\).
Una vez separadas las progresiones geométricas exactas, las demás familias largas quedan descritas por recurrencias de segundo orden de una de estas dos formas:
$$a_{n+1}=m a_n-a_{n-1},$$
o bien
$$a_{n+1}=m a_n+a_{n-1}.$$
Las ramas genéricas arrancan en \((1,m)\). Además hay dos ramas extra del tipo menos, con inicio \((1,2)\) y coeficiente \(3\), y con inicio \((1,3)\) y coeficiente \(4\); y dos ramas extra del tipo más, con inicio \((1,2)\) y coeficiente \(1\), y con inicio \((1,3)\) y coeficiente \(2\).
Cada elección produce una única familia creciente hasta que el siguiente término deja de crecer o supera \(N\). Si esa familia tiene \(t\) términos, aporta \(C(t)\).
Por ejemplo,
$$1,2,3,5,8,\dots$$
sale de la rama de suma con coeficiente \(1\), mientras que
$$1,m,m^2-1,m^3-2m,\dots$$
aparece en la rama genérica de resta.
Además de las familias recursivas, las implementaciones añaden la cadena híbrida
$$1,2,6,18,54,\dots$$
cuyo tramo final es geométrico con razón \(3\). Si esta cadena tiene \(t\) términos por debajo de \(N\), solo son nuevas las subsecuencias que todavía contienen el \(1\) inicial, porque cualquier ventana posterior ya es una progresión geométrica ordinaria. Por eso la contribución híbrida es
$$t-4$$
en lugar de \(C(t)\).
Por último, hay diez secuencias esporádicas aisladas de longitud exactamente \(5\). Cada una aporta \(1\) cuando su último término no supera \(N\). Esa es la razón de que la implementación solo necesite almacenar los diez valores finales.
El valor de comprobación \(G(10)=26\) se reconstruye fácilmente a partir de la descomposición por familias.
La familia de enteros consecutivos aporta
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
El bloque geométrico no aporta nada porque ya \(2^4=16\gt 10\).
Entre las familias recursivas, solo
$$1,2,3,5,8$$
alcanza longitud \(5\) bajo la cota \(10\), así que suma \(1\).
La cadena híbrida empieza como \(1,2,6,18,\dots\), de modo que para \(N=10\) todavía es demasiado corta.
De las diez excepciones esporádicas, cuatro tienen último término \(\le 10\). Luego
$$G(10)=21+0+1+0+4=26,$$
en perfecto acuerdo con la comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen la misma secuencia de pasos. Primero calculan \(R=\lfloor N^{1/4}\rfloor\) con correcciones explícitas para garantizar que \(R^4\le N\lt (R+1)^4\). Después añaden la contribución base de la familia consecutiva, \(C(N)\).
A continuación construyen una tabla de totientes hasta \(R\) y evalúan la suma geométrica
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
Luego recorren todos los coeficientes y semillas permitidos para las recurrencias, generan términos mientras la sucesión siga siendo estrictamente creciente y el siguiente término no exceda \(N\), y añaden \(C(t)\) para la longitud obtenida \(t\). Finalmente incorporan la familia híbrida y las diez correcciones esporádicas. Cada acumulación se reduce módulo \(10^9+7\). La versión en C++ paraleliza únicamente la suma geométrica; la fórmula matemática es la misma en los tres lenguajes.
Sea \(R=\lfloor N^{1/4}\rfloor\). La tabla de totientes cuesta \(O(R\log\log R)\) tiempo y \(O(R)\) memoria. La doble suma geométrica recorre todas las potencias \(u^e\le N\), así que también se mantiene cerca de \(O(R\log\log R)\). Las familias recursivas solo se exploran para coeficientes hasta \(R\), y como cada familia crece exponencialmente, el trabajo total queda bien acotado en la práctica por \(O(R\log N)\). Las partes híbrida y esporádica son de costo constante. En conjunto, el método usa \(O(R)\) memoria y escala aproximadamente con la cuarta raíz de \(N\), no con \(N\) mismo.
设 \(G(N)\) 表示所有严格递增正整数序列
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
中满足每个内部三元组都“近似几何”的个数，也就是对所有 \(2\le i\le t-1\) 都有
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2.$$
题目要求的是 \(G(10^{18})\bmod (10^9+7)\)。由于上界极大，绝不可能逐个枚举序列，因此实现采用的是“先做结构分类，再按家族计数”的办法。
定义局部偏差量
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}.$$
如果一个三元组正好构成几何级数，那么 \(\Delta_i=0\)。本题允许的只是很小的偏差，所以 \(\Delta_i\) 只能取 \(-2,-1,0,1,2\) 这五个值。
序列可行，当且仅当每个内部位置都满足
$$\Delta_i\in\{-2,-1,0,1,2\}.$$
这个条件看起来只是一个很小的误差范围，但它实际上非常刚性。实现所依据的数学分类说明：足够长的合法序列不会随意变化，而是必然落入少数几个固定家族中。也正因为如此，程序真正做的是“计家族”，而不是“试候选”。
如果某个极大合法家族一共包含 \(t\) 个项，那么它内部所有长度至少为 \(5\) 的连续子序列个数为
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
这是因为
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
对于每个固定长度 \(\ell\)，都有 \(t-\ell+1\) 个连续窗口。
考虑任意长度为 \(\ell\) 的连续整数块
$$s,s+1,s+2,\dots,s+\ell-1.$$
对其中任意内部三元组，都有
$$ (x+1)^2-x(x+2)=1. $$
因此，任何连续整数块都是合法的。所有这类块都包含在主链
$$1,2,3,\dots,N$$
的连续窗口中。由于这条主链有 \(N\) 项，所以它的总贡献就是
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
这正是实现里那个显眼的二次主项。
如果整条序列的偏差始终为 \(0\)，那么它就是一条真正的几何级数。任意一个长度为 \(e+1\) 的递增整数几何级数，都可以唯一写成
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
其中
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
这里 \(u/q\) 是化到最简后的公比。对固定的分子 \(u\)，满足 \(1\le q\lt u\) 且与 \(u\) 互素的分母个数恰好是 \(\varphi(u)\)。最后一项等于 \(c\,u^e\)，于是由 \(a_t\le N\) 得到
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
因此几何部分的总贡献是
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
为什么上界是四次根？因为合法序列最短也要有 \(5\) 项，所以最小长度对应的指数已经是 \(4\)，于是必须满足 \(u^4\le N\)。
去掉精确几何级数之后，剩下的长家族可以归结为两类二阶递推：
$$a_{n+1}=m a_n-a_{n-1},$$
或者
$$a_{n+1}=m a_n+a_{n-1}.$$
通用分支都从 \((1,m)\) 开始。除此之外，还需要四个额外分支来覆盖剩余的合法情形：减号型里有起点 \((1,2)\)、系数 \(3\) 的分支，以及起点 \((1,3)\)、系数 \(4\) 的分支；加号型里有起点 \((1,2)\)、系数 \(1\) 的分支，以及起点 \((1,3)\)、系数 \(2\) 的分支。
每一种选择都会生成一条严格递增链，直到下一项不再变大，或者已经超过 \(N\) 为止。如果该家族一共走出了 \(t\) 项，那么它的贡献就是 \(C(t)\)。
例如
$$1,2,3,5,8,\dots$$
来自加号型、系数为 \(1\) 的特殊分支；而
$$1,m,m^2-1,m^3-2m,\dots$$
则是减号型通用分支的起始展开。
除了上述递推家族之外，实现还专门加入了混合链
$$1,2,6,18,54,\dots$$
它从第二步之后开始就变成了公比为 \(3\) 的几何级数。如果这条链在上界 \(N\) 内共有 \(t\) 项，那么真正“新增”的只有那些仍然包含最前面那个 \(1\) 的连续子序列，因为后面开始的任何窗口都已经被几何部分计算过了。所以它的贡献不是 \(C(t)\)，而是
$$t-4.$$
最后还存在十个长度恰好为 \(5\) 的离散例外序列。只要它们的最后一项不超过 \(N\)，每个就贡献 \(1\)。这也是为什么实现只需要保存这十个例外的末项。
代码中的校验值 \(G(10)=26\) 可以完全由上面的分解重建出来。
连续整数主家族贡献
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
几何部分没有贡献，因为最小可能的底数已经满足 \(2^4=16\gt 10\)。
在递推家族中，只有
$$1,2,3,5,8$$
这一条在上界 \(10\) 内能够达到长度 \(5\)，因此再加 \(1\)。
混合链是 \(1,2,6,18,\dots\)，所以在 \(N=10\) 时还不够长。
十个离散例外里，有四个的末项不超过 \(10\)。于是
$$G(10)=21+0+1+0+4=26,$$
和实现中的校验结果完全一致。
C++、Python 和 Java 三份实现遵循同一条计算流程。首先求出 \(R=\lfloor N^{1/4}\rfloor\)，并对初始浮点估计做修正，确保最终满足 \(R^4\le N\lt (R+1)^4\)。然后先加入连续整数主家族的贡献 \(C(N)\)。
接下来构造到 \(R\) 为止的欧拉函数表，并计算几何部分
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
之后程序遍历所有允许的递推系数和起始对，逐项生成序列；一旦下一项不再严格增大，或者超过 \(N\)，就停止，并按得到的长度 \(t\) 加上 \(C(t)\)。最后再补上混合链贡献以及十个离散例外。每次累加后都立即对 \(10^9+7\) 取模。C++ 版本只是在几何求和部分做了并行切分；三种语言使用的是同一套数学公式。
记 \(R=\lfloor N^{1/4}\rfloor\)。构造欧拉函数表需要 \(O(R\log\log R)\) 时间和 \(O(R)\) 空间。几何双重求和会访问所有满足 \(u^e\le N\) 的幂，因此总体量级也接近 \(O(R\log\log R)\)。递推家族只需要枚举到 \(R\) 为止的系数，而每条家族都呈指数增长，所以这部分在实践中可以很好地控制在 \(O(R\log N)\) 以内。混合链和离散例外都是常数级开销。整体上，这个方法只用 \(O(R)\) 空间，时间复杂度也接近 \(N\) 的四次根，而不是与 \(N\) 线性相关。
Пусть \(G(N)\) обозначает число строго возрастающих последовательностей положительных целых чисел
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
для которых каждый внутренний тройной блок почти геометричен, то есть
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1).$$
Требуется найти \(G(10^{18})\bmod (10^9+7)\). Полный перебор невозможен, поэтому реализации используют структурную классификацию: все допустимые последовательности раскладываются на несколько бесконечных семейств и конечный набор коротких исключений.
Величина
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
показывает, насколько тройка отклоняется от точной геометрической прогрессии. Для настоящей геометрической прогрессии \(\Delta_i=0\); в данной задаче разрешены только значения \(-2,-1,0,1,2\).
Последовательность допустима тогда и только тогда, когда для каждого внутреннего индекса выполняется
$$\Delta_i\in\{-2,-1,0,1,2\}.$$
Это очень жесткое условие. Классификация, на которой основана реализация, показывает, что длинные решения не возникают хаотично: они обязательно попадают в несколько заранее известных шаблонов. Именно поэтому программа считает семейства, а не отдельные последовательности.
Если максимальное семейство содержит \(t\) допустимых членов, то число его непрерывных подпоследовательностей длины не меньше \(5\) равно
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
Это просто сумма
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
потому что для каждой длины \(\ell\) существует \(t-\ell+1\) непрерывных окон.
Для любого блока
$$s,s+1,s+2,\dots,s+\ell-1$$
каждая внутренняя тройка удовлетворяет равенству
$$ (x+1)^2-x(x+2)=1. $$
Значит, любой блок последовательных целых чисел допустим. Все такие блоки содержатся в базовой цепочке
$$1,2,3,\dots,N,$$
у которой \(N\) членов, поэтому ее общий вклад равен
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
Именно отсюда возникает квадратичный основной вклад решения.
Если дефект везде равен нулю, то последовательность является точной геометрической прогрессией. Любая возрастающая целочисленная геометрическая прогрессия длины \(e+1\) единственным образом записывается как
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
где
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
Для фиксированного числителя \(u\) существует ровно \(\varphi(u)\) допустимых знаменателей \(q\) с условиями \(1\le q\lt u\) и \(\gcd(u,q)=1\). Последний член равен \(c\,u^e\), поэтому из ограничения \(a_t\le N\) следует
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
Отсюда суммарный геометрический вклад имеет вид
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
Предел по четвертой степени корня возникает потому, что даже самая короткая допустимая геометрическая прогрессия уже имеет длину \(5\), а значит должно выполняться \(u^4\le N\).
После исключения точного геометрического случая остаются длинные семейства, порождаемые рекуррентными соотношениями второго порядка одного из двух видов:
$$a_{n+1}=m a_n-a_{n-1},$$
или
$$a_{n+1}=m a_n+a_{n-1}.$$
Типичные ветви стартуют с \((1,m)\). Кроме того, есть две дополнительные ветви типа с минусом: с началом \((1,2)\) и коэффициентом \(3\), а также с началом \((1,3)\) и коэффициентом \(4\); и две дополнительные ветви типа с плюсом: с началом \((1,2)\) и коэффициентом \(1\), а также с началом \((1,3)\) и коэффициентом \(2\).
Каждый такой выбор дает одну возрастающую цепочку, пока следующий член не перестает расти или не превышает \(N\). Если получено \(t\) членов, вклад семейства равен \(C(t)\).
Например,
$$1,2,3,5,8,\dots$$
появляется в плюсовой ветви с коэффициентом \(1\), а
$$1,m,m^2-1,m^3-2m,\dots$$
получается из общей минусовой ветви.
Помимо рекуррентных семейств, в реализациях отдельно учитывается гибридная цепочка
$$1,2,6,18,54,\dots$$
ее хвост уже является геометрической прогрессией с отношением \(3\). Если эта цепочка дает \(t\) членов, не превосходящих \(N\), то новыми являются только те подпоследовательности, которые все еще содержат начальную \(1\), потому что любое окно, начинающееся позже, уже попало в геометрический блок. Поэтому гибридный вклад равен
$$t-4$$
вместо \(C(t)\).
Наконец, существует десять изолированных спорадических последовательностей длины ровно \(5\). Каждая добавляет \(1\), как только ее последний член не превосходит \(N\). Поэтому реализации достаточно хранить только десять конечных значений этих исключений.
Проверочное значение \(G(10)=26\) полностью восстанавливается из семейной декомпозиции.
Базовое семейство последовательных чисел дает
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
Геометрический блок ничего не дает, поскольку уже \(2^4=16\gt 10\).
Среди рекуррентных семейств только
$$1,2,3,5,8$$
достигает длины \(5\) при верхней границе \(10\), значит отсюда приходит \(1\).
Гибридная цепочка начинается как \(1,2,6,18,\dots\), поэтому при \(N=10\) она еще слишком коротка.
Из десяти спорадических исключений четыре имеют последний член \(\le 10\). Следовательно,
$$G(10)=21+0+1+0+4=26,$$
что точно совпадает с контрольным значением реализации.
Реализации на C++, Python и Java идут по одной и той же схеме. Сначала аккуратно вычисляется \(R=\lfloor N^{1/4}\rfloor\), причем начальная вещественная оценка исправляется до тех пор, пока не будет гарантировано \(R^4\le N\lt (R+1)^4\). Затем добавляется вклад базового семейства последовательных чисел \(C(N)\).
После этого строится таблица значений функции Эйлера до \(R\) и вычисляется геометрическая сумма
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
Далее перебираются все допустимые коэффициенты и стартовые пары для рекуррентных ветвей; члены генерируются, пока последовательность строго возрастает и следующий член не превосходит \(N\), а затем по найденной длине \(t\) добавляется \(C(t)\). В конце прибавляются гибридная цепочка и десять спорадических поправок. После каждого суммирования выполняется взятие по модулю \(10^9+7\). В версии на C++ геометрическая сумма распараллелена, но сама формула во всех трех языках одинакова.
Пусть \(R=\lfloor N^{1/4}\rfloor\). Построение таблицы функции Эйлера занимает \(O(R\log\log R)\) времени и \(O(R)\) памяти. Геометрическая двойная сумма перебирает все степени \(u^e\le N\), поэтому ее трудоемкость также остается порядка \(O(R\log\log R)\). Рекуррентные семейства рассматриваются только для коэффициентов до \(R\), а каждая такая цепочка растет экспоненциально, так что суммарная работа на практике хорошо ограничена величиной \(O(R\log N)\). Гибридная и спорадическая части требуют лишь постоянного времени. В итоге метод использует \(O(R)\) памяти и имеет масштаб примерно четвертого корня из \(N\), а не линейный по \(N\).
لتكن \(G(N)\) هي عدد المتتاليات المتزايدة من الأعداد الصحيحة الموجبة
$$a_1\lt a_2\lt \cdots\lt a_t\le N,\qquad t\ge 5.$$
التي تحقق أن كل ثلاثية داخلية شبه هندسية، أي
$$\left|a_i^2-a_{i-1}a_{i+1}\right|\le 2\qquad (2\le i\le t-1).$$
المطلوب هو حساب \(G(10^{18})\bmod (10^9+7)\). ولأن التعداد المباشر غير ممكن عند هذا الحد الكبير، فإن التنفيذات تعتمد على تصنيف جميع المتتاليات المقبولة إلى عدد صغير من العائلات اللانهائية مع مجموعة من الاستثناءات القصيرة المنتهية.
الكمية
$$\Delta_i=a_i^2-a_{i-1}a_{i+1}$$
تقيس مقدار ابتعاد الثلاثية عن كونها متتالية هندسية تامة. في المتتالية الهندسية الحقيقية يكون \(\Delta_i=0\)، أما هنا فالقيم المسموح بها فقط هي \(-2,-1,0,1,2\).
تكون المتتالية مقبولة إذا وفقط إذا تحقق لكل موضع داخلي أن
$$\Delta_i\in\{-2,-1,0,1,2\}.$$
هذا الشرط يبدو محدودًا فقط، لكنه في الحقيقة شديد التقييد. التصنيف الرياضي الذي تعتمد عليه الحلول يبين أن المتتاليات الطويلة لا تتصرف بحرية، بل تقع داخل عدد قليل من الأنماط الصارمة. لذلك فالبرنامج لا يعد المرشحين واحدًا واحدًا، بل يعد العائلات الكاملة.
إذا كانت عائلة قصوى تحتوي على \(t\) حدود صالحة، فإن عدد المقاطع المتجاورة ذات الطول على الأقل \(5\) داخلها يساوي
$$C(t)=\begin{cases} \dfrac{(t-4)(t-3)}{2}, & t\ge 5,\\ 0, & t\lt 5. \end{cases}$$
وذلك لأن
$$C(t)=\sum_{\ell=5}^{t}(t-\ell+1),$$
إذ يوجد لكل طول \(\ell\) عدد مقداره \(t-\ell+1\) من النوافذ المتجاورة.
إذا أخذنا أي مقطع من الشكل
$$s,s+1,s+2,\dots,s+\ell-1,$$
فإن كل ثلاثية داخلية تحقق
$$ (x+1)^2-x(x+2)=1. $$
لذلك فكل مقطع من أعداد متتالية هو مقطع مقبول. وجميع هذه المقاطع موجودة داخل السلسلة الرئيسية
$$1,2,3,\dots,N,$$
التي تحتوي على \(N\) حدود، وبالتالي تكون مساهمتها الكلية
$$C(N)=\frac{(N-4)(N-3)}{2}\qquad (N\ge 5).$$
ومن هنا يظهر الحد التربيعي الأساسي في الحل.
إذا كان العيب المحلي يساوي الصفر دائمًا، فالمتتالية هندسية تمامًا. وكل متتالية هندسية متزايدة من الأعداد الصحيحة طولها \(e+1\) يمكن كتابتها بصورة وحيدة على الشكل
$$c\,q^e,\ c\,q^{e-1}u,\ c\,q^{e-2}u^2,\ \dots,\ c\,u^e,$$
حيث
$$u\gt q\ge 1,\qquad \gcd(u,q)=1,\qquad e\ge 4,\qquad c\ge 1.$$
بالنسبة إلى بسط ثابت \(u\)، يوجد بالضبط \(\varphi(u)\) اختيارًا ممكنًا للمقام \(q\) مع الشرطين \(1\le q\lt u\) و \(\gcd(u,q)=1\). والحد الأخير يساوي \(c\,u^e\)، ومن ثم يعطي الشرط \(a_t\le N\)
$$1\le c\le \left\lfloor \frac{N}{u^e}\right\rfloor.$$
لذلك تصبح مساهمة الجزء الهندسي
$$G_{\mathrm{geo}}(N)=\sum_{u=2}^{\lfloor N^{1/4}\rfloor}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
ويظهر حد الجذر الرابع لأن أقصر متتالية هندسية مقبولة طولها \(5\)، وبالتالي لا بد من تحقق \(u^4\le N\).
بعد استبعاد الحالة الهندسية الدقيقة، تبقى العائلات الطويلة التي تولدها إحدى العلاقتين العوديتين من الرتبة الثانية:
$$a_{n+1}=m a_n-a_{n-1},$$
أو
$$a_{n+1}=m a_n+a_{n-1}.$$
الفروع العامة تبدأ من \((1,m)\). وهناك أيضًا فرعان إضافيان من النوع ذي الإشارة السالبة يبدأان من \((1,2)\) بمعامل \(3\)، ومن \((1,3)\) بمعامل \(4\)، وكذلك فرعان إضافيان من النوع ذي الإشارة الموجبة يبدأان من \((1,2)\) بمعامل \(1\)، ومن \((1,3)\) بمعامل \(2\).
كل اختيار من هذه الاختيارات يولد عائلة متزايدة واحدة إلى أن يفشل الحد التالي في الاستمرار بالزيادة أو يتجاوز \(N\). فإذا كان طول تلك العائلة هو \(t\)، فإن مساهمتها تساوي \(C(t)\).
ومن الأمثلة على ذلك
$$1,2,3,5,8,\dots$$
التي تأتي من الفرع الموجب ذي المعامل \(1\)، بينما
$$1,m,m^2-1,m^3-2m,\dots$$
تمثل بداية الفرع العام ذي الإشارة السالبة.
إلى جانب عائلات العلاقات العودية، تضيف التنفيذات السلسلة الهجينة
$$1,2,6,18,54,\dots$$
التي يصبح ذيلها بعد الحد الأول متتالية هندسية أساسها \(3\). إذا احتوت هذه السلسلة على \(t\) حدود لا تتجاوز \(N\)، فإن المقاطع الجديدة فعلًا هي فقط تلك التي ما تزال تحتوي على الحد الأول \(1\)، لأن أي نافذة تبدأ بعد ذلك ستكون قد احتُسبت أصلًا ضمن الجزء الهندسي. لذلك تكون مساهمة هذا الجزء
$$t-4$$
وليس \(C(t)\).
وأخيرًا توجد عشرة متتاليات متفرقة معزولة طول كل منها بالضبط \(5\). كل واحدة منها تضيف \(1\) بمجرد أن يصبح حدها الأخير \(\le N\). ولهذا يكفي أن يخزن التنفيذ القيم العشر النهائية لهذه الحالات الخاصة.
قيمة الفحص \(G(10)=26\) يمكن إعادة بنائها مباشرة من هذا التفكيك إلى عائلات.
عائلة الأعداد المتتالية تعطي
$$C(10)=\frac{(10-4)(10-3)}{2}=21.$$
الجزء الهندسي لا يعطي شيئًا لأن \(2^4=16\gt 10\).
ومن بين العائلات العودية، فإن المتتالية الوحيدة التي تصل إلى طول \(5\) تحت الحد \(10\) هي
$$1,2,3,5,8,$$
ولذلك تضيف \(1\).
أما السلسلة الهجينة فتبدأ بـ \(1,2,6,18,\dots\)، ومن ثم فهي ما تزال قصيرة عند \(N=10\).
ومن بين الاستثناءات العشرة المتفرقة، يوجد أربع حالات حدها الأخير لا يتجاوز \(10\). وعليه نحصل على
$$G(10)=21+0+1+0+4=26,$$
وهو نفس ناتج الفحص الموجود في التنفيذ.
تنفيذات C++ وPython وJava تتبع جميعها المسار نفسه. أولًا يُحسب \(R=\lfloor N^{1/4}\rfloor\) بحذر، مع تصحيح التقدير العشري حتى نضمن أن \(R^4\le N\lt (R+1)^4\). بعد ذلك تُضاف مساهمة العائلة الأساسية للأعداد المتتالية، أي \(C(N)\).
ثم تُبنى قيم دالة أويلر حتى \(R\)، ويُحسب المجموع الهندسي
$$\sum_{u=2}^{R}\varphi(u)\sum_{\substack{e\ge 4\\u^e\le N}}\left\lfloor\frac{N}{u^e}\right\rfloor.$$
بعد ذلك تُجرَّب جميع معاملات العودية والأزواج الابتدائية المسموح بها، وتُولَّد الحدود إلى أن تتوقف الزيادة الصارمة أو يتجاوز الحد التالي \(N\)، ثم تُضاف القيمة \(C(t)\) لطول العائلة الناتج. وفي النهاية تُضاف السلسلة الهجينة والعشرة التصحيحات المتفرقة. كل عملية جمع تُختزل مباشرة بترديد \(10^9+7\). نسخة C++ توزع جمع الجزء الهندسي على خيوط متعددة، أما الصيغة الرياضية نفسها فهي واحدة في اللغات الثلاث.
إذا كتبنا \(R=\lfloor N^{1/4}\rfloor\)، فإن بناء جدول دالة أويلر يكلف \(O(R\log\log R)\) زمنًا و\(O(R)\) ذاكرة. والمجموع الهندسي المزدوج يزور جميع القوى \(u^e\le N\)، ولذلك يبقى أيضًا قريبًا من \(O(R\log\log R)\). أما عائلات العودية فلا تُفحص إلا للمعاملات حتى \(R\)، وكل عائلة تنمو أسيًا، لذا يكون العمل الكلي فيها مضبوطًا عمليًا بحد من رتبة \(O(R\log N)\). الجزء الهجين والاستثناءات المتفرقة كلفتهما ثابتة. وبهذا تستخدم الطريقة ذاكرة \(O(R)\) وتعمل بزمن يعتمد تقريبًا على الجذر الرابع لـ \(N\) بدلًا من الاعتماد الخطي على \(N\).