Let \(p_n\) be the \(n\)-th prime, and define \(r_n\) as the least nonnegative remainder of
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$$
The task is to find the smallest index \(n\) for which \(r_n\gt 10^{10}\). At first sight this looks like a large modular-exponentiation problem, but modulo \(p_n^2\) almost every binomial term disappears. That collapse is the whole reason the problem becomes easy.
The remainder is governed entirely by the first two terms of the binomial expansion. Once that is written out carefully, the problem stops being about huge powers and becomes a search over prime indices.
Expand both powers around \(p_n\):
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
Adding the two expansions gives
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
Any term with \(k\ge 2\) is already divisible by \(p_n^2\), so modulo \(p_n^2\) only the cases \(k=0\) and \(k=1\) can survive. Which of those survives depends only on the parity of \(n\).
If \(n\) is even, then the constant terms add and the linear terms cancel, so
$$ r_n\equiv 2 \pmod{p_n^2}. $$
Because \(0\le 2\lt p_n^2\), the actual remainder is simply \(r_n=2\). Even indices can therefore never exceed \(10^{10}\).
If \(n\) is odd, then the constant terms cancel and the linear terms add, giving
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
So for odd indices the remainder is controlled by the single quantity \(2np_n\), but at this stage it is still a congruence rather than an exact equality.
The implementations compare \(2np_n\) directly against the limit, so we need to know when \(2np_n\) is already smaller than \(p_n^2\). A simple counting argument is enough. For \(n\ge 5\), the odd numbers
$$ 1,3,5,\dots,2n-1 $$
form a list of exactly \(n\) numbers. Among them, both \(1\) and \(9\) are non-prime, so there are at most \(n-2\) odd primes below \(2n\). Including the prime \(2\), there are at most \(n-1\) primes not exceeding \(2n\). Therefore the \(n\)-th prime must satisfy
$$ p_n\gt 2n \qquad (n\ge 5). $$
For odd \(n\ge 5\) this implies
$$ 0\lt 2np_n\lt p_n^2, $$
so the least nonnegative residue of \(2np_n \pmod{p_n^2}\) is exactly \(2np_n\). Hence
$$ r_n=2np_n. $$
The first solution occurs far beyond \(n=5\), so this is the formula the code can safely search with.
The distinction between congruence and exact remainder matters for tiny odd indices. For \(n=3\), we have \(p_3=5\), so
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
Modulo \(25\), this gives \(280\bmod 25=5\). The linear formula gives \(2np_n=2\cdot 3\cdot 5=30\), and indeed \(30\equiv 5\pmod{25}\), but the exact remainder is \(5\), not \(30\).
For \(n=5\), however, \(p_5=11\) and
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
Now \(348832\bmod 121=110\), and that equals
$$ 2\cdot 5\cdot 11=110. $$
Here no wrap-around occurs because \(2n\lt p_n\). The target threshold is so large that the first qualifying index lies in this stable regime.
The prime number theorem gives the rough estimate \(p_n\sim n\log n\). Substituting that into the odd-index formula yields
$$ 2n^2\log n \gtrsim 10^{10}. $$
This places the crossing a little above \(2\times 10^4\). So the program only needs to generate primes up to roughly the corresponding \(p_n\), which is on the order of a few hundred thousand. That makes a straightforward sequential search entirely adequate.
The C++, Python, and Java implementations all walk through the prime sequence in increasing order so that the current prime and its index are known simultaneously. The C++ and Java versions keep a growing list of earlier primes and test each new integer candidate only by those primes up to its square root. The Python version advances from one prime to the next through a prime-generation routine, but conceptually it performs the same ordered scan.
Each time a new prime \(p_n\) is reached, the implementation first checks whether \(n\) is odd. Even indices are skipped immediately because their remainder is always \(2\). For odd indices, it evaluates the simple expression \(2np_n\) and stops as soon as this exceeds the limit. None of the implementations ever compute \((p_n-1)^n\) or \((p_n+1)^n\) directly. One implementation also verifies the logic against the smaller threshold \(10^9\) before running the full search.
Let \(P\) be the prime where the search stops. After a prime is known, the mathematical test is constant time: parity check plus one multiplication and one comparison.
In the C++ and Java implementations, the real cost is prime generation by incremental trial division. A candidate \(c\) is tested only by previously found primes up to \(\sqrt c\), so a standard worst-case estimate is
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
with memory usage \(O(\pi(P))\) for the stored primes. For this problem \(P\) is only a few \(10^5\), so that cost is small in practice. The Python implementation delegates prime stepping to a library routine, but from the problem's point of view it still performs one constant-time remainder test per prime index.
Sei \(p_n\) die \(n\)-te Primzahl, und sei \(r_n\) der kleinste nichtnegative Rest von
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$$
Gesucht ist das kleinste \(n\), für das \(r_n\gt 10^{10}\) gilt. Auf den ersten Blick sieht das nach großen modularen Potenzen aus, aber modulo \(p_n^2\) verschwinden fast alle Terme der Binomialentwicklung. Genau diese Vereinfachung macht das Problem handhabbar.
Der Rest wird vollständig von den ersten beiden Binomialtermen bestimmt. Sobald diese Beobachtung sauber formuliert ist, wird aus einem Potenzproblem eine Suche über Primzahlindizes.
Wir entwickeln beide Potenzen um \(p_n\):
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
Addiert man beide Entwicklungen, erhält man
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
Jeder Term mit \(k\ge 2\) ist bereits durch \(p_n^2\) teilbar. Modulo \(p_n^2\) können also nur die Fälle \(k=0\) und \(k=1\) übrig bleiben. Welche davon tatsächlich überleben, hängt nur von der Parität von \(n\) ab.
Ist \(n\) gerade, dann addieren sich die konstanten Terme und die linearen Terme heben sich weg. Deshalb gilt
$$ r_n\equiv 2 \pmod{p_n^2}. $$
Da \(0\le 2\lt p_n^2\), ist der tatsächliche Rest also einfach \(r_n=2\). Gerade Indizes kommen daher niemals als Lösung in Frage.
Ist \(n\) ungerade, dann verschwinden die konstanten Terme und die linearen Terme addieren sich. Man erhält
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
Für ungerade Indizes wird der Rest also von der einen Größe \(2np_n\) kontrolliert; zunächst ist das aber noch eine Kongruenz und keine exakte Gleichheit.
Die Implementierungen vergleichen \(2np_n\) direkt mit der Schranke. Deshalb muss klar sein, ab wann \(2np_n\) bereits kleiner als \(p_n^2\) ist. Dafür reicht ein elementares Zählargument. Für \(n\ge 5\) bilden die ungeraden Zahlen
$$ 1,3,5,\dots,2n-1 $$
eine Liste aus genau \(n\) Zahlen. Darin sind sowohl \(1\) als auch \(9\) nicht prim, also gibt es unter diesen Zahlen höchstens \(n-2\) ungerade Primzahlen. Zusammen mit der Primzahl \(2\) existieren damit höchstens \(n-1\) Primzahlen, die \(\le 2n\) sind. Folglich muss die \(n\)-te Primzahl die Ungleichung
$$ p_n\gt 2n \qquad (n\ge 5) $$
erfüllen. Für ungerade \(n\ge 5\) folgt daraus
$$ 0\lt 2np_n\lt p_n^2, $$
also ist der kleinste nichtnegative Rest von \(2np_n \pmod{p_n^2}\) tatsächlich genau \(2np_n\). Damit gilt
$$ r_n=2np_n. $$
Die gesuchte Lösung liegt weit oberhalb von \(n=5\), daher ist genau dies die Formel, mit der der Code arbeitet.
Der Unterschied zwischen Kongruenz und exaktem Rest ist für kleine ungerade Indizes sichtbar. Für \(n=3\) gilt \(p_3=5\), also
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
Modulo \(25\) ergibt das \(280\bmod 25=5\). Die lineare Formel liefert \(2np_n=2\cdot 3\cdot 5=30\), und tatsächlich ist \(30\equiv 5\pmod{25}\); der exakte Rest ist aber \(5\), nicht \(30\).
Für \(n=5\) ist dagegen \(p_5=11\), und
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
Nun ist \(348832\bmod 121=110\), und genau das ist
$$ 2\cdot 5\cdot 11=110. $$
Hier tritt also kein Zurückfalten modulo \(p_n^2\) mehr auf, weil \(2n\lt p_n\). Die eigentliche Lösung liegt so weit draußen, dass nur noch dieser stabile Fall relevant ist.
Nach dem Primzahlsatz gilt grob \(p_n\sim n\log n\). Setzt man das in die Formel für ungerade Indizes ein, erhält man die Schätzung
$$ 2n^2\log n \gtrsim 10^{10}. $$
Damit liegt die gesuchte Stelle etwas oberhalb von \(2\times 10^4\). Das bedeutet, dass nur Primzahlen bis ungefähr zum zugehörigen \(p_n\) erzeugt werden müssen, also in einer Größenordnung von wenigen Hunderttausend. Eine einfache sequentielle Suche genügt daher völlig.
Die C++-, Python- und Java-Implementierungen durchlaufen die Primzahlen in aufsteigender Reihenfolge, sodass die aktuelle Primzahl und ihr Index immer gemeinsam bekannt sind. Die C++- und Java-Versionen speichern die bereits gefundenen Primzahlen und testen jede neue ganze Zahl nur durch diese früheren Primzahlen bis zur Quadratwurzel des Kandidaten. Die Python-Version springt mit einer Primzahlroutine direkt zur nächsten Primzahl; konzeptionell ist es dieselbe geordnete Durchmusterung.
Sobald eine neue Primzahl \(p_n\) erreicht ist, prüft die Implementierung zuerst die Parität von \(n\). Gerade Indizes werden sofort übersprungen, denn ihr Rest ist immer \(2\). Für ungerade Indizes wird lediglich \(2np_n\) berechnet und mit der Schranke verglichen. Es wird beim ersten \(n\) angehalten, für das dieser Wert die Grenze überschreitet. Keine der Implementierungen berechnet die riesigen Potenzen \((p_n-1)^n\) oder \((p_n+1)^n\) direkt. Eine Implementierung prüft die Logik zusätzlich noch an der kleineren Schranke \(10^9\), bevor der volle Lauf gestartet wird.
Sei \(P\) die Primzahl, bei der die Suche endet. Sobald eine Primzahl bekannt ist, kostet der mathematische Test nur konstante Zeit: Paritätsprüfung, Multiplikation und Vergleich.
In den C++- und Java-Implementierungen liegt die eigentliche Arbeit in der Primzahlerzeugung durch inkrementelle Probedivision. Ein Kandidat \(c\) wird nur durch bereits bekannte Primzahlen bis \(\sqrt c\) geprüft. Eine übliche Worst-Case-Abschätzung lautet daher
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
wobei der Speicherbedarf \(O(\pi(P))\) für die gespeicherten Primzahlen beträgt. In diesem Problem ist \(P\) nur von der Größenordnung einiger \(10^5\), also bleibt die Laufzeit praktisch klein. Die Python-Implementierung delegiert den Primzahlsprung an eine Bibliotheksroutine, führt aber aus Problemsicht ebenfalls nur einen konstanten Resttest pro Primzahlindex aus.
\(p_n\), \(n\)'inci asal sayı olsun ve
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2$$
ifadesinin en küçük negatif olmayan kalanı \(r_n\) ile gösterilsin. Amaç, \(r_n\gt 10^{10}\) olacak en küçük \(n\) değerini bulmaktır. İlk bakışta bu, çok büyük üslerle modüler üs alma problemi gibi görünür; fakat mod \(p_n^2\) altında binom açılımındaki terimlerin neredeyse tamamı yok olur. Problemi kolaylaştıran nokta tam olarak budur.
Kalan aslında yalnızca binom açılımının ilk iki teriminden etkilenir. Bu gözlem düzgün biçimde yazıldığında, devasa üslerden oluşan problem asal indisleri üzerinde yapılan basit bir aramaya dönüşür.
İki kuvveti de \(p_n\) etrafında açalım:
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
Bu iki açılım toplanınca
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right) $$
elde edilir. \(k\ge 2\) olan her terim zaten \(p_n^2\) çarpanı taşır. Bu yüzden mod \(p_n^2\) altında yalnızca \(k=0\) ve \(k=1\) terimleri kalabilir. Hangi terimin kaldığını belirleyen şey sadece \(n\)'in tek mi çift mi olduğudur.
\(n\) çiftse sabit terimler toplanır, lineer terimler birbirini götürür. Dolayısıyla
$$ r_n\equiv 2 \pmod{p_n^2}. $$
\(0\le 2\lt p_n^2\) olduğu için gerçek kalan doğrudan \(r_n=2\) olur. Bu nedenle çift indisler hiçbir zaman \(10^{10}\) eşiğini aşamaz.
\(n\) tekse bu kez sabit terimler yok olur, lineer terimler toplanır ve
$$ r_n\equiv 2np_n \pmod{p_n^2} $$
elde edilir. Yani tek indislerde kalan tek bir ifade tarafından kontrol edilir; ancak bu aşamada elimizde hâlâ tam eşitlik değil, sadece bir kongruans vardır.
Uygulamalar \(2np_n\) ifadesini doğrudan sınırla karşılaştırdığı için, bunun ne zaman zaten \(p_n^2\)'den küçük olduğunu bilmek gerekir. Bunun için basit bir sayma argümanı yeterlidir. \(n\ge 5\) için
$$ 1,3,5,\dots,2n-1 $$
listesinde tam \(n\) tane tek sayı vardır. Bu listede hem \(1\) hem de \(9\) asal değildir; dolayısıyla burada en fazla \(n-2\) tane tek asal bulunabilir. Buna asal sayı \(2\) de eklenince, \(2n\)'yi aşmayan asal sayılarının toplamı en fazla \(n-1\) olur. O halde \(n\)'inci asal için
$$ p_n\gt 2n \qquad (n\ge 5) $$
sonucu çıkar. Tek \(n\ge 5\) için bu eşitsizlik
$$ 0\lt 2np_n\lt p_n^2 $$
anlamına gelir; dolayısıyla \(2np_n \pmod{p_n^2}\) ifadesinin en küçük negatif olmayan kalanı doğrudan \(2np_n\)'dir. Yani
$$ r_n=2np_n $$
olur. Aranan çözüm \(n=5\)'ten çok daha büyük olduğu için kod güvenle bu formülü kullanır.
Kongruans ile gerçek kalan arasındaki fark küçük tek indislerde görülebilir. \(n=3\) için \(p_3=5\) olduğundan
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
Mod \(25\) altında bu değer \(280\bmod 25=5\) verir. Lineer formül ise \(2np_n=2\cdot 3\cdot 5=30\) üretir; gerçekten de \(30\equiv 5\pmod{25}\), fakat gerçek kalan \(30\) değil \(5\)'tir.
\(n=5\) için ise \(p_5=11\) ve
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
Bu kez \(348832\bmod 121=110\) olur ve bu değer tam olarak
$$ 2\cdot 5\cdot 11=110 $$
ile aynıdır. Çünkü artık \(2n\lt p_n\) olduğu için modüler sarma yoktur. Aranan eşik çok büyük olduğundan gerçek çözüm de bu kararlı bölgede ortaya çıkar.
Asal sayı teoremi kabaca \(p_n\sim n\log n\) der. Bunu tek indis formülüne koyarsak
$$ 2n^2\log n \gtrsim 10^{10} $$
tahmini elde edilir. Bu, geçiş noktasını \(2\times 10^4\)'ün biraz üstüne yerleştirir. Dolayısıyla programın üretmesi gereken asal sayılar, karşılık gelen \(p_n\) civarında yani birkaç yüz bin mertebesindedir. Bu nedenle basit bir sıralı arama fazlasıyla yeterlidir.
C++, Python ve Java uygulamaları asal sayı dizisini artan sırada dolaşır; böylece o anda hem asal sayı \(p_n\) hem de onun indisi \(n\) bilinir. C++ ve Java sürümleri daha önce bulunan asalları saklar ve her yeni adayı yalnızca kareköküne kadar olan eski asallarla test eder. Python sürümü ise bir asal üretim yordamıyla bir asal sayıdan sonrakine geçer; fakat kavramsal olarak aynı sıralı taramayı yapar.
Yeni bir \(p_n\) elde edildiğinde uygulama önce \(n\)'in tek mi çift mi olduğuna bakar. Çift indisler hemen geçilir; çünkü bunlarda kalan her zaman \(2\)'dir. Tek indislerde ise yalnızca \(2np_n\) hesaplanır ve bu değer sınırı aşar aşmaz arama durur. Hiçbir uygulama \((p_n-1)^n\) ya da \((p_n+1)^n\) gibi devasa kuvvetleri doğrudan hesaplamaz. Sürümlerden biri, tam probleme geçmeden önce aynı mantığı \(10^9\) sınırı üzerinde de doğrular.
Aramanın durduğu asal sayıya \(P\) diyelim. Bir asal sayı elde edildikten sonra yapılan matematiksel kontrol sabit zamandır: parite testi, bir çarpma ve bir karşılaştırma.
C++ ve Java uygulamalarında asıl maliyet, artımlı deneme bölmesiyle asal üretmektir. Bir aday \(c\), yalnızca \(\sqrt c\)'ye kadar olan daha önce bulunmuş asallarla sınanır. Bu nedenle standart kötü durum tahmini
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right) $$
şeklindedir. Bellek kullanımı da saklanan asallar için \(O(\pi(P))\)'dir. Bu problemde \(P\) yalnızca birkaç \(10^5\) büyüklüğünde olduğundan pratikte çalışma süresi küçüktür. Python sürümü asal ilerlemesini bir kütüphane yordamına bırakır; fakat problem açısından bakıldığında o da her asal indis için sadece sabit zamanlı bir eşik testi yapar.
Sea \(p_n\) el \(n\)-ésimo primo, y sea \(r_n\) el menor residuo no negativo de
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$$
Hay que encontrar el menor índice \(n\) para el cual \(r_n\gt 10^{10}\). A primera vista parece un problema de potenciación modular enorme, pero módulo \(p_n^2\) casi todos los términos de la expansión binomial desaparecen. Esa reducción es precisamente la clave del problema.
El residuo queda determinado por los dos primeros términos de la expansión binomial. Una vez que eso se escribe con cuidado, el problema deja de tratar de potencias gigantes y pasa a ser una búsqueda sobre índices primos.
Expandimos ambas potencias alrededor de \(p_n\):
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
Al sumar las dos expansiones se obtiene
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
Cualquier término con \(k\ge 2\) ya es múltiplo de \(p_n^2\), así que módulo \(p_n^2\) solo pueden sobrevivir los casos \(k=0\) y \(k=1\). Cuál de ellos aparece depende únicamente de la paridad de \(n\).
Si \(n\) es par, los términos constantes se suman y los términos lineales se cancelan, de modo que
$$ r_n\equiv 2 \pmod{p_n^2}. $$
Como \(0\le 2\lt p_n^2\), el residuo real es simplemente \(r_n=2\). Por eso ningún índice par puede superar el umbral \(10^{10}\).
Si \(n\) es impar, los términos constantes se cancelan y los términos lineales se suman, dando
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
Así, para índices impares el residuo queda gobernado por la cantidad \(2np_n\), aunque por ahora todavía se trata de una congruencia y no de una igualdad exacta.
Las implementaciones comparan \(2np_n\) directamente con el límite, así que hace falta saber cuándo ese valor ya es menor que \(p_n^2\). Un argumento elemental de conteo basta. Para \(n\ge 5\), los impares
$$ 1,3,5,\dots,2n-1 $$
forman una lista de exactamente \(n\) números. Dentro de ella, tanto \(1\) como \(9\) son compuestos o no primos, así que entre esos impares hay como máximo \(n-2\) primos impares. Si además contamos al primo \(2\), obtenemos como máximo \(n-1\) primos menores o iguales que \(2n\). Por lo tanto, el \(n\)-ésimo primo satisface
$$ p_n\gt 2n \qquad (n\ge 5). $$
Para \(n\) impar y \(n\ge 5\), esto implica
$$ 0\lt 2np_n\lt p_n^2, $$
y entonces el menor residuo no negativo de \(2np_n \pmod{p_n^2}\) es exactamente \(2np_n\). En consecuencia,
$$ r_n=2np_n. $$
La primera solución aparece muchísimo después de \(n=5\), de modo que esta es la fórmula que el código puede usar con total seguridad.
La diferencia entre una congruencia y el residuo exacto se ve en índices impares pequeños. Para \(n=3\), se tiene \(p_3=5\), así que
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
Módulo \(25\), esto da \(280\bmod 25=5\). La fórmula lineal produce \(2np_n=2\cdot 3\cdot 5=30\), y en efecto \(30\equiv 5\pmod{25}\); sin embargo, el residuo exacto es \(5\), no \(30\).
Para \(n=5\), en cambio, \(p_5=11\) y
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
Ahora \(348832\bmod 121=110\), y ese valor coincide con
$$ 2\cdot 5\cdot 11=110. $$
Aquí ya no hay reducción adicional porque \(2n\lt p_n\). Como el umbral buscado es enorme, el primer índice válido cae dentro de este régimen estable.
El teorema de los números primos da la aproximación \(p_n\sim n\log n\). Si se sustituye en la fórmula de los índices impares, aparece la condición aproximada
$$ 2n^2\log n \gtrsim 10^{10}. $$
Eso sitúa el cruce un poco por encima de \(2\times 10^4\). En consecuencia, el programa solo necesita generar primos hasta el \(p_n\) correspondiente, que está en el orden de unos pocos cientos de miles. Una búsqueda secuencial sencilla es más que suficiente.
Las implementaciones en C++, Python y Java recorren la sucesión de primos en orden creciente, de modo que el primo actual \(p_n\) y su índice \(n\) se conocen al mismo tiempo. Las versiones en C++ y Java guardan los primos ya encontrados y prueban cada nuevo entero candidato solo con esos primos previos hasta su raíz cuadrada. La versión en Python avanza al siguiente primo mediante una rutina de generación de primos, pero conceptualmente sigue el mismo recorrido ordenado.
Cada vez que aparece un nuevo \(p_n\), la implementación mira primero si \(n\) es impar. Los índices pares se descartan al instante porque su residuo siempre es \(2\). Para los índices impares, basta calcular \(2np_n\) y detenerse en el primer caso en que ese valor supera el límite. Ninguna de las implementaciones evalúa directamente las potencias gigantes \((p_n-1)^n\) o \((p_n+1)^n\). Una de ellas, además, verifica la misma lógica con el umbral más pequeño \(10^9\) antes de resolver el caso completo.
Sea \(P\) el primo en el que termina la búsqueda. Una vez conocido un primo, la comprobación matemática cuesta tiempo constante: una prueba de paridad, una multiplicación y una comparación.
En las implementaciones de C++ y Java, el coste principal es la generación de primos por división de prueba incremental. Un candidato \(c\) solo se divide por primos ya conocidos hasta \(\sqrt c\), de modo que una estimación estándar en el peor caso es
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
con memoria \(O(\pi(P))\) para almacenar la lista de primos. En este problema, \(P\) solo está en el orden de unos pocos \(10^5\), así que el tiempo real es pequeño. La implementación en Python delega el avance entre primos a una rutina de biblioteca, pero desde el punto de vista del problema sigue haciendo una sola prueba de umbral en tiempo constante por índice primo.
设 \(p_n\) 是第 \(n\) 个素数，\(r_n\) 表示
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2$$
的最小非负余数。题目要求找出满足 \(r_n\gt 10^{10}\) 的最小 \(n\)。表面上看，这像是一个需要处理巨大幂次的模运算问题；但在模 \(p_n^2\) 的意义下，二项式展开中几乎所有高次项都会消失。真正决定答案的，只是最前面的少数几项。
这一题的关键，不是去直接计算 \((p_n-1)^n\) 与 \((p_n+1)^n\)，而是先把它们按二项式定理展开，再观察模 \(p_n^2\) 之后还剩下什么。这样一来，问题就从“大数幂的余数”变成了“按顺序扫描素数并检查一个简单不等式”。
先把两项都围绕 \(p_n\) 展开：
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
把两式相加，得到
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
只要 \(k\ge 2\)，该项就至少含有一个 \(p_n^2\) 因子，因此在模 \(p_n^2\) 下直接消失。于是真正可能留下来的只有 \(k=0\) 和 \(k=1\) 两项。接下来要看的是：这两项在奇偶不同的 \(n\) 下分别会不会相互抵消。
如果 \(n\) 是偶数，那么常数项会相加，而一次项会互相抵消，所以有
$$ r_n\equiv 2 \pmod{p_n^2}. $$
由于 \(0\le 2\lt p_n^2\)，这里的同余实际上就是精确余数，因此
$$ r_n=2. $$
这立刻说明偶数下标永远不可能让余数超过 \(10^{10}\)。
如果 \(n\) 是奇数，那么常数项相消，一次项相加，于是得到
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
所以真正需要研究的，只剩下奇数下标时 \(2np_n\) 与 \(p_n^2\) 的关系。此时还不能马上把余数写成 \(2np_n\)，因为它目前只是模 \(p_n^2\) 的同余类。
实现代码直接把 \(2np_n\) 与阈值比较，因此必须先证明：在真正会出现答案的范围里，\(2np_n\) 已经小于 \(p_n^2\)，不会再发生“绕回去”的模约化。这个结论可以用一个很初等的计数论证得到。
对 \(n\ge 5\)，考虑所有不超过 \(2n\) 的奇数：
$$ 1,3,5,\dots,2n-1. $$
这个序列一共有恰好 \(n\) 个数。其中 \(1\) 不是素数，\(9\) 也不是素数，所以在这些奇数里，至多只有 \(n-2\) 个奇素数。再把唯一的偶素数 \(2\) 算进去，不超过 \(2n\) 的素数总数至多为 \(n-1\)。因此第 \(n\) 个素数一定满足
$$ p_n\gt 2n \qquad (n\ge 5). $$
一旦 \(n\) 为奇数且 \(n\ge 5\)，上式就推出
$$ 0\lt 2np_n\lt p_n^2. $$
这意味着 \(2np_n \pmod{p_n^2}\) 的最小非负代表元就是它本身，所以
$$ r_n=2np_n. $$
题目的答案远远大于 \(5\)，因此实现里直接检查 \(2np_n\) 是完全合理的。
小的奇数下标可以清楚地展示“同余”和“精确余数”之间的差别。先看 \(n=3\)。这时 \(p_3=5\)，于是
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
模 \(25\) 的余数是 \(280\bmod 25=5\)。而线性表达式给出
$$ 2np_n=2\cdot 3\cdot 5=30. $$
两者并不相等，但它们满足 \(30\equiv 5\pmod{25}\)。也就是说，奇数情形下的公式先给出的是同余类，而不是始终等于最终余数。
再看 \(n=5\)。这时 \(p_5=11\)，并且
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
模 \(121\) 之后得到 \(348832\bmod 121=110\)，而
$$ 2\cdot 5\cdot 11=110. $$
这一次它们完全相等，因为已经满足 \(2n\lt p_n\)，不再发生模意义下的回卷。题目所要求的阈值很大，因此第一次超过阈值时，正处在这种稳定区间内。
素数定理给出粗略近似 \(p_n\sim n\log n\)。把它代入奇数情形的公式，就得到近似条件
$$ 2n^2\log n \gtrsim 10^{10}. $$
这个估计把答案的位置放在略高于 \(2\times 10^4\) 的地方。也就是说，程序只需要把素数顺序生成到对应的 \(p_n\) 附近，而那个素数只在几十万数量级。对这种规模，顺序扫描完全足够。
C++、Python 和 Java 实现都按照从小到大的顺序走过素数序列，因此当前素数 \(p_n\) 和当前下标 \(n\) 会同时出现。C++ 与 Java 版本维护一个已经找到的素数表，并把每个新的整数候选只除以前面那些不超过其平方根的素数。Python 版本则通过素数生成例程从一个素数跳到下一个素数，但本质上做的仍然是同样的顺序枚举。
每得到一个新的 \(p_n\)，实现首先判断 \(n\) 的奇偶性。若 \(n\) 为偶数，就立刻跳过，因为它对应的余数恒为 \(2\)。若 \(n\) 为奇数，就计算 \(2np_n\)，并在它第一次超过目标阈值时停止。整个过程中，没有任何一个实现会直接去算 \((p_n-1)^n\) 或 \((p_n+1)^n\) 这样的巨大幂。还有一个实现会先用较小的阈值 \(10^9\) 做一次校验，再执行完整搜索。
设搜索终止时对应的素数为 \(P\)。一旦某个素数已经得到，后续的数学检查就是常数时间：判断奇偶、做一次乘法、做一次比较。
在 C++ 与 Java 实现中，主要成本来自用增量试除法生成素数。候选整数 \(c\) 只需要用已经找到的、且不超过 \(\sqrt c\) 的素数去测试，因此一个标准的最坏情形估计是
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
空间复杂度则是存储这些素数所需的 \(O(\pi(P))\)。在本题中，\(P\) 只有若干个 \(10^5\) 量级，所以运行非常轻松。Python 版本把素数推进交给库函数处理，但从题目逻辑上看，它同样只是对每个素数下标做一次常数时间的阈值检查。
Пусть \(p_n\) обозначает \(n\)-е простое число, а \(r_n\) — наименьший неотрицательный остаток выражения
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$$
Нужно найти наименьшее \(n\), для которого \(r_n\gt 10^{10}\). На первый взгляд задача выглядит как вычисление огромных степеней по модулю, но по модулю \(p_n^2\) почти все члены биномиального разложения исчезают. Именно это и превращает задачу в очень короткий поиск.
Весь остаток определяется первыми двумя членами бинома. Как только это выписано явно, задача перестаёт быть задачей о больших степенях и становится задачей о последовательном переборе индексов простых чисел.
Разложим обе степени около \(p_n\):
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
После сложения получаем
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
Если \(k\ge 2\), то член уже делится на \(p_n^2\), поэтому по модулю \(p_n^2\) могут остаться только случаи \(k=0\) и \(k=1\). Какой из них выживает, определяется только чётностью \(n\).
Если \(n\) чётно, постоянные члены складываются, а линейные взаимно уничтожаются. Поэтому
$$ r_n\equiv 2 \pmod{p_n^2}. $$
Так как \(0\le 2\lt p_n^2\), отсюда сразу следует точное равенство \(r_n=2\). Значит, чётные индексы никогда не дадут остаток больше \(10^{10}\).
Если \(n\) нечётно, постоянные члены сокращаются, а линейные складываются, и получается
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
Следовательно, в нечётном случае всё сводится к величине \(2np_n\), но пока это ещё только сравнение по модулю, а не точное значение остатка.
Реализации сравнивают с порогом непосредственно число \(2np_n\), поэтому нужно понять, когда оно уже строго меньше \(p_n^2\). Здесь достаточно элементарного подсчёта. Для \(n\ge 5\) числа
$$ 1,3,5,\dots,2n-1 $$
образуют список ровно из \(n\) нечётных чисел. Среди них и \(1\), и \(9\) не являются простыми, значит, нечётных простых среди них не больше \(n-2\). Если добавить простое число \(2\), то простых чисел, не превосходящих \(2n\), не больше \(n-1\). Следовательно, \(n\)-е простое обязано удовлетворять неравенству
$$ p_n\gt 2n \qquad (n\ge 5). $$
Для нечётного \(n\ge 5\) это даёт
$$ 0\lt 2np_n\lt p_n^2, $$
а значит, наименьший неотрицательный представитель класса \(2np_n \pmod{p_n^2}\) равен самому \(2np_n\). Поэтому
$$ r_n=2np_n. $$
Искомый индекс находится намного правее \(5\), так что именно эту формулу код и использует.
Разница между сравнением и точным остатком видна на маленьких нечётных индексах. При \(n=3\) имеем \(p_3=5\), поэтому
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
По модулю \(25\) это даёт \(280\bmod 25=5\). Линейная формула даёт \(2np_n=2\cdot 3\cdot 5=30\), и действительно \(30\equiv 5\pmod{25}\), но точный остаток равен \(5\), а не \(30\).
При \(n=5\) уже \(p_5=11\), и
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
Теперь \(348832\bmod 121=110\), а это в точности
$$ 2\cdot 5\cdot 11=110. $$
Здесь дополнительного сокращения по модулю уже нет, потому что выполнено \(2n\lt p_n\). А искомый порог настолько велик, что первое подходящее \(n\) попадает именно в этот устойчивый режим.
Теорема о распределении простых чисел даёт приближение \(p_n\sim n\log n\). Подставляя его в формулу для нечётных индексов, получаем приблизительное условие
$$ 2n^2\log n \gtrsim 10^{10}. $$
Оно помещает искомую точку немного выше \(2\times 10^4\). Значит, программе нужно дойти лишь до соответствующего простого \(p_n\), а это всего лишь несколько сотен тысяч. Для такого масштаба простого последовательного перебора более чем достаточно.
Реализации на C++, Python и Java идут по последовательности простых чисел в возрастающем порядке, так что текущие \(p_n\) и \(n\) известны одновременно. В версиях на C++ и Java хранится список уже найденных простых, и каждый новый кандидат проверяется только делением на эти ранние простые до квадратного корня из кандидата. Версия на Python переходит от одного простого к следующему с помощью библиотечной процедуры, но по сути выполняет тот же упорядоченный проход.
Как только найдено новое \(p_n\), реализация сначала смотрит на чётность индекса \(n\). Чётные индексы сразу пропускаются, потому что их остаток всегда равен \(2\). Для нечётных индексов вычисляется только \(2np_n\), и поиск останавливается при первом превышении порога. Ни одна из реализаций не вычисляет огромные степени \((p_n-1)^n\) или \((p_n+1)^n\) напрямую. Одна из реализаций дополнительно проверяет ту же идею на меньшем пороге \(10^9\), а уже затем решает полную задачу.
Пусть \(P\) — простое число, на котором поиск завершается. После того как очередное простое уже найдено, сама математическая проверка занимает константное время: проверка чётности, одно умножение и одно сравнение.
В реализациях на C++ и Java основная стоимость связана с порождением простых чисел методом накапливаемого пробного деления. Кандидат \(c\) проверяется только на делимость на ранее найденные простые, не превосходящие \(\sqrt c\), поэтому стандартная оценка сверху имеет вид
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
а память равна \(O(\pi(P))\), поскольку хранится список найденных простых. В этой задаче \(P\) имеет порядок всего нескольких \(10^5\), так что на практике программа работает быстро. В Python переход к следующему простому делегирован библиотеке, но с точки зрения самой задачи там тоже выполняется только одна проверка порога за константное время на каждый индекс простого.
ليكن \(p_n\) هو العدد الأولي رقم \(n\)، ولتكن \(r_n\) هي أصغر قيمة غير سالبة للباقي الناتج من
$$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$$
المطلوب هو إيجاد أصغر \(n\) يحقق \(r_n\gt 10^{10}\). من النظرة الأولى قد يبدو السؤال وكأنه يتطلب حساب قوى هائلة بترديد كبير، لكن عند العمل بترديد \(p_n^2\) تختفي تقريبًا كل حدود التوسع ذي الحدين. هذا الانهيار الجبري هو الذي يجعل المسألة قصيرة في النهاية.
الباقي يتحدد بالكامل من الحدين الأولين فقط في التوسع. وبمجرد كتابة ذلك بدقة، تتحول المسألة من حساب قوى ضخمة إلى مسح متسلسل لفهارس الأعداد الأولية مع اختبار متباينة بسيطة.
نوسع القوتين حول \(p_n\):
$$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $$
وبجمع التوسعين نحصل على
$$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $$
كل حد فيه \(k\ge 2\) يحتوي أصلًا على عامل \(p_n^2\)، ولذلك يختفي مباشرة عند الأخذ بترديد \(p_n^2\). إذن الحدّان الوحيدان اللذان قد يبقيان هما \(k=0\) و\(k=1\)، وما إذا كان أحدهما ينجو أو يختفي يعتمد فقط على زوجية \(n\) أو فرديته.
إذا كان \(n\) زوجيًا فإن الحدود الثابتة تتجمع، بينما تلغي الحدود الخطية بعضها بعضًا، ومن ثم
$$ r_n\equiv 2 \pmod{p_n^2}. $$
وبما أن \(0\le 2\lt p_n^2\)، فإن هذا يعني مباشرة أن الباقي الفعلي هو \(r_n=2\). لذلك لا يمكن لأي فهرس زوجي أن يتجاوز العتبة \(10^{10}\).
أما إذا كان \(n\) فرديًا فإن الحدود الثابتة تختفي، والحدود الخطية تتجمع، فنحصل على
$$ r_n\equiv 2np_n \pmod{p_n^2}. $$
إذن في الحالة الفردية يصبح كل شيء محكومًا بالكمية \(2np_n\)، لكن هذه ما تزال موافقة بترديد \(p_n^2\) وليست بعد قيمة الباقي نفسها.
بما أن التطبيقات تقارن \(2np_n\) مباشرة مع الحد المطلوب، فلا بد من معرفة متى تكون هذه القيمة أصغر أصلًا من \(p_n^2\). يمكن إثبات ذلك بحجة عد بسيطة. عندما يكون \(n\ge 5\)، فإن الأعداد الفردية
$$ 1,3,5,\dots,2n-1 $$
تشكل قائمة فيها بالضبط \(n\) عددًا. داخل هذه القائمة، كل من \(1\) و\(9\) ليس أوليًا، ولذلك لا يمكن أن يوجد أكثر من \(n-2\) عدد أولي فردي فيها. وإذا أضفنا العدد الأولي \(2\)، صار مجموع الأعداد الأولية التي لا تتجاوز \(2n\) في حده الأقصى \(n-1\). ومن ثم يجب أن يحقق العدد الأولي رقم \(n\) المتباينة
$$ p_n\gt 2n \qquad (n\ge 5). $$
وعندما يكون \(n\) فرديًا مع \(n\ge 5\)، ينتج من ذلك
$$ 0\lt 2np_n\lt p_n^2. $$
وعليه فإن أصغر ممثل غير سالب للصنف \(2np_n \pmod{p_n^2}\) هو \(2np_n\) نفسه، أي أن
$$ r_n=2np_n. $$
والحل الأول للمسألة يقع بعيدًا جدًا بعد \(n=5\)، ولذلك تستطيع الشيفرة أن تعتمد هذا التعبير مباشرة بأمان.
الفرق بين الموافقة والقيمة الدقيقة للباقي يظهر بوضوح عند الفهارس الفردية الصغيرة. عندما \(n=3\) يكون \(p_3=5\)، وبالتالي
$$ (5-1)^3+(5+1)^3=4^3+6^3=280. $$
وبترديد \(25\) نحصل على \(280\bmod 25=5\). أما الصيغة الخطية فتعطي
$$ 2np_n=2\cdot 3\cdot 5=30. $$
وهذا صحيح فقط من حيث الموافقة، لأن \(30\equiv 5\pmod{25}\)، لكن الباقي الحقيقي هو \(5\) وليس \(30\).
أما عند \(n=5\) فإن \(p_5=11\)، ولدينا
$$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $$
والباقي بترديد \(121\) هو \(348832\bmod 121=110\)، وهذه القيمة تساوي تمامًا
$$ 2\cdot 5\cdot 11=110. $$
هنا لا يحدث التفاف إضافي لأن \(2n\lt p_n\). وبما أن العتبة المستهدفة كبيرة جدًا، فإن أول فهرس يحقق الشرط يقع داخل هذا النطاق المستقر.
تعطي نظرية الأعداد الأولية التقريب \(p_n\sim n\log n\). وبالتعويض في صيغة الحالة الفردية نحصل على الشرط التقريبي
$$ 2n^2\log n \gtrsim 10^{10}. $$
وهذا يضع نقطة التجاوز قليلًا فوق \(2\times 10^4\). لذلك لا تحتاج الشيفرة إلا إلى توليد الأعداد الأولية حتى العدد الموافق لهذا الفهرس تقريبًا، وهو في حدود بضع مئات من الآلاف فقط. ولهذا فالمسح التتابعي البسيط كافٍ تمامًا.
تنطلق تطبيقات C++ وPython وJava في تسلسل الأعداد الأولية تصاعديًا، بحيث يكون العدد الأولي الحالي \(p_n\) وفهرسه \(n\) معروفين في اللحظة نفسها. في نسختي C++ وJava تُحفَظ الأعداد الأولية المكتشفة سابقًا، ويُختبر كل مرشح جديد بالقسمة فقط على تلك الأعداد الأولية التي لا تتجاوز جذره التربيعي. أما نسخة Python فتنتقل من عدد أولي إلى الذي يليه باستخدام أداة لتوليد الأعداد الأولية، لكنها من الناحية المفهومية تقوم بالمسح المرتب نفسه.
كلما ظهر عدد أولي جديد \(p_n\)، تفحص الشيفرة أولًا هل \(n\) فردي أم زوجي. الفهارس الزوجية تُتخطى فورًا لأن باقيها دائمًا \(2\). أما في الفهارس الفردية فيُحسب التعبير \(2np_n\) فقط، ويتوقف التنفيذ عند أول فهرس تتجاوز فيه هذه القيمة الحد المطلوب. ولا تقوم أي من النسخ بحساب القوتين الضخمتين \((p_n-1)^n\) أو \((p_n+1)^n\) مباشرة. كما أن إحدى النسخ تتحقق أولًا من المنطق نفسه على العتبة الأصغر \(10^9\) قبل حل الحالة الكاملة.
لنرمز بـ \(P\) إلى العدد الأولي الذي تتوقف عنده عملية البحث. بعد معرفة كل عدد أولي، يصبح الاختبار الرياضي نفسه ذا كلفة ثابتة: فحص زوجية، ثم ضرب، ثم مقارنة.
في نسختي C++ وJava، الكلفة الحقيقية تأتي من توليد الأعداد الأولية بالقسمة التجريبية التزايدية. فالمرشح \(c\) لا يُفحَص إلا على الأعداد الأولية المكتشفة سابقًا حتى \(\sqrt c\)، ولذلك فإن تقديرًا قياسيًا في أسوأ الأحوال هو
$$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $$
أما الذاكرة فهي \(O(\pi(P))\) من أجل قائمة الأعداد الأولية المحفوظة. في هذه المسألة يكون \(P\) في حدود بضعة \(10^5\) فقط، ولذلك يكون الأداء العملي مريحًا جدًا. وتفوّض نسخة Python خطوة الانتقال بين الأعداد الأولية إلى أداة مكتبية، لكن من زاوية المسألة نفسها فهي أيضًا تنفذ اختبار عتبة بزمن ثابت لكل فهرس أولي.