For integers \(n \ge 2\), define
$$t_n=2n^2-1.$$
Problem 216 asks for the number of indices \(2 \le n \le 50{,}000{,}000\) for which \(t_n\) is prime.
A naive solution would evaluate fifty million numbers of size about \(5\times10^{15}\) and run a primality test on each of them. The implementations take a more number-theoretic route: instead of proving primality one value at a time, they sieve the indices \(n\) for which some smaller prime is known to divide \(2n^2-1\). The survivors are exactly the prime values.
The key observation is that divisibility of \(2n^2-1\) by a fixed prime turns into a modular square-root problem, so the sequence can be attacked with a residue-class sieve on \(n\).
Let \(N=50{,}000{,}000\). If \(t_n\) is composite, then it has a prime divisor \(p\) with
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
Therefore every composite value \(2n^2-1\) is detected by some prime at most \(\sqrt{2N^2-1}\). Conversely, if no prime in that range divides \(t_n\), then \(t_n\) has no proper prime factor and must itself be prime. This is the invariant that makes the sieve correct.
Since \(2n^2-1\) is always odd, the prime \(2\) can never divide it, so only odd primes need to be examined.
If an odd prime \(p\) divides \(t_n\), then
$$2n^2\equiv1\pmod p,$$
hence
$$n^2\equiv2^{-1}\pmod p.$$
For odd \(p\), the inverse of \(2\) modulo \(p\) is
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
because \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
So the congruence has a solution exactly when \(2^{-1}\), and therefore also \(2\), is a quadratic residue modulo \(p\). By the classical formula
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8},$$
this happens precisely for
$$p\equiv1\text{ or }7\pmod8.$$
That congruence filter removes half of the odd primes immediately. Any prime with \(p\equiv3\) or \(5\pmod8\) cannot divide a value of the form \(2n^2-1\).
For each eligible prime \(p\), solve
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
If one solution is \(r\), then the second is \(-r\pmod p\). Every integer \(n\) satisfying
$$n\equiv r\pmod p \qquad\text{or}\qquad n\equiv-r\pmod p$$
makes \(p\mid(2n^2-1)\). Therefore the composite values are found by marking at most two arithmetic progressions for each relevant prime.
This is the central reduction: the original primality problem over very large integers is converted into a structured sieve over residue classes of the index \(n\).
The implementations split the root-finding step into two cases.
If \(p\equiv7\pmod8\), then \(p\equiv3\pmod4\), and \(2\) has the explicit square root
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
Multiplying by \(2^{-1}\) gives a square root of \(2^{-1}\):
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
If \(p\equiv1\pmod8\), there is no equally short special formula in general, so the implementations use the Tonelli-Shanks algorithm to compute a square root of \((p+1)/2\) modulo \(p\). In both cases the second residue class is obtained by negation modulo \(p\).
One subtlety is essential. When the sieve processes a prime \(p\), it marks every index \(n\) such that \(p\mid(2n^2-1)\). But sometimes that value is not composite at all: it can equal \(p\) itself. The equality
$$2n^2-1=p$$
is equivalent to
$$n^2=\frac{p+1}{2}.$$
So there is exactly one index to skip whenever \((p+1)/2\) is an ordinary integer square. The implementations test that condition once per prime, and if it holds they leave that single \(n\) unmarked while still marking the rest of the progression.
Without this correction, every prime of the special form \(p=2m^2-1\) would incorrectly eliminate its own generating index \(n=m\).
Take \(p=7\). Then
$$2^{-1}\equiv4\pmod7,$$
so the relevant congruence is
$$n^2\equiv4\pmod7.$$
Its two roots are \(n\equiv2\) and \(n\equiv5\pmod7\). Therefore every \(n\) in either residue class makes \(7\mid(2n^2-1)\).
Now list the values for \(2\le n\le8\):
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
The classes \(2\) and \(5\) modulo \(7\) hit \(n=2\) and \(n=5\) in this interval. The first one must be skipped because
$$2\cdot2^2-1=7,$$
which is prime, not composite. The second one is correctly marked because
$$2\cdot5^2-1=49=7^2.$$
This tiny example already contains the whole method: solve one modular equation, mark its residue classes, and protect the one possible self-factor case.
The C++, Python, and Java implementations follow the same algorithmic structure. They first generate all primes up to \(\sqrt{2N^2-1}\), then maintain an array indexed by \(n\) recording whether \(2n^2-1\) has been proved composite by at least one sieving prime.
The first phase is a standard prime sieve. Each prime is then filtered by its residue modulo \(8\): \(2\) is discarded because \(2n^2-1\) is odd, and primes congruent to \(3\) or \(5\) modulo \(8\) are ignored because the congruence \(n^2\equiv2^{-1}\pmod p\) has no solution for them.
For every remaining prime, the implementation computes one root of \((p+1)/2\) modulo \(p\). When \(p\equiv7\pmod8\), it uses the direct power formula; when \(p\equiv1\pmod8\), it uses Tonelli-Shanks. The second root is the negative of the first one modulo \(p\).
Those roots define up to two arithmetic progressions of valid indices. The implementation advances from the first term in each progression that is at least \(2\), then steps forward by \(p\), marking every visited index as composite.
Before the marking loop begins, the implementation checks whether \((p+1)/2\) is an exact integer square. If so, that single index is excluded from marking, because its value is \(p\) itself rather than a composite multiple of \(p\).
After all relevant primes have been processed, the answer is the number of unmarked indices \(n\ge2\). By the sieving invariant, these are exactly the \(n\) for which \(2n^2-1\) is prime.
Let \(N\) denote the upper limit for \(n\). The initial prime sieve runs up to \(\sqrt{2}N\), so its cost is on the usual order of
$$O(N\log\log N).$$
The dominant work is the marking of arithmetic progressions. For each relevant prime \(p\), at most two residue classes are visited, which gives a total cost comparable to
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N).$$
The modular square-root computations add extra work, but they do not change the overall asymptotic behavior of the sieve. Memory usage is \(O(N)\), because the implementations store one boolean or byte flag for each index \(n\).
Für ganze Zahlen \(n \ge 2\) sei
$$t_n=2n^2-1.$$
In Problem 216 soll gezählt werden, für wie viele Indizes \(2 \le n \le 50{,}000{,}000\) der Wert \(t_n\) eine Primzahl ist.
Ein naiver Ansatz würde fünfzig Millionen Zahlen der Größenordnung \(5\times10^{15}\) erzeugen und jede davon einzeln auf Primzahleigenschaft testen. Die Implementierungen gehen genau andersherum vor: Sie sieben die Indizes \(n\) aus, für die bereits bekannt ist, dass ein kleinerer Primteiler \(2n^2-1\) teilt. Übrig bleiben genau die Primwerte.
Der Ausdruck \(2n^2-1\) eignet sich besonders gut für ein Sieb über den Index \(n\), weil Teilbarkeit durch eine feste Primzahl auf ein Problem über quadratische Reste modulo \(p\) führt.
Sei \(N=50{,}000{,}000\). Falls \(t_n\) zusammengesetzt ist, besitzt es einen Primteiler \(p\) mit
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
Also wird jeder zusammengesetzte Wert \(2n^2-1\) bereits von einer Primzahl höchstens \(\sqrt{2N^2-1}\) entdeckt. Umgekehrt gilt: Teilt keine Primzahl in diesem Bereich den Wert \(t_n\), dann hat \(t_n\) überhaupt keinen echten Primteiler und muss selbst prim sein. Genau auf diesem Invarianzgedanken beruht das gesamte Verfahren.
Da \(2n^2-1\) immer ungerade ist, kommt \(p=2\) als Teiler nie in Frage; untersucht werden nur ungerade Primzahlen.
Wenn eine ungerade Primzahl \(p\) den Wert \(t_n\) teilt, dann gilt
$$2n^2\equiv1\pmod p,$$
also
$$n^2\equiv2^{-1}\pmod p.$$
Für ungerades \(p\) ist das Inverse von \(2\) modulo \(p\)
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
denn \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
Damit ist die Kongruenz genau dann lösbar, wenn \(2^{-1}\) und damit auch \(2\) ein quadratischer Rest modulo \(p\) ist. Mit der klassischen Formel
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
ergibt sich das äquivalent zu
$$p\equiv1\text{ oder }7\pmod8.$$
Diese Kongruenzbedingung verwirft sofort die Hälfte aller ungeraden Primzahlen. Für \(p\equiv3\) oder \(5\pmod8\) kann keine Zahl der Form \(2n^2-1\) durch \(p\) teilbar sein.
Für jede zugelassene Primzahl \(p\) löst man
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
Ist \(r\) eine Lösung, dann ist \(-r\pmod p\) die zweite. Jedes \(n\) mit
$$n\equiv r\pmod p \qquad\text{oder}\qquad n\equiv-r\pmod p$$
erfüllt \(p\mid(2n^2-1)\). Zusammengesetzte Werte werden daher gefunden, indem man für jede relevante Primzahl höchstens zwei arithmetische Progressionen markiert.
Genau hier liegt die entscheidende Reduktion: Aus einem Primzahlproblem über sehr große Zahlen wird ein strukturiertes Sieb über Restklassen des Indexes \(n\).
Die Implementierungen trennen den Wurzel-Schritt in zwei Fälle.
Falls \(p\equiv7\pmod8\), gilt zugleich \(p\equiv3\pmod4\), und \(2\) besitzt die explizite Quadratwurzel
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
Durch Multiplikation mit \(2^{-1}\) erhält man eine Quadratwurzel von \(2^{-1}\):
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
Falls dagegen \(p\equiv1\pmod8\), gibt es im Allgemeinen keine gleich kurze Spezialformel; dort verwenden die Implementierungen den Tonelli-Shanks-Algorithmus, um eine Quadratwurzel von \((p+1)/2\) modulo \(p\) zu berechnen. In beiden Fällen entsteht die zweite Restklasse durch Negation modulo \(p\).
Eine Feinheit ist unverzichtbar. Wenn das Sieb die Primzahl \(p\) verarbeitet, markiert es alle Indizes \(n\) mit \(p\mid(2n^2-1)\). Manchmal ist dieser Wert aber gar nicht zusammengesetzt, sondern gleich \(p\) selbst. Die Gleichung
$$2n^2-1=p$$
ist äquivalent zu
$$n^2=\frac{p+1}{2}.$$
Also gibt es genau dann einen zu überspringenden Index, wenn \((p+1)/2\) als gewöhnliche ganze Zahl ein Quadrat ist. Die Implementierungen testen diese Bedingung einmal pro Primzahl und lassen diesen einen Index unmarkiert, während alle übrigen Treffer derselben Progression weiterhin gestrichen werden.
Ohne diese Korrektur würde jede Primzahl der Form \(p=2m^2-1\) fälschlich ihren eigenen Ursprungsindex \(n=m\) entfernen.
Betrachte \(p=7\). Dann gilt
$$2^{-1}\equiv4\pmod7,$$
also lautet die relevante Kongruenz
$$n^2\equiv4\pmod7.$$
Die beiden Lösungen sind \(n\equiv2\) und \(n\equiv5\pmod7\). Jede Zahl in einer dieser Restklassen liefert also \(7\mid(2n^2-1)\).
Für \(2\le n\le8\) erhält man die Folge
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
Die Restklassen \(2\) und \(5\) modulo \(7\) treffen in diesem Bereich auf \(n=2\) und \(n=5\). Der erste Wert muss ausgelassen werden, denn
$$2\cdot2^2-1=7$$
ist prim und nicht zusammengesetzt. Der zweite Treffer wird korrekt markiert, denn
$$2\cdot5^2-1=49=7^2.$$
Dieses kleine Beispiel enthält bereits die komplette Methode: eine modulare Gleichung lösen, die zugehörigen Restklassen markieren und den einen möglichen Selbstteiler-Fall schützen.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst werden alle Primzahlen bis \(\sqrt{2N^2-1}\) erzeugt. Danach wird ein Array über den Indizes \(n\) gehalten, das speichert, ob \(2n^2-1\) bereits durch mindestens eine Siebprimzahl als zusammengesetzt erkannt wurde.
Die erste Phase ist ein gewöhnliches Primzahlsieb. Anschließend wird jede Primzahl über ihre Restklasse modulo \(8\) gefiltert: \(2\) wird sofort verworfen, weil \(2n^2-1\) ungerade ist, und Primzahlen mit \(p\equiv3\) oder \(5\pmod8\) werden ignoriert, weil dort die Kongruenz \(n^2\equiv2^{-1}\pmod p\) keine Lösung besitzt.
Für jede verbleibende Primzahl berechnet die Implementierung eine Quadratwurzel von \((p+1)/2\) modulo \(p\). Für \(p\equiv7\pmod8\) wird die direkte Potenzformel verwendet; für \(p\equiv1\pmod8\) kommt Tonelli-Shanks zum Einsatz. Die zweite Wurzel ist jeweils das negative dieser ersten Wurzel modulo \(p\).
Aus diesen Wurzeln entstehen bis zu zwei arithmetische Progressionen von gültigen Indizes. Die Implementierung springt zum jeweils ersten Glied der Progression, das mindestens \(2\) ist, und schreitet dann in Schritten von \(p\) weiter, wobei jeder besuchte Index als zusammengesetzt markiert wird.
Bevor die Markierung beginnt, wird geprüft, ob \((p+1)/2\) ein exaktes Quadrat in den ganzen Zahlen ist. Falls ja, wird genau dieser Index von der Markierung ausgenommen, weil sein Wert nicht ein zusammengesetztes Vielfaches von \(p\), sondern \(p\) selbst ist.
Nachdem alle relevanten Primzahlen verarbeitet wurden, besteht die Antwort einfach aus der Anzahl unmarkierter Indizes \(n\ge2\). Wegen des Siebinvarianten sind dies genau die Werte, für die \(2n^2-1\) prim ist.
Sei \(N\) die Obergrenze für \(n\). Das anfängliche Primzahlsieb läuft bis \(\sqrt{2}N\) und kostet daher in der üblichen Modellierung
$$O(N\log\log N).$$
Die dominierende Arbeit ist das Markieren der arithmetischen Progressionen. Für jede relevante Primzahl \(p\) werden höchstens zwei Restklassen besucht, daher ist der Gesamtaufwand vergleichbar mit
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N).$$
Die modularen Quadratwurzelberechnungen erzeugen zusätzlichen Aufwand, ändern aber nicht die asymptotische Gesamtordnung des Siebs. Der Speicherverbrauch ist \(O(N)\), weil für jeden Index \(n\) genau ein boolesches oder byteweises Markierungsfeld vorgehalten wird.
\(n \ge 2\) için
$$t_n=2n^2-1$$
tanımlansın. Problem 216, \(2 \le n \le 50{,}000{,}000\) aralığında bu değerlerden kaç tanesinin asal olduğunu sorar.
Doğrudan yaklaşım, yaklaşık \(5\times10^{15}\) büyüklüğünde elli milyon sayı üretip her biri için ayrı asal testi yapmaktır. Uygulamalar bunun tersini yapar: \(2n^2-1\) ifadesinin hangi \(n\) değerlerinde daha küçük bir asal tarafından bölündüğünü topluca bulur, yani indeksler üzerinde bir eleme uygular. İşaretlenmeden kalan indeksler tam olarak asal değerleri verir.
\(2n^2-1\) biçimi, sabit bir asala bölünebilme koşulunu modüler karekök problemine çevirdiği için \(n\) üzerinde çalışan bir eleme için çok uygundur.
\(N=50{,}000{,}000\) olsun. Eğer \(t_n\) bileşikse, o zaman onu bölen bir asal \(p\) vardır ve
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
Dolayısıyla her bileşik \(2n^2-1\) değeri, en geç \(\sqrt{2N^2-1}\) sınırına kadar olan bir asal tarafından yakalanır. Tersine, bu aralıktaki hiçbir asal \(t_n\)'yi bölmüyorsa \(t_n\)'nin artık gerçek bir asal böleni kalmaz; o halde sayı asaldır. Bütün yöntemin temel doğruluk ilkesi budur.
Ayrıca \(2n^2-1\) her zaman tek sayı olduğundan \(p=2\) baştan elenir; yalnızca tek asalları incelemek gerekir.
Tek bir asal \(p\), \(t_n\)'yi bölüyorsa
$$2n^2\equiv1\pmod p$$
ve dolayısıyla
$$n^2\equiv2^{-1}\pmod p$$
olur. Tek \(p\) için \(2\)'nin modüler tersi
$$2^{-1}\equiv\frac{p+1}{2}\pmod p$$
şeklindedir; çünkü \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
Demek ki problem, \((p+1)/2\)'nin mod \(p\) altında kuadratik artık olup olmadığını sormaya indirgenir. Klasik formül
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
bize bunun tam olarak
$$p\equiv1\text{ veya }7\pmod8$$
durumunda gerçekleştiğini söyler. Böylece \(p\equiv3\) veya \(5\pmod8\) olan bütün asallar hiçbir ek iş yapılmadan elenir.
Uygun bir asal \(p\) için
$$n^2\equiv\frac{p+1}{2}\pmod p$$
kongruansı çözülür. Bir çözüm \(r\) ise öteki çözüm \(-r\pmod p\)'dir. Şu iki artık sınıfından birine düşen her \(n\)
$$n\equiv r\pmod p \qquad\text{veya}\qquad n\equiv-r\pmod p$$
\(p\mid(2n^2-1)\) özelliğine sahiptir. Bu yüzden bileşik adayları, her ilgili asal için en fazla iki aritmetik diziyi işaretleyerek bulunur.
Asıl dönüşüm burada ortaya çıkar: çok büyük sayıların asal olup olmadığını tek tek sınamak yerine, indeks uzayında düzenli artık sınıfları taranır.
Uygulamalar kök bulma işini iki duruma ayırır.
Eğer \(p\equiv7\pmod8\) ise aynı zamanda \(p\equiv3\pmod4\) olur ve \(2\)'nin açık karekökü vardır:
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
Bunu \(2^{-1}\) ile çarpmak, \(2^{-1}\)'in bir karekökünü verir:
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
Eğer \(p\equiv1\pmod8\) ise bu kadar kısa bir özel formül genel olarak yoktur; bu durumda uygulamalar \((p+1)/2\)'nin mod \(p\) altındaki karekökünü Tonelli-Shanks algoritması ile bulur. Her iki durumda da ikinci kök, ilkinin mod \(p\) altında negatifidir.
Burada çok önemli bir incelik vardır. Eleme, bir asal \(p\) için \(p\mid(2n^2-1)\) olan bütün indeksleri işaretler. Ama bazen bu değer bileşik değildir; doğrudan \(p\)'nin kendisidir. Şu eşitlik
$$2n^2-1=p$$
yeniden düzenlenince
$$n^2=\frac{p+1}{2}$$
elde edilir. Demek ki \((p+1)/2\) tam kare ise tam bir tane atlanması gereken indeks vardır. Uygulamalar bu testi her asal için bir kez yapar ve koşul sağlanıyorsa sadece o tek \(n\) değerini işaretlemeden bırakır.
Bu düzeltme olmazsa \(p=2m^2-1\) biçimindeki her asal, kendi üretildiği \(n=m\) indeksini yanlışlıkla silmiş olurdu.
\(p=7\) alalım. Bu durumda
$$2^{-1}\equiv4\pmod7$$
olduğundan çözmemiz gereken kongruans
$$n^2\equiv4\pmod7$$
olur. Bunun kökleri \(n\equiv2\) ve \(n\equiv5\pmod7\)'dir. Yani bu iki artık sınıfındaki her \(n\), \(7\)'nin \(2n^2-1\)'i bölmesini sağlar.
Şimdi \(2\le n\le8\) aralığındaki değerleri yazalım:
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
\(7\)'ye göre \(2\) ve \(5\) artık sınıfları bu aralıkta \(n=2\) ve \(n=5\)'e denk gelir. İlki atlanmalıdır; çünkü
$$2\cdot2^2-1=7$$
asal bir sayıdır. İkinci isabet doğru biçimde işaretlenir; çünkü
$$2\cdot5^2-1=49=7^2.$$
Bu küçük örnek, bütün algoritmanın özünü gösterir: modüler denklemi çöz, ilgili artık sınıflarını işaretle ve tek olası öz-bölen durumunu koru.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce \(\sqrt{2N^2-1}\) sınırına kadar olan tüm asallar üretilir. Sonra \(n\) ile indekslenen bir dizi tutulur; bu dizinin her hücresi, \(2n^2-1\) değerinin en az bir asal tarafından bileşik olduğunun kanıtlanıp kanıtlanmadığını gösterir.
İlk faz klasik bir asal eleğidir. Sonrasında her asal, \(8\)'e göre kalanı üzerinden süzülür: \(2\) sayısı doğrudan atılır, çünkü \(2n^2-1\) tektir; \(3\) veya \(5\pmod8\) sınıfındaki asallar da yok sayılır, çünkü onlar için \(n^2\equiv2^{-1}\pmod p\) çözümsüzdür.
Geriye kalan her asal için uygulama, \((p+1)/2\)'nin mod \(p\) altındaki bir karekökünü hesaplar. \(p\equiv7\pmod8\) olduğunda doğrudan üs alma formülü kullanılır; \(p\equiv1\pmod8\) olduğunda Tonelli-Shanks devreye girer. İkinci kök, birincinin modüler negatifidir.
Bu kökler en fazla iki aritmetik dizi tanımlar. Uygulama, her dizinin \(2\)'den küçük olmayan ilk terimine sıçrar, sonra her adımda \(p\) ekleyerek ilerler ve ziyaret ettiği indeksleri bileşik olarak işaretler.
İşaretleme başlamadan önce \((p+1)/2\)'nin tam kare olup olmadığı kontrol edilir. Eğer öyleyse, bu tek indeks işaretlenmez; çünkü karşılık gelen değer bileşik bir \(p\) katı değil, doğrudan \(p\)'dir.
Tüm ilgili asallar işlendiğinde geriye sadece işaretlenmemiş indekslerin sayılması kalır. Elemenin doğruluk ilkesine göre bunlar tam olarak \(2n^2-1\)'in asal olduğu \(n\) değerleridir.
\(N\), \(n\) için üst sınır olsun. Başlangıçtaki asal eleği \(\sqrt{2}N\) seviyesine kadar çalıştığı için standart modelde maliyeti
$$O(N\log\log N)$$
mertebesindedir.
Baskın maliyet, aritmetik dizilerin işaretlenmesidir. Her uygun asal \(p\) için en fazla iki artık sınıfı tarandığından toplam iş
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N)$$
davranışı gösterir. Modüler karekök hesapları ek bir yük getirir, fakat elemenin toplam asimptotik düzenini değiştirmez. Bellek kullanımı \(O(N)\)'dir; çünkü her \(n\) için tek bir boole ya da baytlık işaret tutulur.
Para enteros \(n \ge 2\), definimos
$$t_n=2n^2-1.$$
El Problema 216 pide contar cuántos índices \(2 \le n \le 50{,}000{,}000\) producen un valor primo de \(t_n\).
Un enfoque ingenuo generaría cincuenta millones de números de tamaño cercano a \(5\times10^{15}\) y aplicaría una prueba de primalidad a cada uno. Las implementaciones hacen lo contrario: criban los índices \(n\) para los que ya se sabe que algún primo más pequeño divide a \(2n^2-1\). Los índices que sobreviven son exactamente aquellos para los que el valor es primo.
La forma \(2n^2-1\) es ideal para una criba sobre el índice \(n\), porque la divisibilidad por un primo fijo se convierte en un problema de raíces cuadradas modulares.
Sea \(N=50{,}000{,}000\). Si \(t_n\) es compuesto, entonces tiene un divisor primo \(p\) tal que
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
Por tanto, todo valor compuesto \(2n^2-1\) queda detectado por algún primo menor o igual que \(\sqrt{2N^2-1}\). Recíprocamente, si ningún primo de ese rango divide a \(t_n\), entonces \(t_n\) no tiene divisor primo propio y debe ser primo. Ese es el invariante fundamental de la solución.
Además, \(2n^2-1\) siempre es impar, así que el primo \(2\) nunca interviene y puede descartarse de inmediato.
Si un primo impar \(p\) divide a \(t_n\), entonces
$$2n^2\equiv1\pmod p,$$
y por tanto
$$n^2\equiv2^{-1}\pmod p.$$
Para \(p\) impar, el inverso de \(2\) módulo \(p\) es
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
porque \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
La congruencia tiene solución exactamente cuando \(2^{-1}\), y por lo tanto también \(2\), es un residuo cuadrático módulo \(p\). La fórmula clásica
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
muestra que esto ocurre precisamente cuando
$$p\equiv1\text{ o }7\pmod8.$$
Ese filtro elimina la mitad de los primos impares sin trabajo adicional. Si \(p\equiv3\) o \(5\pmod8\), ningún término de la forma \(2n^2-1\) puede ser divisible por \(p\).
Para cada primo permitido \(p\), se resuelve
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
Si una solución es \(r\), la otra es \(-r\pmod p\). Todo entero \(n\) que satisfaga
$$n\equiv r\pmod p \qquad\text{o}\qquad n\equiv-r\pmod p$$
cumple \(p\mid(2n^2-1)\). Así, los valores compuestos se detectan marcando a lo sumo dos progresiones aritméticas por cada primo relevante.
Esta es la reducción central: el problema original sobre primalidad de enteros enormes se transforma en una criba estructurada sobre clases de residuos del índice \(n\).
Las implementaciones separan este paso en dos casos.
Si \(p\equiv7\pmod8\), entonces también \(p\equiv3\pmod4\), y \(2\) tiene la raíz cuadrada explícita
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
Multiplicar por \(2^{-1}\) produce una raíz cuadrada de \(2^{-1}\):
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
Si \(p\equiv1\pmod8\), no existe en general una fórmula corta comparable, así que las implementaciones usan el algoritmo de Tonelli-Shanks para hallar una raíz cuadrada de \((p+1)/2\) módulo \(p\). En ambos casos la segunda clase de residuos se obtiene negando la primera raíz módulo \(p\).
Hay un detalle crucial. Al procesar un primo \(p\), la criba marca todos los índices \(n\) tales que \(p\mid(2n^2-1)\). Pero a veces ese valor no es compuesto: puede ser exactamente el propio \(p\). La igualdad
$$2n^2-1=p$$
equivale a
$$n^2=\frac{p+1}{2}.$$
Por eso existe exactamente un índice que debe excluirse cuando \((p+1)/2\) es un cuadrado perfecto entero. Las implementaciones comprueban esa condición una vez por cada primo y, si se cumple, dejan sin marcar ese único \(n\) mientras siguen marcando el resto de la progresión.
Sin esta corrección, todo primo de la forma \(p=2m^2-1\) eliminaría incorrectamente su propio índice generador \(n=m\).
Tomemos \(p=7\). Entonces
$$2^{-1}\equiv4\pmod7,$$
así que la congruencia relevante es
$$n^2\equiv4\pmod7.$$
Sus raíces son \(n\equiv2\) y \(n\equiv5\pmod7\). En consecuencia, todo \(n\) en una de esas dos clases hace que \(7\) divida a \(2n^2-1\).
Ahora listemos los valores para \(2\le n\le8\):
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
Las clases \(2\) y \(5\) módulo \(7\) alcanzan a \(n=2\) y \(n=5\) dentro de ese intervalo. El primero debe omitirse, porque
$$2\cdot2^2-1=7$$
es primo, no compuesto. El segundo sí debe marcarse, ya que
$$2\cdot5^2-1=49=7^2.$$
Este ejemplo pequeño contiene todo el algoritmo: resolver una ecuación modular, marcar las clases de residuos resultantes y proteger el único posible caso de auto-factorización.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero generan todos los primos hasta \(\sqrt{2N^2-1}\). Después mantienen un arreglo indexado por \(n\) que indica si el valor \(2n^2-1\) ya ha sido demostrado compuesto por al menos un primo del cribado.
La primera fase es una criba ordinaria de primos. Luego cada primo se filtra por su residuo módulo \(8\): se descarta el \(2\) porque \(2n^2-1\) es impar, y se ignoran los primos congruentes con \(3\) o \(5\pmod8\) porque para ellos la congruencia \(n^2\equiv2^{-1}\pmod p\) no tiene solución.
Para cada primo restante, la implementación calcula una raíz cuadrada de \((p+1)/2\) módulo \(p\). Si \(p\equiv7\pmod8\), utiliza la fórmula directa mediante potencias; si \(p\equiv1\pmod8\), utiliza Tonelli-Shanks. La segunda raíz es simplemente la negación modular de la primera.
Esas raíces definen hasta dos progresiones aritméticas de índices válidos. La implementación avanza hasta el primer término de cada progresión que sea al menos \(2\), y a partir de ahí suma \(p\) repetidamente, marcando todos los índices visitados.
Antes de iniciar el marcado, la implementación comprueba si \((p+1)/2\) es un cuadrado perfecto entero. Si lo es, ese único índice se excluye del marcado, porque su valor no es un múltiplo compuesto de \(p\), sino el propio \(p\).
Tras procesar todos los primos relevantes, la respuesta es simplemente el número de índices no marcados con \(n\ge2\). Por el invariante de la criba, esos son exactamente los \(n\) para los que \(2n^2-1\) es primo.
Sea \(N\) el límite superior de \(n\). La criba inicial de primos llega hasta \(\sqrt{2}N\), así que su coste es del orden habitual
$$O(N\log\log N).$$
El trabajo dominante es marcar las progresiones aritméticas. Para cada primo relevante \(p\), se recorren a lo sumo dos clases de residuos, de modo que el coste total es comparable a
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N).$$
El cálculo de raíces cuadradas modulares añade sobrecoste, pero no cambia el comportamiento asintótico global de la criba. El uso de memoria es \(O(N)\), porque las implementaciones guardan una marca booleana o de byte por cada índice \(n\).
对所有整数 \(n \ge 2\)，定义
$$t_n=2n^2-1.$$
第 216 题要求统计在 \(2 \le n \le 50{,}000{,}000\) 的范围内，有多少个 \(t_n\) 是素数。
如果直接做，需要计算五千万个大约在 \(5\times10^{15}\) 量级的整数，并分别进行素性判定，这在实现上非常低效。这里采用的思路完全不同：不是逐个证明某个 \(2n^2-1\) 是不是素数，而是先找出哪些下标 \(n\) 一定会让某个较小素数整除 \(2n^2-1\)，把这些下标筛掉；最后留下来的下标对应的值就恰好都是素数。
这个问题之所以适合筛法，是因为“某个固定素数 \(p\) 是否整除 \(2n^2-1\)”可以改写成一个模 \(p\) 的平方根问题，而这类问题天然会落到有限个剩余类上。
设 \(N=50{,}000{,}000\)。如果 \(t_n\) 是合数，那么它一定有一个素因子 \(p\) 满足
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
这说明：任何合数 \(2n^2-1\)，都一定会被某个不超过 \(\sqrt{2N^2-1}\) 的素数抓到。反过来说，如果这个范围内没有任何素数能整除 \(t_n\)，那么 \(t_n\) 就不可能还有真素因子，因此它只能是素数。整个算法的正确性正是建立在这个不变量之上。
另外，\(2n^2-1\) 永远是奇数，所以素数 \(2\) 不可能参与整除，可以直接跳过。
如果某个奇素数 \(p\) 整除 \(t_n\)，那么必有
$$2n^2\equiv1\pmod p,$$
也就是
$$n^2\equiv2^{-1}\pmod p.$$
对奇素数 \(p\) 来说，\(2\) 在模 \(p\) 下的逆元就是
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
因为 \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\)。
于是问题变成：\((p+1)/2\) 是否是模 \(p\) 的二次剩余。由于逆元不会改变“是否为平方”的性质，这等价于问 \(2\) 是否是模 \(p\) 的二次剩余。经典公式
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
告诉我们，这恰好发生在
$$p\equiv1\text{ 或 }7\pmod8$$
时成立。于是所有满足 \(p\equiv3\) 或 \(5\pmod8\) 的奇素数都可以提前排除，它们不可能整除任何一个 \(2n^2-1\)。
对每个可能的素数 \(p\)，我们要求解
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
如果一个解是 \(r\)，那么另一个解就是 \(-r\pmod p\)。于是所有满足
$$n\equiv r\pmod p \qquad\text{或}\qquad n\equiv-r\pmod p$$
的整数 \(n\)，都会使 \(p\mid(2n^2-1)\)。这意味着对每个相关素数，我们最多只需要筛掉两条等差数列上的下标。
这一步就是整个方法的核心转化：原题表面上是在判定一批很大的整数是否为素数，实际计算却变成了在下标空间里批量标记若干个固定剩余类。
实现里把求根分成两个情形。
如果 \(p\equiv7\pmod8\)，那么同时也有 \(p\equiv3\pmod4\)，此时 \(2\) 的平方根可以直接写成
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
再乘上 \(2^{-1}\)，就得到 \(2^{-1}\) 的一个平方根：
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
如果 \(p\equiv1\pmod8\)，一般没有这么短的专门公式，于是实现改用 Tonelli-Shanks 算法来求 \((p+1)/2\) 在模 \(p\) 下的平方根。无论是哪一种方法，求出一个根之后，另一个根都可以通过取模意义下的相反数得到。
这里有一个容易漏掉但非常关键的细节。筛法处理素数 \(p\) 时，会把所有满足 \(p\mid(2n^2-1)\) 的下标都标成“合数候选”。可是在某些下标上，这个值并不是合数，而恰好就是素数 \(p\) 本身。方程
$$2n^2-1=p$$
等价于
$$n^2=\frac{p+1}{2}.$$
因此，当且仅当 \((p+1)/2\) 在普通整数意义下是一个完全平方数时，会出现一个需要跳过的下标。实现对每个素数只检查一次这个条件；如果成立，就在标记那两条等差数列时把这唯一的下标保留下来。
如果没有这一步修正，那么所有形如 \(p=2m^2-1\) 的素数都会错误地把它们自己的生成下标 \(n=m\) 从答案中删掉。
取 \(p=7\)。这时
$$2^{-1}\equiv4\pmod7,$$
所以要解的同余式是
$$n^2\equiv4\pmod7.$$
它的两个根是 \(n\equiv2\) 和 \(n\equiv5\pmod7\)。也就是说，所有落在这两个剩余类里的 \(n\)，都会让 \(7\) 整除 \(2n^2-1\)。
现在把 \(2\le n\le8\) 时的数列列出来：
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
模 \(7\) 的剩余类 \(2\) 与 \(5\) 在这个区间里对应到 \(n=2\) 和 \(n=5\)。其中 \(n=2\) 必须跳过，因为
$$2\cdot2^2-1=7$$
本身是素数，不该被当成合数。相反，\(n=5\) 应该被正确标记，因为
$$2\cdot5^2-1=49=7^2.$$
这个小例子已经把整个算法完整展示出来了：先解模方程，再筛对应的剩余类，同时保护唯一可能出现的“自因子”情形。
C++、Python 和 Java 实现遵循同一条主线。第一步是用普通素数筛生成所有不超过 \(\sqrt{2N^2-1}\) 的素数。第二步是维护一个按下标 \(n\) 编号的布尔数组或字节数组，记录 \(2n^2-1\) 是否已经被某个筛选素数证明为合数。
先做标准素数筛，然后根据模 \(8\) 的结果进一步过滤：素数 \(2\) 直接丢掉，因为目标表达式始终为奇数；模 \(8\) 余 \(3\) 或 \(5\) 的素数也直接跳过，因为它们不可能使 \(n^2\equiv2^{-1}\pmod p\) 有解。
对每个保留下来的素数，程序先求出 \((p+1)/2\) 在模 \(p\) 下的一个平方根。若 \(p\equiv7\pmod8\)，用显式幂公式；若 \(p\equiv1\pmod8\)，用 Tonelli-Shanks。另一个根就是它在模 \(p\) 下的相反数。
得到这两个根之后，就得到至多两条需要筛掉的等差数列。程序从每条数列中第一个不小于 \(2\) 的项开始，每次加上 \(p\)，把经过的下标都标记为合数候选。
在真正开始标记之前，程序会检查 \((p+1)/2\) 是否是整数完全平方。如果是，就说明有一个下标对应的值恰好等于 \(p\) 本身，这个位置不能标记为合数，因此会被单独跳过。
当所有相关素数都处理完成后，只需要统计所有没有被标记且满足 \(n\ge2\) 的下标个数即可。根据筛法不变量，这些下标对应的 \(2n^2-1\) 恰好全都是素数。
设 \(N\) 是下标上界。初始素数筛做到 \(\sqrt{2}N\) 的量级，因此其复杂度是常见的
$$O(N\log\log N).$$
主导成本来自后面的等差数列标记。对每个相关素数 \(p\)，最多只会遍历两条剩余类，所以总体工作量与
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N)$$
同阶。模平方根计算会带来额外常数开销，但不会改变整体渐近复杂度。空间复杂度是 \(O(N)\)，因为实现需要为每个下标 \(n\) 保存一个是否已知合数的标记。
Для целых \(n \ge 2\) определим
$$t_n=2n^2-1.$$
В задаче 216 требуется посчитать, для скольких индексов \(2 \le n \le 50{,}000{,}000\) значение \(t_n\) является простым.
Наивный путь состоял бы в том, чтобы вычислить пятьдесят миллионов чисел порядка \(5\times10^{15}\) и отдельно проверять каждое на простоту. Реальные реализации идут в противоположную сторону: они не доказывают простоту каждого значения по отдельности, а просеивают те индексы \(n\), для которых уже известно, что некоторое меньшее простое число делит \(2n^2-1\). Все неотмеченные индексы и дают простые значения.
Выражение \(2n^2-1\) удобно тем, что условие делимости на фиксированное простое число переводится в задачу о квадратном корне по модулю. Благодаря этому можно строить решето не по самим большим числам, а по индексам \(n\).
Пусть \(N=50{,}000{,}000\). Если \(t_n\) составно, то у него есть простой делитель \(p\), удовлетворяющий
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
Значит, каждое составное число вида \(2n^2-1\) обязательно будет обнаружено некоторым простым \(p\le\sqrt{2N^2-1}\). И наоборот, если ни одно простое из этого диапазона не делит \(t_n\), то у \(t_n\) нет собственного простого делителя, а значит, оно само простое. Именно на этом инварианте держится корректность всего метода.
Кроме того, \(2n^2-1\) всегда нечетно, поэтому простое \(2\) сразу исключается из рассмотрения.
Если нечетное простое \(p\) делит \(t_n\), то
$$2n^2\equiv1\pmod p,$$
а значит
$$n^2\equiv2^{-1}\pmod p.$$
Для нечетного \(p\) обратный элемент к \(2\) по модулю \(p\) равен
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
поскольку \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
Следовательно, вопрос сводится к тому, является ли \((p+1)/2\) квадратом по модулю \(p\). Это эквивалентно тому, что и \(2\) является квадратичным вычетом по модулю \(p\). Классическая формула
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
дает точный критерий:
$$p\equiv1\text{ или }7\pmod8.$$
Тем самым все простые \(p\equiv3\) или \(5\pmod8\) отбрасываются сразу: ни одно число вида \(2n^2-1\) не может делиться на них.
Для каждого допустимого простого \(p\) нужно решить сравнение
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
Если один корень равен \(r\), то второй равен \(-r\pmod p\). Тогда любой индекс \(n\), удовлетворяющий
$$n\equiv r\pmod p \qquad\text{или}\qquad n\equiv-r\pmod p,$$
автоматически дает делимость \(p\mid(2n^2-1)\). Значит, для каждого нужного простого достаточно отметить не более двух арифметических прогрессий.
Именно здесь исходная задача о простоте больших чисел превращается в аккуратное решето по классам вычетов индекса \(n\).
Реализации делят этот шаг на два случая.
Если \(p\equiv7\pmod8\), то одновременно \(p\equiv3\pmod4\), и для \(2\) существует короткая формула
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
Умножая это значение на \(2^{-1}\), получаем корень из \(2^{-1}\):
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
Если же \(p\equiv1\pmod8\), столь же короткой универсальной формулы уже нет, и реализации используют алгоритм Тонелли-Шенкса для вычисления квадратного корня из \((p+1)/2\) по модулю \(p\). Во всех случаях второй корень получается как отрицание первого по модулю \(p\).
Есть тонкость, без которой решение было бы неверным. Когда решето обрабатывает простое \(p\), оно отмечает все индексы \(n\), для которых \(p\mid(2n^2-1)\). Но иногда это значение вовсе не составное: оно может совпадать с самим \(p\). Равенство
$$2n^2-1=p$$
равносильно условию
$$n^2=\frac{p+1}{2}.$$
Следовательно, существует ровно один индекс, который надо пропустить, когда \((p+1)/2\) является точным квадратом среди целых чисел. Реализации проверяют это один раз для каждого простого \(p\) и, если условие выполнено, не отмечают этот единственный индекс, продолжая помечать остальные элементы той же прогрессии.
Без такой поправки каждое простое число вида \(p=2m^2-1\) ошибочно вычеркивало бы собственный индекс \(n=m\).
Возьмем \(p=7\). Тогда
$$2^{-1}\equiv4\pmod7,$$
поэтому нужно решить сравнение
$$n^2\equiv4\pmod7.$$
Его корни: \(n\equiv2\) и \(n\equiv5\pmod7\). Значит, любой индекс из этих двух классов вычетов дает делимость \(7\mid(2n^2-1)\).
Теперь выпишем значения при \(2\le n\le8\):
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
Классы \(2\) и \(5\) по модулю \(7\) попадают здесь в \(n=2\) и \(n=5\). Первый индекс необходимо пропустить, потому что
$$2\cdot2^2-1=7$$
само простое число. А второй индекс нужно пометить, поскольку
$$2\cdot5^2-1=49=7^2.$$
Этот маленький пример уже демонстрирует весь алгоритм целиком: решить сравнение, отметить соответствующие классы вычетов и отдельно защитить единственный возможный случай самоделения.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они строят список всех простых чисел до \(\sqrt{2N^2-1}\). Затем создают массив, индексированный по \(n\), где хранится факт, было ли число \(2n^2-1\) уже доказано составным хотя бы одним простым из решета.
Первый этап - обычное решето простых чисел. После этого каждое простое фильтруется по остатку по модулю \(8\): число \(2\) сразу исключается, так как \(2n^2-1\) нечетно, а простые с остатками \(3\) и \(5\) по модулю \(8\) пропускаются, потому что сравнение \(n^2\equiv2^{-1}\pmod p\) для них неразрешимо.
Для каждого оставшегося простого программа находит один квадратный корень из \((p+1)/2\) по модулю \(p\). Если \(p\equiv7\pmod8\), используется явная степенная формула; если \(p\equiv1\pmod8\), используется Тонелли-Шенкс. Второй корень получается как противоположный по модулю \(p\).
Эти корни задают не более двух арифметических прогрессий индексов. Реализация переходит к первому члену каждой прогрессии, который не меньше \(2\), и затем идет вперед шагом \(p\), отмечая все посещенные индексы как составные кандидаты.
Перед началом маркировки проверяется, является ли \((p+1)/2\) точным квадратом в целых числах. Если да, соответствующий единственный индекс пропускается, потому что его значение равно самому \(p\), а не составному кратному \(p\).
После обработки всех релевантных простых ответом становится число неотмеченных индексов \(n\ge2\). По инварианту решета это в точности те \(n\), для которых \(2n^2-1\) простое.
Пусть \(N\) - верхняя граница для \(n\). Начальное решето простых работает до уровня \(\sqrt{2}N\), поэтому его стоимость имеет привычный порядок
$$O(N\log\log N).$$
Основная работа приходится на маркировку арифметических прогрессий. Для каждого подходящего простого \(p\) посещаются не более двух классов вычетов, так что общий объем вычислений сравним с
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N).$$
Вычисление квадратных корней по модулю добавляет накладные расходы, но не меняет асимптотический порядок метода. Память равна \(O(N)\), потому что для каждого индекса \(n\) хранится один булев или байтовый флаг.
لكل عدد صحيح \(n \ge 2\) نعرّف
$$t_n=2n^2-1.$$
تطلب المسألة 216 حساب عدد القيم \(n\) في المجال \(2 \le n \le 50{,}000{,}000\) التي يكون فيها \(t_n\) عددًا أوليًا.
الطريقة الساذجة هي توليد خمسين مليون عدد بحجم يقارب \(5\times10^{15}\) ثم إجراء اختبار أولية مستقل لكل واحد منها. التنفيذات هنا تعتمد الفكرة المعاكسة تمامًا: لا نحاول إثبات أولية كل قيمة مباشرة، بل نبحث عن قيم \(n\) التي نعرف مسبقًا أن عددًا أوليًا أصغر يقسم \(2n^2-1\). كل قيمة \(n\) تنجو من هذا الغربال تعطي قيمة أولية فعلًا.
سبب مناسبة هذه المسألة للغربلة هو أن شرط القسمة على عدد أولي ثابت \(p\) يتحول إلى مسألة إيجاد جذر تربيعي بترديد \(p\)، وهذا يعني أن الحل يقع في عدد صغير من الفئات التوافقية بالنسبة إلى \(n\).
لنضع \(N=50{,}000{,}000\). إذا كانت \(t_n\) عددًا مركبًا، فلا بد أن لها قاسمًا أوليًا \(p\) يحقق
$$p \le \sqrt{t_n} \le \sqrt{2N^2-1}.$$
إذن كل قيمة مركبة من الشكل \(2n^2-1\) ستُكتشف بواسطة عدد أولي لا يتجاوز \(\sqrt{2N^2-1}\). وبالعكس، إذا لم يقسم أي عدد أولي في هذا المجال القيمة \(t_n\)، فليس لها قاسم أولي حقيقي، وبالتالي لا بد أن تكون أولية. هذه هي الفكرة الثابتة التي تضمن صحة الطريقة كلها.
ولأن \(2n^2-1\) عدد فردي دائمًا، فإن العدد الأولي \(2\) لا يمكن أن يقسمه، ولذلك يُستبعد من البداية.
إذا كان عدد أولي فردي \(p\) يقسم \(t_n\)، فإن
$$2n^2\equiv1\pmod p,$$
ومن ثم
$$n^2\equiv2^{-1}\pmod p.$$
ولكل \(p\) فردي يكون معكوس \(2\) بترديد \(p\) هو
$$2^{-1}\equiv\frac{p+1}{2}\pmod p,$$
لأن \(2\cdot\frac{p+1}{2}=p+1\equiv1\pmod p\).
إذًا المسألة تختزل إلى السؤال: هل \((p+1)/2\) بقايا تربيعية بترديد \(p\)؟ وهذا مكافئ تمامًا لكون \(2\) نفسها بقايا تربيعية. وباستخدام العلاقة الكلاسيكية
$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$
نحصل على الشرط الدقيق التالي: يجب أن يكون \(p\) في أحد الصنفين التوافقيين الآتيين.
$$p\equiv1\pmod8,\qquad p\equiv7\pmod8.$$
وهكذا تُحذف جميع الأعداد الأولية التي تحقق \(p\equiv3\) أو \(5\pmod8\) مباشرة، لأنها لا يمكن أن تقسم أي قيمة من الشكل \(2n^2-1\).
لكل عدد أولي مناسب \(p\)، نحل المقارنة
$$n^2\equiv\frac{p+1}{2}\pmod p.$$
إذا كان أحد الحلين هو \(r\)، فالحل الآخر هو \(-r\pmod p\). لذلك كل \(n\) يقع في أحد الصنفين التاليين
$$n\equiv r\pmod p,\qquad n\equiv-r\pmod p$$
يجعل \(p\mid(2n^2-1)\). وهذا يعني أن الغربال لا يحتاج، لكل عدد أولي مناسب، إلا إلى تعليم قيم \(n\) الواقعة في متتاليتين حسابيتين على الأكثر.
هذه هي النقلة الأساسية: بدلًا من اختبار أولية أعداد ضخمة واحدةً واحدة، نعمل على فضاء المؤشرات \(n\) ونستبعد فئات توافقية منتظمة.
التنفيذات تقسم هذه الخطوة إلى حالتين.
إذا كان \(p\equiv7\pmod8\)، فهذا يعني أيضًا أن \(p\equiv3\pmod4\)، وعندها يوجد تعبير مباشر لجذر \(2\):
$$\sqrt{2}\equiv2^{(p+1)/4}\pmod p.$$
وبضرب هذا الجذر في \(2^{-1}\) نحصل على جذر لـ \(2^{-1}\):
$$r\equiv2^{(p+1)/4}\cdot\frac{p+1}{2}\pmod p.$$
أما إذا كان \(p\equiv1\pmod8\)، فلا توجد عمومًا صيغة قصيرة مماثلة، ولذلك تستخدم التنفيذات خوارزمية Tonelli-Shanks لإيجاد جذر تربيعي لـ \((p+1)/2\) بترديد \(p\). وفي الحالتين يكون الجذر الآخر هو السالب المعياري للجذر الأول.
هناك تفصيل مهم جدًا. عندما يعالج الغربال عددًا أوليًا \(p\)، فهو يعلّم كل قيمة \(n\) تحقق \(p\mid(2n^2-1)\). لكن أحيانًا لا تكون القيمة الناتجة مركبة أصلًا، بل تساوي \(p\) نفسه. المعادلة
$$2n^2-1=p$$
تكافئ
$$n^2=\frac{p+1}{2}.$$
إذن يوجد مؤشر واحد فقط يجب استثناؤه عندما تكون \((p+1)/2\) مربعًا كاملًا في الأعداد الصحيحة. التنفيذات تختبر هذا الشرط مرة واحدة لكل عدد أولي، وإذا تحقق فإنها تترك هذا المؤشر الوحيد بدون تعليم بينما تستمر في تعليم بقية عناصر المتتالية.
من دون هذا التصحيح، فإن كل عدد أولي من الشكل \(p=2m^2-1\) سيحذف خطأً المؤشر الذي ولّده أصلًا، أي \(n=m\).
لنأخذ \(p=7\). عندئذ
$$2^{-1}\equiv4\pmod7,$$
فتصبح المقارنة المطلوبة
$$n^2\equiv4\pmod7.$$
وجذراها هما \(n\equiv2\) و\(n\equiv5\pmod7\). لذلك كل \(n\) يقع في إحدى هاتين الفئتين يجعل \(7\) يقسم \(2n^2-1\).
إذا كتبنا القيم عندما \(2\le n\le8\) نحصل على
$$7,\ 17,\ 31,\ 49,\ 71,\ 97,\ 127.$$
الفئتان \(2\) و\(5\) بترديد \(7\) تصيبان هنا \(n=2\) و\(n=5\). يجب تجاهل \(n=2\) لأن
$$2\cdot2^2-1=7$$
عدد أولي وليس مركبًا. أما \(n=5\) فيجب تعليمه فعلًا لأن
$$2\cdot5^2-1=49=7^2.$$
هذا المثال الصغير يعرض الخوارزمية كاملة بصيغة مصغرة: نحل مقارنة معيارية، نعلّم الفئات الناتجة، ثم نحمي الحالة الوحيدة الممكنة التي يكون فيها العامل الأولي مساويًا للقيمة نفسها.
تنفيذات C++ وPython وJava تتبع المسار نفسه. أولًا تولّد جميع الأعداد الأولية حتى \(\sqrt{2N^2-1}\). ثم تحتفظ بمصفوفة مفهرسة حسب \(n\) تبيّن هل ثبت أن القيمة \(2n^2-1\) مركبة بواسطة أحد الأعداد الأولية في الغربال أم لا.
المرحلة الأولى هي غربال أولي تقليدي. بعد ذلك يُفحص كل عدد أولي حسب باقيه modulo \(8\): يُستبعد \(2\) مباشرة لأن \(2n^2-1\) فردي، كما تُهمل جميع الأعداد الأولية ذات الباقي \(3\) أو \(5\pmod8\) لأن المقارنة \(n^2\equiv2^{-1}\pmod p\) لا تملك حلولًا فيها.
لكل عدد أولي يبقى بعد الفلترة، يحسب التنفيذ جذرًا تربيعيًا واحدًا لـ \((p+1)/2\) بترديد \(p\). إذا كان \(p\equiv7\pmod8\) يستخدم الصيغة المباشرة بالقوى؛ وإذا كان \(p\equiv1\pmod8\) يستخدم Tonelli-Shanks. الجذر الثاني هو السالب المعياري للأول.
هاتان الجذران تحددان على الأكثر متتاليتين حسابيتين من المؤشرات. يبدأ التنفيذ من أول حد في كل متتالية لا يقل عن \(2\)، ثم يزيد بمقدار \(p\) في كل مرة ويعلّم كل مؤشر يمر به على أنه مركب.
قبل بدء التعليم، يفحص التنفيذ ما إذا كانت \((p+1)/2\) مربعًا كاملًا صحيحًا. إذا كانت كذلك، فإن هذا المؤشر الوحيد لا يُعلَّم، لأن القيمة المقابلة له ليست مضاعفًا مركبًا للعدد \(p\)، بل هي \(p\) نفسه.
بعد معالجة جميع الأعداد الأولية المناسبة، تكون الإجابة ببساطة هي عدد المؤشرات غير المعلَّمة مع \(n\ge2\). ووفقًا لثابت الغربلة، فهذه هي بالضبط القيم التي يكون فيها \(2n^2-1\) عددًا أوليًا.
إذا رمزنا للحد الأعلى بـ \(N\)، فإن غربال الأعداد الأولية الأولي يصل إلى \(\sqrt{2}N\)، ولذلك تكون كلفته من الرتبة المعتادة
$$O(N\log\log N).$$
أما العمل المهيمن فيأتي من تعليم المتتاليات الحسابية. فلكل عدد أولي مناسب \(p\) نزور فئتين توافقـيتين على الأكثر، ومن ثم يكون مجموع الجهد قريبًا من
$$\sum_{p\le\sqrt{2}N} O\!\left(\frac{N}{p}\right)=O(N\log\log N).$$
حساب الجذور التربيعية المعيارية يضيف كلفة إضافية، لكنه لا يغيّر السلوك التقاربي العام للخوارزمية. أما الذاكرة فهي \(O(N)\)، لأن التنفيذات تخزن علمًا منطقيًا أو بايتًا واحدًا لكل مؤشر \(n\).