The task is to evaluate
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
for the specific target \(B(10^9,10^7,10^{15})\), where the sequence is defined by
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3.$$
The recurrence is explosive: every step squares the previous value, so computing \(a_n\) directly is hopeless when \(n=10^{15}\). The solution therefore avoids building the integer \(a_n\) itself and instead works modulo each prime in the interval.
The central idea is to turn the quadratic recurrence into a Lucas-sequence problem whose enormous index can be reduced modulo a small group order.
Introduce
$$b_t=6a_t+5.$$
Then the recurrence becomes
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
with initial value
$$b_1=6\cdot 1+5=11.$$
This is the key simplification. Instead of a quadratic polynomial with three terms, we now have repeated application of the much cleaner map \(u\mapsto u^2-2\).
Let
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
Define the Lucas \(V\)-sequence with parameters \(P=11\) and \(Q=1\) by
$$V_m=\alpha^m+\beta^m.$$
Then
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
Because \(\alpha\beta=1\), we also have the doubling identity
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
Since \(b_1=V_1\) and both sequences obey the same doubling rule, induction gives
$$b_t=V_{2^{t-1}}.$$
Therefore the original problem is equivalent to evaluating
$$a_n \bmod p \quad \text{from} \quad V_{2^{n-1}} \bmod p.$$
For the primes relevant to the target sum, \(p>13\), so the discriminant
$$\Delta=11^2-4=117$$
is nonzero modulo \(p\), and \(6\) is invertible modulo \(p\).
If \(117\) is a quadratic residue modulo \(p\), then \(\sqrt{117}\in\mathbb{F}_p\), so \(\alpha,\beta\in\mathbb{F}_p^\times\). Since \(\beta=\alpha^{-1}\), the value
$$V_k=\alpha^k+\alpha^{-k}$$
depends only on \(k\bmod(p-1)\).
If \(117\) is a quadratic nonresidue modulo \(p\), then \(\alpha\) and \(\beta\) live in \(\mathbb{F}_{p^2}\), and the Frobenius map swaps them:
$$\alpha^p=\beta=\alpha^{-1}.$$
Hence
$$\alpha^{p+1}=1,$$
so \(V_k\) depends only on \(k\bmod(p+1)\).
Thus the enormous index
$$k=2^{n-1}$$
is reduced by
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{if }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{if }\left(\frac{117}{p}\right)=-1.$$
This turns an index of size roughly \(2^{10^{15}}\) into one smaller than \(p+1\).
After the index has been reduced, the Lucas value is computed with standard doubling identities:
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
Processing the bits of \(k\) from top to bottom keeps a pair of consecutive Lucas values and reaches \(V_k \bmod p\) in \(O(\log k)\) arithmetic steps.
Once \(b_n \equiv V_k \pmod p\) is known, we recover the original sequence via
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
The interval \([x,x+y]\) is handled with a segmented sieve. First, all base primes up to \(\sqrt{x+y}\) are generated. Then their multiples are marked inside the target interval, leaving exactly the primes that contribute to the sum.
For each prime \(p\) in the segment, the algorithm performs three modular tasks:
$$\text{determine whether }117\text{ is a residue mod }p,$$
$$\text{compute }2^{n-1}\text{ modulo }p-1\text{ or }p+1,$$
$$\text{evaluate }V_k\text{ and convert it back to }a_n\bmod p.$$
Adding those residues yields the required value of \(B(x,y,n)\).
A small example shows the reduction clearly. Take \(n=4\) and the interval \([5,7]\), so the contributing primes are \(5\) and \(7\).
For \(p=5\), \(117\equiv 2\pmod 5\), which is a nonresidue, so the index is reduced modulo \(p+1=6\):
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
Then
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
so
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
For \(p=7\), \(117\equiv 5\pmod 7\), also a nonresidue, so the index is reduced modulo \(p+1=8\):
$$k\equiv 8\equiv 0\pmod 8.$$
Therefore
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
Hence
$$B(5,2,4)=4+3=7.$$
The C++, Python, and Java implementations follow the same pipeline. They first build a simple sieve up to \(\sqrt{x+y}\), then use those base primes to mark a segmented interval \([x,x+y]\). Every unmarked entry is a prime that contributes one term to the final sum.
For each such prime, the implementation computes a Legendre-style residue test for \(117\), chooses \(p-1\) or \(p+1\) as the period modulus, and evaluates \(2^{n-1}\) modulo that period with fast modular exponentiation. It then performs Lucas fast doubling on a pair of consecutive values until it reaches the reduced index \(k\), converts the result back from \(b_n\) to \(a_n\), and adds the residue to the running total.
No large integer value of \(a_n\) is ever constructed. Only modular values are propagated, which is why the method stays fast even when \(n=10^{15}\).
Let \(H=x+y\), and let \(\pi(x,y)\) denote the number of primes in \([x,x+y]\). Building the base sieve up to \(\sqrt{H}\) costs \(O(\sqrt{H}\log\log H)\) time and \(O(\sqrt{H})\) memory. Marking the segment costs \(O(y\log\log H)\) time and \(O(y)\) memory.
For each prime in the segment, the modular residue test, the reduction of \(2^{n-1}\), and the Lucas doubling stage together require \(O(\log n+\log p)\) arithmetic operations. The overall running time is therefore
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
with memory usage
$$O(\sqrt{H}+y).$$
Gesucht ist der Wert
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
im eigentlichen Problem also \(B(10^9,10^7,10^{15})\), wobei die Folge durch
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3$$
gegeben ist. Diese Rekursion wächst extrem schnell, denn in jedem Schritt wird im Wesentlichen quadriert. Eine direkte Berechnung bis \(n=10^{15}\) ist daher ausgeschlossen, also muss man von Anfang an modulo jeder Primzahl arbeiten.
Der Kern der Lösung besteht darin, die quadratische Rekursion in eine Lucas-Folge umzuschreiben und den riesigen Index anschließend auf eine kleine Periode modulo \(p-1\) oder \(p+1\) zu reduzieren.
Wir setzen
$$b_t=6a_t+5.$$
Dann folgt
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
und außerdem
$$b_1=6\cdot 1+5=11.$$
Damit wird aus der ursprünglichen Rekursion eine viel sauberere Vorschrift: wiederholte Anwendung der Abbildung \(u\mapsto u^2-2\).
Definiere
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
Die zugehörige Lucas-\(V\)-Folge mit \(P=11\) und \(Q=1\) ist
$$V_m=\alpha^m+\beta^m.$$
Sie erfüllt
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
Wegen \(\alpha\beta=1\) gilt die Verdopplungsformel
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
Da \(b_1=V_1\) ist und beide Folgen dieselbe Verdopplungsregel besitzen, erhält man induktiv
$$b_t=V_{2^{t-1}}.$$
Somit reduziert sich alles auf die Berechnung von
$$V_{2^{n-1}}\bmod p.$$
Für die im Zielintervall vorkommenden Primzahlen gilt \(p>13\). Daher ist die Diskriminante
$$\Delta=11^2-4=117$$
modulo \(p\) ungleich null, und \(6\) besitzt ein multiplikatives Inverses modulo \(p\).
Ist \(117\) ein quadratischer Rest modulo \(p\), dann liegt \(\sqrt{117}\) bereits in \(\mathbb{F}_p\), also auch \(\alpha,\beta\in\mathbb{F}_p^\times\). Weil \(\beta=\alpha^{-1}\) gilt, hängt
$$V_k=\alpha^k+\alpha^{-k}$$
nur von \(k\bmod(p-1)\) ab.
Ist \(117\) dagegen ein Nichtrest, dann liegen \(\alpha\) und \(\beta\) in \(\mathbb{F}_{p^2}\), und die Frobenius-Abbildung vertauscht beide:
$$\alpha^p=\beta=\alpha^{-1}.$$
Daraus folgt
$$\alpha^{p+1}=1,$$
also hängt \(V_k\) nur von \(k\bmod(p+1)\) ab.
Der astronomische Index
$$k=2^{n-1}$$
wird also ersetzt durch
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{falls }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{falls }\left(\frac{117}{p}\right)=-1.$$
Nach dieser Reduktion wird der Lucas-Term mit den Standardidentitäten berechnet:
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
Wenn man die Bits des reduzierten Index von oben nach unten verarbeitet und dabei ein Paar aufeinanderfolgender Lucas-Werte mitführt, erhält man \(V_k\bmod p\) in \(O(\log k)\) Schritten.
Anschließend wird zur ursprünglichen Folge zurückgerechnet:
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
Die Primzahlen in \([x,x+y]\) werden mit einem segmentierten Sieb erzeugt. Zuerst bestimmt man alle Basisprimzahlen bis \(\sqrt{x+y}\), dann markiert man deren Vielfache im Zielintervall. Übrig bleiben genau die Primzahlen, die einen Beitrag zur Summe liefern.
Für jede solche Primzahl \(p\) werden drei modulare Teilaufgaben gelöst:
$$\text{Test auf quadratischen Rest für }117,$$
$$\text{Berechnung von }2^{n-1}\text{ modulo }p-1\text{ oder }p+1,$$
$$\text{Auswertung von }V_k\text{ und Rückumrechnung zu }a_n\bmod p.$$
Die Summe dieser Residuen ist genau \(B(x,y,n)\).
Ein kleines Beispiel macht die Reduktion sichtbar. Nimm \(n=4\) und das Intervall \([5,7]\). Dann tragen genau die Primzahlen \(5\) und \(7\) bei.
Für \(p=5\) ist \(117\equiv 2\pmod 5\), also ein Nichtrest. Deshalb reduzieren wir den Index modulo \(p+1=6\):
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
Damit
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
und folglich
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
Für \(p=7\) gilt \(117\equiv 5\pmod 7\), ebenfalls ein Nichtrest. Jetzt wird modulo \(p+1=8\) reduziert:
$$k\equiv 8\equiv 0\pmod 8.$$
Also
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
Somit erhält man
$$B(5,2,4)=4+3=7.$$
Die Implementierungen in C++, Python und Java folgen demselben Ablauf. Zuerst wird ein kleines Sieb bis \(\sqrt{x+y}\) aufgebaut, danach wird das Segment \([x,x+y]\) markiert. Jeder nicht markierte Eintrag ist eine Primzahl, für die genau ein Summand berechnet wird.
Für jede Primzahl wird per modularer Potenzierung geprüft, ob \(117\) ein quadratischer Rest ist. Danach wählt die Implementierung \(p-1\) oder \(p+1\) als Periodenmodulus, reduziert \(2^{n-1}\) auf diesen Modulus und berechnet den zugehörigen Lucas-Wert mit der Verdopplungsmethode. Zum Schluss wird von \(b_n\) zurück auf \(a_n\) umgerechnet und der Rest zur Gesamtsumme addiert.
Entscheidend ist, dass niemals der riesige ganzzahlige Wert \(a_n\) konstruiert wird. Die Rechnung bleibt vollständig modular.
Setze \(H=x+y\), und sei \(\pi(x,y)\) die Anzahl der Primzahlen im Intervall \([x,x+y]\). Das Basissieb bis \(\sqrt{H}\) benötigt \(O(\sqrt{H}\log\log H)\) Zeit und \(O(\sqrt{H})\) Speicher. Das Markieren des Segments kostet \(O(y\log\log H)\) Zeit und \(O(y)\) Speicher.
Für jede Primzahl kommen ein Resttest, eine modulare Potenz \(2^{n-1}\) und eine Lucas-Verdopplung hinzu, insgesamt also \(O(\log n+\log p)\) Operationen pro Primzahl. Die Gesamtlaufzeit ist daher
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
bei einem Speicherverbrauch von
$$O(\sqrt{H}+y).$$
İstenen değer
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
özellikle de \(B(10^9,10^7,10^{15})\) toplamıdır. Burada dizi
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3$$
şeklinde tanımlıdır. Bu dizi her adımda temelde karesini aldığı için son derece hızlı büyür; dolayısıyla \(n=10^{15}\) için doğrudan ilerlemek mümkün değildir. Çözüm, büyük tamsayıları üretmek yerine her asal için hesabı baştan sona modüler olarak yürütür.
Ana fikir, kuadratik yinelemeyi bir Lucas dizisine dönüştürmek ve sonra dev indeksi \(p-1\) ya da \(p+1\) modunda küçültmektir.
Şunu tanımlayalım:
$$b_t=6a_t+5.$$
Böylece
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
ve başlangıç değeri de
$$b_1=6\cdot 1+5=11$$
olur. Yani karmaşık görünen orijinal yineleme, çok daha temiz olan \(u\mapsto u^2-2\) dönüşümüne indirgenir.
Şimdi
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1$$
olsun. Lucas \(V\)-dizisini
$$V_m=\alpha^m+\beta^m$$
ile tanımlayalım. O zaman
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}$$
sağlanır. Ayrıca \(\alpha\beta=1\) olduğu için
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
\(b_1=V_1\) ve her iki yapı da aynı iki katına çıkarma bağıntısını sağladığından
$$b_t=V_{2^{t-1}}$$
elde edilir. Böylece sorun,
$$V_{2^{n-1}}\bmod p$$
hesabına dönüşür.
Hedef toplamda kullanılan asallar için \(p>13\) olduğundan diskriminant
$$\Delta=11^2-4=117$$
mod \(p\) altında sıfır değildir ve \(6\)'nın da modüler tersi vardır.
Eğer \(117\), \(p\) modunda kuadratik kalansa, \(\sqrt{117}\) zaten \(\mathbb{F}_p\) içindedir; dolayısıyla \(\alpha,\beta\in\mathbb{F}_p^\times\). \(\beta=\alpha^{-1}\) olduğundan
$$V_k=\alpha^k+\alpha^{-k}$$
yalnızca \(k\bmod(p-1)\)'e bağlıdır.
Eğer \(117\) kuadratik kalıntı değilse, kökler \(\mathbb{F}_{p^2}\) içine gider ve Frobenius dönüşümü onları yer değiştirir:
$$\alpha^p=\beta=\alpha^{-1}.$$
Buradan
$$\alpha^{p+1}=1$$
gelir; yani \(V_k\) bu kez yalnızca \(k\bmod(p+1)\)'e bağlıdır.
Sonuç olarak
$$k=2^{n-1}$$
yerine şu küçültülmüş indeks kullanılır:
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{eğer }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{eğer }\left(\frac{117}{p}\right)=-1.$$
İndeks küçültüldükten sonra şu özdeşlikler kullanılır:
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
Küçültülmüş indeksin bitleri yukarıdan aşağıya işlenirken ardışık iki Lucas değeri taşınır ve \(V_k\bmod p\) değeri \(O(\log k)\) zamanda bulunur.
Sonra da
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p$$
ile istenen kalıntıya geri dönülür.
\([x,x+y]\) aralığı segmentli elek ile taranır. Önce \(\sqrt{x+y}\)'ye kadar taban asallar üretilir, sonra bunların katları hedef aralık içinde işaretlenir. İşaretlenmeden kalan sayılar tam olarak toplamda kullanılacak asallardır.
Her asal \(p\) için üç modüler adım uygulanır:
$$117\text{ sayısının mod }p\text{ altında kuadratik kalan olup olmadığını belirlemek},$$
$$2^{n-1}\text{ değerini }p-1\text{ ya da }p+1\text{ modunda hesaplamak},$$
$$V_k\text{ değerini bulup bunu }a_n\bmod p\text{ biçimine çevirmek}.$$
Bu kalıntılar toplandığında \(B(x,y,n)\) elde edilir.
Küçük bir örnek yöntemin nasıl çalıştığını netleştirir. \(n=4\) ve aralık \([5,7]\) olsun. Katkı yapan asallar yalnızca \(5\) ve \(7\)'dir.
\(p=5\) için \(117\equiv 2\pmod 5\) ve bu bir kuadratik kalıntı değildir. O halde indeks \(p+1=6\) modunda küçültülür:
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
Buradan
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
ve dolayısıyla
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
\(p=7\) için \(117\equiv 5\pmod 7\) yine kalıntı değildir. Bu kez modül \(p+1=8\) olur:
$$k\equiv 8\equiv 0\pmod 8.$$
Bu yüzden
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
Sonuç olarak
$$B(5,2,4)=4+3=7.$$
C++, Python ve Java uygulamalarının hepsi aynı akışı izler. Önce \(\sqrt{x+y}\)'ye kadar küçük bir asal eleği kurulur, sonra \([x,x+y]\) segmenti işaretlenir. İşaretlenmemiş her sayı bir asaldır ve toplamda tek bir katkı üretir.
Her asal için uygulama önce \(117\)'nin kuadratik kalan olup olmadığını modüler üs alma ile sınar. Ardından periyot modülü olarak \(p-1\) ya da \(p+1\) seçilir, \(2^{n-1}\) bu modüle indirgenir ve Lucas iki katlama yöntemiyle küçültülmüş indeks için değer hesaplanır. Son aşamada \(b_n\) değerinden tekrar \(a_n\) kalıntısına dönülür ve toplam güncellenir.
Önemli nokta şudur: Algoritma hiçbir zaman devasa büyüklükteki tam \(a_n\) sayısını üretmez; hesap tamamen modüler düzeyde kalır.
\(H=x+y\) olsun ve \(\pi(x,y)\), \([x,x+y]\) aralığındaki asal sayısını göstersin. \(\sqrt{H}\)'ye kadar olan taban eleği \(O(\sqrt{H}\log\log H)\) zamanda ve \(O(\sqrt{H})\) bellekte kurulur. Segmentin işaretlenmesi \(O(y\log\log H)\) zaman ve \(O(y)\) bellek kullanır.
Aralıktaki her asal için kalıntı testi, \(2^{n-1}\)'in indirgenmesi ve Lucas iki katlama aşaması toplam \(O(\log n+\log p)\) işlem gerektirir. Böylece toplam süre
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
bellek kullanımı ise
$$O(\sqrt{H}+y)$$
olur.
Se quiere calcular
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
y en particular \(B(10^9,10^7,10^{15})\), donde la sucesión está dada por
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3.$$
La secuencia crece de forma explosiva, porque en cada paso aparece esencialmente un cuadrado del término anterior. Por eso no tiene sentido iterar hasta \(n=10^{15}\); la única estrategia viable es trabajar módulo cada primo del intervalo desde el principio.
La solución transforma la recurrencia cuadrática en un problema sobre una sucesión de Lucas y luego reduce el índice gigantesco \(2^{n-1}\) a un módulo pequeño.
Definimos
$$b_t=6a_t+5.$$
Entonces
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
y además
$$b_1=6\cdot 1+5=11.$$
La recurrencia original se convierte así en la iteración repetida de la aplicación simple \(u\mapsto u^2-2\).
Tomemos
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
La sucesión de Lucas \(V\) con \(P=11\) y \(Q=1\) se escribe como
$$V_m=\alpha^m+\beta^m.$$
Por tanto,
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
Como \(\alpha\beta=1\), aparece la identidad de duplicación
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
Dado que \(b_1=V_1\) y ambas construcciones cumplen la misma regla de duplicación, se obtiene por inducción
$$b_t=V_{2^{t-1}}.$$
El problema queda reducido a calcular
$$V_{2^{n-1}}\bmod p.$$
En el intervalo real del problema siempre se tiene \(p>13\), así que el discriminante
$$\Delta=11^2-4=117$$
no es cero módulo \(p\), y \(6\) es invertible módulo \(p\).
Si \(117\) es residuo cuadrático módulo \(p\), entonces \(\sqrt{117}\in\mathbb{F}_p\), de modo que \(\alpha,\beta\in\mathbb{F}_p^\times\). Como \(\beta=\alpha^{-1}\), el valor
$$V_k=\alpha^k+\alpha^{-k}$$
depende solo de \(k\bmod(p-1)\).
Si \(117\) no es residuo cuadrático, las raíces viven en \(\mathbb{F}_{p^2}\) y el automorfismo de Frobenius las intercambia:
$$\alpha^p=\beta=\alpha^{-1}.$$
Por eso
$$\alpha^{p+1}=1,$$
y ahora \(V_k\) depende solo de \(k\bmod(p+1)\).
Así, el índice gigantesco
$$k=2^{n-1}$$
se reemplaza por
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{si }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{si }\left(\frac{117}{p}\right)=-1.$$
Una vez reducido el índice, se usan las identidades
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
Recorriendo los bits de \(k\) de arriba hacia abajo y manteniendo un par de valores consecutivos, se obtiene \(V_k\bmod p\) en \(O(\log k)\) pasos.
Después se vuelve a la sucesión original mediante
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
Los primos en \([x,x+y]\) se generan con una criba segmentada. Primero se calculan todos los primos base hasta \(\sqrt{x+y}\), y luego se tachan sus múltiplos dentro del segmento objetivo. Los números que quedan sin marcar son exactamente los primos que contribuyen a la suma.
Para cada primo \(p\), el algoritmo hace tres cosas:
$$\text{decidir si }117\text{ es residuo cuadrático módulo }p,$$
$$\text{reducir }2^{n-1}\text{ módulo }p-1\text{ o }p+1,$$
$$\text{evaluar }V_k\text{ y convertirlo a }a_n\bmod p.$$
La suma de todos esos residuos es \(B(x,y,n)\).
Un ejemplo pequeño aclara el procedimiento. Tomemos \(n=4\) y el intervalo \([5,7]\), cuyos primos son \(5\) y \(7\).
Para \(p=5\), se tiene \(117\equiv 2\pmod 5\), que no es residuo cuadrático. Entonces el índice se reduce módulo \(p+1=6\):
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
Luego
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
así que
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
Para \(p=7\), \(117\equiv 5\pmod 7\), también no residuo cuadrático. Ahora el índice se reduce módulo \(p+1=8\):
$$k\equiv 8\equiv 0\pmod 8.$$
Por tanto
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
En consecuencia,
$$B(5,2,4)=4+3=7.$$
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero construyen una criba pequeña hasta \(\sqrt{x+y}\); después usan esos primos base para marcar el segmento \([x,x+y]\). Cada posición no marcada corresponde a un primo que aporta un término a la suma final.
Para cada primo, la implementación calcula si \(117\) es residuo cuadrático mediante exponenciación modular, elige \(p-1\) o \(p+1\) como módulo de periodo, reduce \(2^{n-1}\) a ese módulo y evalúa el término de Lucas con duplicación rápida. Finalmente convierte el resultado desde \(b_n\) a \(a_n\bmod p\) y lo añade al acumulado.
En ningún momento se construye el entero gigantesco \(a_n\). Todo el trabajo se hace con residuos modulares.
Sea \(H=x+y\), y sea \(\pi(x,y)\) el número de primos en \([x,x+y]\). La criba base hasta \(\sqrt{H}\) cuesta \(O(\sqrt{H}\log\log H)\) tiempo y \(O(\sqrt{H})\) memoria. Marcar el segmento cuesta \(O(y\log\log H)\) tiempo y \(O(y)\) memoria.
Para cada primo del intervalo, la prueba de residuo, la reducción de \(2^{n-1}\) y la etapa de Lucas requieren en total \(O(\log n+\log p)\) operaciones aritméticas. Por tanto, el tiempo total es
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
y el uso de memoria es
$$O(\sqrt{H}+y).$$
题目要求计算
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
在本题中目标是 \(B(10^9,10^7,10^{15})\)。其中序列由
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3$$
定义。这个递推的增长速度极快，因为每一步本质上都在对前一项做平方级放大，所以不可能把序列老老实实推到第 \(10^{15}\) 项。可行的方法只能是：对区间中的每个素数分别做模运算，把所有计算都压在有限域里完成。
核心思路分成两层。第一层是把原始二次递推改写成 Lucas \(V\) 序列；第二层是利用有限域中的阶，把巨大的指数 \(2^{n-1}\) 压缩到模 \(p-1\) 或模 \(p+1\) 的小范围内。
定义新序列
$$b_t=6a_t+5.$$
把原递推代入，可得
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
同时初值为
$$b_1=6\cdot 1+5=11.$$
这一步非常关键。原来是一个带三项的二次递推，现在变成了不断作用映射 \(u\mapsto u^2-2\)。形式简单以后，后面的代数结构就会显现出来。
记
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
用它们定义 Lucas \(V\) 序列
$$V_m=\alpha^m+\beta^m.$$
于是有
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
由于 \(\alpha\beta=1\)，还满足一个非常适合本题的倍增恒等式：
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
现在比较 \(b_t\) 和 \(V_m\)。我们已经知道 \(b_1=11=V_1\)，而且 \(b_{t+1}=b_t^2-2\) 与 \(V_{2m}=V_m^2-2\) 完全同型，所以归纳可得
$$b_t=V_{2^{t-1}}.$$
也就是说，只要能算出
$$V_{2^{n-1}}\bmod p,$$
就能恢复出所需的 \(a_n\bmod p\)。
在实际目标区间里，所有参与求和的素数都满足 \(p>13\)。因此判别式
$$\Delta=11^2-4=117$$
在模 \(p\) 下不为零，并且 \(6\) 在模 \(p\) 下一定可逆。
如果 \(117\) 在模 \(p\) 下是二次剩余，那么 \(\sqrt{117}\in\mathbb{F}_p\)，从而 \(\alpha,\beta\in\mathbb{F}_p^\times\)。又因为 \(\beta=\alpha^{-1}\)，所以
$$V_k=\alpha^k+\alpha^{-k}$$
只依赖于 \(k\bmod(p-1)\)。
如果 \(117\) 在模 \(p\) 下是二次非剩余，那么根不在 \(\mathbb{F}_p\) 里，而是在扩域 \(\mathbb{F}_{p^2}\) 中。此时 Frobenius 自同构会交换这两个根：
$$\alpha^p=\beta=\alpha^{-1}.$$
于是得到
$$\alpha^{p+1}=1,$$
所以 \(V_k\) 只依赖于 \(k\bmod(p+1)\)。
因此，原本天文数字大小的指数
$$k=2^{n-1}$$
可以先做如下约化：
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{当 }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{当 }\left(\frac{117}{p}\right)=-1.$$
这一步把原本几乎无法想象的大指数压缩到小于 \(p+1\) 的范围，后续计算才真正可行。
把指数压缩后，就可以利用 Lucas 序列的倍增公式：
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
实现时从高位到低位扫描约化后的指数 \(k\)，始终维护一对相邻的 Lucas 值，这样就能在 \(O(\log k)\) 的模运算内得到 \(V_k\bmod p\)。
求出 \(b_n\equiv V_k\pmod p\) 后，再用仿射变换反解：
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
区间 \([x,x+y]\) 中的素数通过分段筛得到。先筛出所有不超过 \(\sqrt{x+y}\) 的基础素数，再用这些基础素数去标记目标区间中的合数，剩下的未标记位置就是需要参与求和的素数。
对每个素数 \(p\)，算法都执行同样的三件事：
$$\text{判断 }117\text{ 在模 }p\text{ 下是二次剩余还是二次非剩余},$$
$$\text{把 }2^{n-1}\text{ 约化到 }p-1\text{ 或 }p+1\text{ 模下},$$
$$\text{计算 }V_k\text{，再还原出 }a_n\bmod p.$$
把这些模值加起来，就得到题目要求的 \(B(x,y,n)\)。
下面用一个很小的例子展示整个流程。取 \(n=4\)，区间取 \([5,7]\)，那么参与求和的素数只有 \(5\) 和 \(7\)。
先看 \(p=5\)。因为 \(117\equiv 2\pmod 5\)，而 \(2\) 在模 \(5\) 下不是二次剩余，所以指数按 \(p+1=6\) 约化：
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
于是
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
从而
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
再看 \(p=7\)。此时 \(117\equiv 5\pmod 7\)，而 \(5\) 也不是二次剩余，所以指数按 \(p+1=8\) 约化：
$$k\equiv 8\equiv 0\pmod 8.$$
于是
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
最终得到
$$B(5,2,4)=4+3=7.$$
C++、Python 和 Java 实现采用的是同一条流水线。第一步先建立一个到 \(\sqrt{x+y}\) 为止的小筛，用它得到基础素数。第二步把这些基础素数的倍数标记到区间 \([x,x+y]\) 中，于是未被标记的位置就是区间内的素数。
接下来对每个素数，程序先用模幂判断 \(117\) 是否为二次剩余，再据此选择周期模数 \(p-1\) 或 \(p+1\)。然后再计算 \(2^{n-1}\) 在该模数下的值，并通过 Lucas 快速倍增求出对应的 \(V_k\bmod p\)。最后把它从 \(b_n\) 转回 \(a_n\bmod p\)，累加到总和中。
整个过程中从来不会显式构造庞大的整数 \(a_n\)。程序始终只传播模值，这正是它能处理 \(n=10^{15}\) 的根本原因。
记 \(H=x+y\)，记 \(\pi(x,y)\) 为区间 \([x,x+y]\) 内的素数个数。建立到 \(\sqrt{H}\) 的基础筛需要 \(O(\sqrt{H}\log\log H)\) 时间和 \(O(\sqrt{H})\) 内存；对长度为 \(y+1\) 的目标区间做分段标记需要 \(O(y\log\log H)\) 时间和 \(O(y)\) 内存。
对于区间中的每个素数，二次剩余判定、指数约化以及 Lucas 快速倍增合起来需要 \(O(\log n+\log p)\) 次模运算。因此总时间复杂度为
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
总空间复杂度为
$$O(\sqrt{H}+y).$$
Нужно вычислить
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
а в самой задаче требуется значение \(B(10^9,10^7,10^{15})\). Последовательность задается формулой
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3.$$
Рост здесь фактически взрывной: на каждом шаге возникает квадрат предыдущего значения. Поэтому прямой проход до \(n=10^{15}\) невозможен. Правильная стратегия состоит в том, чтобы ни разу не строить огромное число \(a_n\), а сразу считать все по модулю каждого простого из нужного интервала.
Решение опирается на два наблюдения. Сначала квадратичную рекурсию нужно превратить в последовательность Лукаса. Затем гигантский индекс \(2^{n-1}\) сокращается по модулю \(p-1\) или \(p+1\), что делает вычисление реальным.
Введем новую последовательность
$$b_t=6a_t+5.$$
Тогда
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
а начальное значение равно
$$b_1=6\cdot 1+5=11.$$
Это главный алгебраический шаг: вместо исходной квадратичной формулы получается повторное применение отображения \(u\mapsto u^2-2\).
Положим
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
Определим Lucas \(V\)-последовательность
$$V_m=\alpha^m+\beta^m.$$
Тогда
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
Так как \(\alpha\beta=1\), выполняется формула удвоения
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
Поскольку \(b_1=V_1\), а дальнейшее развитие определяется той же самой схемой удвоения, по индукции получаем
$$b_t=V_{2^{t-1}}.$$
Значит, нужно научиться быстро вычислять
$$V_{2^{n-1}}\bmod p.$$
Во всех простых модулях, реально встречающихся в целевом интервале, \(p>13\). Поэтому дискриминант
$$\Delta=11^2-4=117$$
не обращается в ноль по модулю \(p\), а число \(6\) обратимо по модулю \(p\).
Если \(117\) является квадратичным вычетом по модулю \(p\), то \(\sqrt{117}\in\mathbb{F}_p\), следовательно, \(\alpha,\beta\in\mathbb{F}_p^\times\). Поскольку \(\beta=\alpha^{-1}\), значение
$$V_k=\alpha^k+\alpha^{-k}$$
зависит только от \(k\bmod(p-1)\).
Если же \(117\) является невычетом, корни лежат в \(\mathbb{F}_{p^2}\), и автоморфизм Фробениуса их переставляет:
$$\alpha^p=\beta=\alpha^{-1}.$$
Отсюда следует
$$\alpha^{p+1}=1,$$
поэтому \(V_k\) зависит только от \(k\bmod(p+1)\).
Итак, индекс
$$k=2^{n-1}$$
заменяется на
$$k\equiv 2^{n-1}\pmod{p-1}\quad\text{если }\left(\frac{117}{p}\right)=1,$$
$$k\equiv 2^{n-1}\pmod{p+1}\quad\text{если }\left(\frac{117}{p}\right)=-1.$$
Это и есть решающий переход от астрономического индекса к маленькому числу, которое уже можно обрабатывать напрямую.
После сокращения индекса используются стандартные формулы
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
Если проходить по битам сокращенного индекса сверху вниз и хранить пару соседних значений Lucas-последовательности, то \(V_k\bmod p\) находится за \(O(\log k)\) шагов.
После этого исходная последовательность восстанавливается формулой
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
Простые числа на отрезке \([x,x+y]\) генерируются сегментированным решетом. Сначала находятся все базовые простые до \(\sqrt{x+y}\), затем их кратные вычеркиваются внутри целевого сегмента. Не вычеркнутые позиции и есть нужные простые.
Для каждого такого простого \(p\) алгоритм выполняет три модульные операции:
$$\text{проверяет, является ли }117\text{ квадратичным вычетом по модулю }p,$$
$$\text{вычисляет }2^{n-1}\text{ по модулю }p-1\text{ или }p+1,$$
$$\text{находит }V_k\text{ и переводит результат обратно в }a_n\bmod p.$$
Сумма этих остатков и дает \(B(x,y,n)\).
Небольшой пример показывает механизм в действии. Возьмем \(n=4\) и интервал \([5,7]\). Тогда в сумме участвуют только простые \(5\) и \(7\).
Для \(p=5\) имеем \(117\equiv 2\pmod 5\), а это квадратичный невычет. Значит, индекс сокращается по модулю \(p+1=6\):
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
Следовательно,
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
и потому
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
Для \(p=7\) получаем \(117\equiv 5\pmod 7\), что тоже невычет. Теперь модуль равен \(p+1=8\):
$$k\equiv 8\equiv 0\pmod 8.$$
Значит,
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
Итак,
$$B(5,2,4)=4+3=7.$$
Реализации на C++, Python и Java устроены одинаково. Сначала они строят небольшое решето до \(\sqrt{x+y}\), а затем с его помощью размечают сегмент \([x,x+y]\). Каждая невычеркнутая позиция соответствует простому числу, дающему одно слагаемое.
Для каждого простого модульной степенью определяется, является ли \(117\) вычетом. Затем выбирается период \(p-1\) или \(p+1\), вычисляется \(2^{n-1}\) по этому модулю и запускается быстрое удвоение Lucas-последовательности для получения нужного значения \(V_k\bmod p\). После этого результат переводится из \(b_n\) обратно в \(a_n\bmod p\) и добавляется к общей сумме.
Нигде не строится сам огромный integer \(a_n\); программа работает только с остатками.
Пусть \(H=x+y\), а \(\pi(x,y)\) обозначает число простых на отрезке \([x,x+y]\). Построение базового решета до \(\sqrt{H}\) требует \(O(\sqrt{H}\log\log H)\) времени и \(O(\sqrt{H})\) памяти. Разметка сегмента требует \(O(y\log\log H)\) времени и \(O(y)\) памяти.
Для каждого простого в интервале тест на вычет, сокращение \(2^{n-1}\) и этап быстрого удвоения Lucas дают суммарно \(O(\log n+\log p)\) арифметических операций. Поэтому общая сложность равна
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
а память составляет
$$O(\sqrt{H}+y).$$
المطلوب هو حساب
$$B(x,y,n)=\sum_{\substack{p\ \text{prime}\\ x\le p\le x+y}} \left(a_n \bmod p\right),$$
وفي المسألة نفسها نريد القيمة \(B(10^9,10^7,10^{15})\). المتتالية معرفة بالعلاقة
$$a_1=1,\qquad a_{t+1}=6a_t^2+10a_t+3.$$
هذه متتالية تنمو بسرعة انفجارية، لأن كل خطوة تحتوي فعليًا على تربيع للحد السابق. لذلك لا يمكن الوصول مباشرة إلى \(n=10^{15}\) بالتكرار العادي. الفكرة الصحيحة هي أن نحسب كل شيء modulo كل عدد أولي في المجال، من دون تكوين العدد الهائل \(a_n\) نفسه.
جوهر الحل هو تحويل العلاقة التربيعية إلى مسألة على متتالية Lucas من النوع \(V\)، ثم اختزال الفهرس العملاق \(2^{n-1}\) إلى فهرس صغير modulo \(p-1\) أو modulo \(p+1\).
نعرّف
$$b_t=6a_t+5.$$
عندئذ نحصل على
$$b_{t+1}=6a_{t+1}+5=6(6a_t^2+10a_t+3)+5=(6a_t+5)^2-2=b_t^2-2,$$
ومع الشرط الابتدائي
$$b_1=6\cdot 1+5=11.$$
وهكذا تختفي الصيغة التربيعية الأصلية ذات الحدود المتعددة، وتتحول المسألة إلى تكرار بسيط للدالة \(u\mapsto u^2-2\).
لتكن
$$\alpha,\beta=\frac{11\pm\sqrt{117}}{2},\qquad \alpha+\beta=11,\qquad \alpha\beta=1.$$
ونعرّف متتالية Lucas من النوع \(V\) بواسطة
$$V_m=\alpha^m+\beta^m.$$
إذن
$$V_0=2,\qquad V_1=11,\qquad V_{m+1}=11V_m-V_{m-1}.$$
وبسبب العلاقة \(\alpha\beta=1\) نحصل على هوية المضاعفة
$$V_{2m}=\alpha^{2m}+\beta^{2m}=(\alpha^m+\beta^m)^2-2(\alpha\beta)^m=V_m^2-2.$$
بما أن \(b_1=V_1\) وأن القاعدتين تتبعان قانون المضاعفة نفسه، ينتج بالاستقراء أن
$$b_t=V_{2^{t-1}}.$$
إذًا أصبحت المسألة هي حساب
$$V_{2^{n-1}}\bmod p.$$
في مجال الأعداد الأولية المستعمل في الهدف الفعلي للمسألة يكون دائمًا \(p>13\)، ولذلك فإن المميز
$$\Delta=11^2-4=117$$
غير منعدم modulo \(p\)، كما أن \(6\) قابل للعكس modulo \(p\).
إذا كان \(117\) باقيًا تربيعيًا modulo \(p\)، فذلك يعني أن \(\sqrt{117}\in\mathbb{F}_p\)، وبالتالي \(\alpha,\beta\in\mathbb{F}_p^\times\). وبما أن \(\beta=\alpha^{-1}\)، فإن
$$V_k=\alpha^k+\alpha^{-k}$$
يعتمد فقط على \(k\bmod(p-1)\).
أما إذا كان \(117\) غير باقي تربيعي modulo \(p\)، فإن الجذرين يعيشان في \(\mathbb{F}_{p^2}\)، وتقوم مؤثرة Frobenius بتبديلهما:
$$\alpha^p=\beta=\alpha^{-1}.$$
ومن ثم
$$\alpha^{p+1}=1,$$
فيعتمد \(V_k\) فقط على \(k\bmod(p+1)\).
لذلك يُختزل الفهرس
$$k=2^{n-1}$$
إلى أحد الشكلين
إذا كان \(\left(\frac{117}{p}\right)=1\)، فإن
$$k\equiv 2^{n-1}\pmod{p-1}.$$
وإذا كان \(\left(\frac{117}{p}\right)=-1\)، فإن
$$k\equiv 2^{n-1}\pmod{p+1}.$$
وهذه هي الخطوة التي تحول فهرسًا فلكي الحجم إلى عدد صغير يمكن التعامل معه حسابيًا.
بعد اختزال الفهرس نستخدم العلاقات
$$V_{2m}=V_m^2-2,$$
$$V_{2m+1}=V_mV_{m+1}-11,$$
$$V_{2m+2}=V_{m+1}^2-2.$$
بالمسير على بتات الفهرس المختزل من الأعلى إلى الأسفل، مع الاحتفاظ بزوج من حدود Lucas المتتالية، يمكن الوصول إلى \(V_k\bmod p\) في \(O(\log k)\) خطوة حسابية.
بعد ذلك نرجع إلى المتتالية الأصلية عبر
$$a_n\equiv (b_n-5)\cdot 6^{-1}\pmod p.$$
الأعداد الأولية في الفترة \([x,x+y]\) تُستخرج بمنخل مقطعي. أولًا نولّد جميع الأعداد الأولية الأساسية حتى \(\sqrt{x+y}\)، ثم نعلّم مضاعفاتها داخل الفترة المطلوبة. القيم غير المعلّمة هي تمامًا الأعداد الأولية التي تساهم في المجموع.
لكل عدد أولي \(p\)، تنفذ الخوارزمية ثلاث عمليات معيارية:
الخطوة الأولى هي تحديد ما إذا كان \(117\) باقيًا تربيعيًا modulo \(p\).
الخطوة الثانية هي حساب \(2^{n-1}\) modulo \(p-1\) أو modulo \(p+1\).
الخطوة الثالثة هي تقييم \(V_k\) ثم إرجاع النتيجة إلى \(a_n\bmod p\).
وبجمع هذه البواقي نحصل على \(B(x,y,n)\).
مثال صغير يوضح الفكرة. خذ \(n=4\) والفترة \([5,7]\)، وعندها يكون العددان الأوليان الوحيدان هما \(5\) و\(7\).
بالنسبة إلى \(p=5\)، لدينا \(117\equiv 2\pmod 5\)، و\(2\) ليس باقيًا تربيعيًا. لذلك نختزل الفهرس modulo \(p+1=6\):
$$k\equiv 2^{4-1}=8\equiv 2\pmod 6.$$
إذًا
$$V_2=11^2-2=119\equiv 4\pmod 5,$$
ومن ثم
$$a_4\equiv (4-5)\cdot 6^{-1}\equiv (-1)\cdot 1\equiv 4\pmod 5.$$
أما بالنسبة إلى \(p=7\)، فنجد \(117\equiv 5\pmod 7\)، وهو أيضًا ليس باقيًا تربيعيًا. هنا يكون الاختزال modulo \(p+1=8\):
$$k\equiv 8\equiv 0\pmod 8.$$
وعليه
$$V_0=2,\qquad a_4\equiv (2-5)\cdot 6^{-1}\equiv (-3)\cdot 6\equiv 3\pmod 7.$$
إذن
$$B(5,2,4)=4+3=7.$$
تنفذ تطبيقات C++ وPython وJava الخطة نفسها. تبدأ ببناء منخل صغير حتى \(\sqrt{x+y}\)، ثم تستخدم هذه الأعداد الأولية الأساسية لوسم الفترة \([x,x+y]\). كل موضع يبقى غير معلَّم يمثل عددًا أوليًا يضيف حدًا واحدًا إلى المجموع النهائي.
لكل عدد أولي، تحسب الخوارزمية أولًا اختبار الباقي التربيعي للعدد \(117\) باستخدام أس سريع معياري. بعد ذلك تختار \(p-1\) أو \(p+1\) باعتباره طول الفترة المناسبة، ثم تختزل \(2^{n-1}\) modulo ذلك العدد، وتستخدم مضاعفة Lucas السريعة للوصول إلى الحد المطلوب. في النهاية تحوّل القيمة من \(b_n\) إلى \(a_n\bmod p\) وتضيفها إلى المجاميع.
الميزة الأساسية أن أي نسخة من التطبيق لا تبني العدد الكامل \(a_n\) أبدًا؛ كل العمليات تبقى داخل الحساب المعياري.
لنضع \(H=x+y\)، ولتكن \(\pi(x,y)\) عدد الأعداد الأولية في الفترة \([x,x+y]\). بناء المنخل الأساسي حتى \(\sqrt{H}\) يكلف \(O(\sqrt{H}\log\log H)\) زمنًا و\(O(\sqrt{H})\) ذاكرة. أما وسم الفترة نفسها فيكلف \(O(y\log\log H)\) زمنًا و\(O(y)\) ذاكرة.
لكل عدد أولي داخل الفترة، فإن اختبار الباقي التربيعي واختزال \(2^{n-1}\) ومرحلة Lucas السريعة تحتاج معًا إلى \(O(\log n+\log p)\) عملية حسابية. لذلك يكون التعقيد الكلي
$$O\!\left(\sqrt{H}\log\log H+y\log\log H+\pi(x,y)(\log n+\log H)\right),$$
بينما استهلاك الذاكرة هو
$$O(\sqrt{H}+y).$$