We study the quadratic family \(q_{a,b}(n)=n^2+an+b\) under the bounds \(|a| \lt 1000\) and \(|b| \le 1000\). For each choice of coefficients, we start at \(n=0\) and ask how long the values stay prime without interruption. The task is to find the pair \((a,b)\) with the longest initial prime streak and return the product \(ab\).
Inside these bounds, the best pair is \(a=-61\) and \(b=971\). It produces 71 consecutive primes for \(n=0,1,\dots,70\), so the required product is \(-59231\).
Let \(\mathbb{P}\) denote the set of positive primes, and let \(L(a,b)\) be the length of the initial prime run generated by \(q_{a,b}(n)\):
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
If the values at \(n=0,1,\dots,k-1\) are all prime, then \(L(a,b)=k\). The problem is therefore a finite maximization problem over all allowed coefficient pairs.
At \(n=0\), the polynomial is simply
$$q_{a,b}(0)=b.$$
So \(b\) itself must be prime. Because the primality test used by the implementations rejects every integer below 2, this means \(b\) must in fact be a positive prime. Mathematically, that already removes the overwhelming majority of the nominal \(|b|\le 1000\) search interval.
The next term is
$$q_{a,b}(1)=1+a+b.$$
If \(b\) is an odd prime, then \(1+b\) is even, so \(q_{a,b}(1)\) has the same parity as \(a\). To remain prime and exceed 2, this value should usually be odd, which strongly suggests that successful choices of \(a\) are odd once \(b>2\). The implementations do not exploit this observation, but it explains part of the structure of the winning search region.
Substituting \(n=b\) reveals a useful factorization:
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
Since \(b\) is prime, this term is automatically divisible by \(b\). Therefore a prime run will normally break no later than \(n=b\), because \(q_{a,b}(b)\) is then forced to be composite. The only way around that divisibility trap is the exceptional case
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
which makes \(q_{a,b}(b)=b\) prime again. This identity is not used as a pruning rule in the code, but it is a genuine problem-specific invariant and shows why long runs are rare.
The coefficient box is small, and most pairs fail quickly. For each admissible pair, one evaluates
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
until the first non-prime value appears. All three implementations use the same simple primality test: reject \(n<2\), handle the even case separately, then try odd divisors up to \(\sqrt{n}\). No sieve, recurrence, or deeper number theory is required for this problem size.
The maximizing polynomial is
$$q(n)=n^2-61n+971.$$
Its first values are
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
and the prime streak continues all the way to \(n=70\). The last prime in that initial block is
$$q(70)=70^2-61\cdot 70+971=1601,$$
while the next value is
$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$
So this pair produces exactly 71 consecutive primes, and no admissible pair produces more.
The C++, Python, and Java implementations scan every integer \(a\) from \(-999\) to \(999\) and every integer \(b\) from \(-999\) to \(999\). This is effectively the Project Euler search box, because the only omitted endpoints are \(\pm 1000\), and neither is prime. Before any streak is counted, the implementation checks whether \(b\) itself is prime and skips the pair immediately if it is not.
For each surviving pair, the implementation starts with \(n=0\), computes \(n^2+an+b\), and stops as soon as the result fails the prime test. Negative values, 0, and 1 therefore end the loop at once. The number of successful iterations is exactly the mathematical quantity \(L(a,b)\).
Whenever a newly tested pair yields a longer streak than the current record, the stored best coefficients are updated. Before the full search, the implementations also support self-checks using the classical examples \(n^2+n+41\) and \(n^2-79n+1601\), verifying streak lengths 40 and 80. The second example lies outside the final coefficient bounds, but it is still a useful correctness test for the counting routine.
Let \(A=999\) and \(B=999\). The raw scan touches \((2A+1)(2B+1)=1999^2\) coefficient pairs, but only those with prime \(b\) require a full streak count. Since there are 168 positive primes at most 999, the more expensive part is closer to
$$1999\times 168 \approx 3.36\times 10^5$$
candidate quadratics.
If a given pair survives for \(K\) terms and the largest tested value has size about \(M\), then trial division costs \(O(K\sqrt{M})\) for that pair. In this problem \(K\) never exceeds 71 inside the search box, so the runtime is easily manageable. Memory usage is \(O(1)\): the implementations keep only loop counters, the current polynomial value, and the best pair found so far.
Wir betrachten die quadratische Familie \(q_{a,b}(n)=n^2+an+b\) unter den Schranken \(|a| \lt 1000\) und \(|b| \le 1000\). Für jedes Koeffizientenpaar beginnt man bei \(n=0\) und fragt, wie lange die entstehenden Werte ohne Unterbrechung prim bleiben. Gesucht ist das Paar \((a,b)\) mit der längsten Anfangsserie von Primzahlen; ausgegeben wird das Produkt \(ab\).
Innerhalb dieser Grenzen ist das beste Paar \(a=-61\) und \(b=971\). Es liefert 71 aufeinanderfolgende Primzahlen für \(n=0,1,\dots,70\), also lautet das gesuchte Produkt \(-59231\).
Sei \(\mathbb{P}\) die Menge der positiven Primzahlen, und sei \(L(a,b)\) die Länge der anfänglichen Primzahlserie von \(q_{a,b}(n)\):
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
Wenn also die Werte für \(n=0,1,\dots,k-1\) alle prim sind, dann gilt \(L(a,b)=k\). Das Problem ist damit eine endliche Maximierungsaufgabe über alle zulässigen Koeffizientenpaare.
Für \(n=0\) erhält man unmittelbar
$$q_{a,b}(0)=b.$$
Daher muss \(b\) selbst prim sein. Da die in den Implementierungen verwendete Primzahlprüfung alle Zahlen kleiner als 2 verwirft, folgt sogar: \(b\) muss eine positive Primzahl sein. Rein mathematisch schrumpft damit der nominelle Bereich \(|b|\le 1000\) sofort auf sehr wenige Kandidaten.
Der nächste Term lautet
$$q_{a,b}(1)=1+a+b.$$
Ist \(b\) eine ungerade Primzahl, dann ist \(1+b\) gerade, also hat \(q_{a,b}(1)\) dieselbe Parität wie \(a\). Damit dieser Wert prim und größer als 2 sein kann, sollte er in der Regel ungerade sein; erfolgreiche Werte von \(a\) sind deshalb meist ungerade, sobald \(b>2\) gilt. Der Code nutzt dieses Argument nicht als Filter, aber es erklärt die Form des Suchraums.
Setzt man \(n=b\), so entsteht die Faktorisierung
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
Da \(b\) prim ist, ist dieser Ausdruck automatisch durch \(b\) teilbar. Deshalb bricht eine Primzahlserie normalerweise spätestens bei \(n=b\) ab, denn dann ist \(q_{a,b}(b)\) zusammengesetzt. Die einzige Ausnahme ist
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
wodurch wieder \(q_{a,b}(b)=b\) entsteht. Diese Beziehung wird in den Implementierungen nicht zur Beschleunigung verwendet, ist aber eine echte problemspezifische Invariante und zeigt, warum lange Serien selten sind.
Das Koeffizientenrechteck ist klein, und die meisten Paare scheitern sehr früh. Für jedes zulässige Paar berechnet man
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
bis der erste nicht-prime Wert auftritt. Alle drei Implementierungen verwenden dafür dieselbe einfache Primzahlprüfung: Zahlen kleiner als 2 verwerfen, den geraden Fall separat behandeln und danach nur ungerade Teiler bis \(\sqrt{n}\) testen. Für diese Problemgröße ist keine aufwendigere Zahlentheorie nötig.
Das maximierende Polynom ist
$$q(n)=n^2-61n+971.$$
Die ersten Werte sind
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
und die Primzahlserie reicht bis \(n=70\). Der letzte Primwert dieser Anfangsserie ist
$$q(70)=70^2-61\cdot 70+971=1601,$$
während der nächste Wert
$$q(71)=71^2-61\cdot 71+971=1681=41^2$$
bereits zusammengesetzt ist. Also liefert dieses Paar genau 71 aufeinanderfolgende Primzahlen, und kein anderes zulässiges Paar ist besser.
Die C++-, Python- und Java-Implementierungen durchlaufen alle ganzen Zahlen \(a\) von \(-999\) bis \(999\) und alle ganzen Zahlen \(b\) von \(-999\) bis \(999\). Das entspricht dem Problem effektiv vollständig, denn die einzigen ausgelassenen Randwerte sind \(\pm 1000\), und keiner davon ist prim. Bevor eine Serie gezählt wird, prüft die Implementierung sofort, ob \(b\) prim ist; andernfalls wird das Paar verworfen.
Für jedes verbleibende Paar startet die Implementierung mit \(n=0\), berechnet \(n^2+an+b\) und stoppt, sobald der Wert die Primzahlprüfung nicht besteht. Negative Zahlen, 0 und 1 beenden die Schleife daher unmittelbar. Die gezählte Anzahl erfolgreicher Schritte ist exakt die mathematische Größe \(L(a,b)\).
Ergibt ein neu getestetes Paar eine längere Serie als alle bisherigen, werden die gespeicherten besten Koeffizienten ersetzt. Zusätzlich unterstützen die Implementierungen optionale Selbsttests mit den klassischen Beispielen \(n^2+n+41\) und \(n^2-79n+1601\), um die Serienlängen 40 bzw. 80 zu bestätigen. Das zweite Beispiel liegt außerhalb des endgültigen Suchbereichs, ist aber trotzdem ein wertvoller Korrektheitstest.
Setze \(A=999\) und \(B=999\). Der rohe Suchlauf besucht \((2A+1)(2B+1)=1999^2\) Koeffizientenpaare, aber nur Paare mit primem \(b\) benötigen überhaupt eine vollständige Serienzählung. Da es höchstens 999 nur 168 positive Primzahlen gibt, liegt der teurere Teil näher bei
$$1999\times 168 \approx 3.36\times 10^5$$
Kandidatenquadriken.
Überlebt ein Paar \(K\) Glieder und hat der größte getestete Wert Größenordnung \(M\), dann kostet die Probedivision für dieses Paar \(O(K\sqrt{M})\). In diesem Problem überschreitet \(K\) innerhalb des Suchbereichs nie 71, daher ist die Laufzeit problemlos klein. Der Speicherbedarf ist \(O(1)\), weil nur Zähler, der aktuelle Funktionswert und das bisher beste Paar gehalten werden.
\(q_{a,b}(n)=n^2+an+b\) biçimindeki ikinci dereceden aileyi, \(|a| \lt 1000\) ve \(|b| \le 1000\) sınırları altında inceliyoruz. Her katsayı çifti için \(n=0\) noktasından başlanır ve üretilen değerlerin asal olarak ne kadar süre kesintisiz devam ettiği sorulur. Amaç, en uzun başlangıç asal zincirini veren \((a,b)\) çiftini bulup \(ab\) çarpımını döndürmektir.
Bu sınırlar içinde en iyi çift \(a=-61\) ve \(b=971\) olur. Bu seçim \(n=0,1,\dots,70\) için 71 ardışık asal üretir; dolayısıyla istenen çarpım \(-59231\) değeridir.
Pozitif asallar kümesini \(\mathbb{P}\) ile gösterelim; \(q_{a,b}(n)\) tarafından üretilen başlangıç asal zincirinin uzunluğu da \(L(a,b)\) olsun:
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
Yani \(n=0,1,\dots,k-1\) için tüm değerler asal ise \(L(a,b)=k\) olur. Böylece problem, izin verilen katsayı çiftleri üzerinde sonlu bir maksimum arama problemine dönüşür.
\(n=0\) için
$$q_{a,b}(0)=b$$
elde edilir. Bu yüzden \(b\) doğrudan asal olmak zorundadır. Uygulamaların kullandığı asallık testi 2'den küçük tüm sayıları reddettiği için, \(b\)'nin yalnızca asal değil aynı zamanda pozitif asal olması gerekir. Matematiksel olarak bu gözlem, \(|b|\le 1000\) aralığının büyük kısmını tek hamlede eler.
Bir sonraki terim
$$q_{a,b}(1)=1+a+b$$
olur. Eğer \(b\) tek bir asal ise, \(1+b\) çift olduğundan \(q_{a,b}(1)\) ile \(a\) aynı pariteye sahiptir. Bu değerin asal ve 2'den büyük kalabilmesi için genellikle tek olması gerekir; dolayısıyla \(b>2\) olduğunda başarılı \(a\) değerleri çoğunlukla tektir. Kod bu bilgiyi filtre olarak kullanmaz, ancak kazanan bölgenin neden belirli bir yapıya sahip olduğunu açıklar.
\(n=b\) yazınca şu çarpanlara ayırma ortaya çıkar:
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
\(b\) zaten asal olduğu için bu terim otomatik olarak \(b\)'ye bölünür. Bu nedenle asal zinciri normalde \(n=b\) adımına gelmeden ya da en geç orada kırılır; çünkü \(q_{a,b}(b)\) bileşik olmaya zorlanır. Bu tuzaktan çıkmanın tek yolu
$$b+a+1=1 \quad\Longrightarrow\quad a=-b$$
olup bu durumda \(q_{a,b}(b)=b\) tekrar asal olur. Uygulamalar bu özdeşliği aramayı budamak için kullanmaz, fakat bu yine de probleme özgü gerçek bir değişmezdir ve uzun zincirlerin neden nadir olduğunu gösterir.
Katsayı kutusu küçüktür ve çiftlerin çoğu çok erken başarısız olur. Her uygun çift için
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
değerleri ilk asal olmayan sonuç görülene kadar hesaplanır. Üç uygulamanın da kullandığı asallık testi aynıdır: \(n<2\) ise reddet, çift sayıları ayrı ele al, sonra yalnızca \(\sqrt{n}\)'e kadar tek bölenleri dene. Bu problem boyutunda elek ya da daha derin bir sayı teorisi gerekmez.
Maksimum veren polinom
$$q(n)=n^2-61n+971$$
olur. İlk değerler
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853$$
şeklindedir ve asal zinciri \(n=70\) değerine kadar sürer. Bu bloktaki son asal değer
$$q(70)=70^2-61\cdot 70+971=1601,$$
bir sonraki değer ise
$$q(71)=71^2-61\cdot 71+971=1681=41^2$$
olur. Böylece bu çift tam 71 ardışık asal üretir ve izin verilen hiçbir çift bundan daha iyi değildir.
C++, Python ve Java uygulamaları \(a\) için \(-999\) ile \(999\) arasındaki tüm tam sayıları, \(b\) için de yine \(-999\) ile \(999\) arasındaki tüm tam sayıları dener. Bu, problemi fiilen tam kapsar; çünkü dışarıda bırakılan tek uç değerler \(\pm 1000\)'dir ve bunların hiçbiri asal değildir. Herhangi bir zincir sayılmadan önce uygulama \(b\)'nin asal olup olmadığını kontrol eder; değilse çift anında atlanır.
Geriye kalan her çift için uygulama \(n=0\) ile başlar, \(n^2+an+b\) değerini hesaplar ve sonuç asallık testini geçmediği anda durur. Negatif değerler, 0 ve 1 bu yüzden döngüyü hemen sonlandırır. Başarılı yineleme sayısı tam olarak \(L(a,b)\) niceliğidir.
Yeni denenmiş bir çift mevcut rekoru aşarsa saklanan en iyi katsayılar güncellenir. Ayrıca uygulamalar, tam aramadan önce \(n^2+n+41\) ve \(n^2-79n+1601\) örnekleriyle isteğe bağlı doğrulamalar yaparak zincir uzunluklarının sırasıyla 40 ve 80 olduğunu kontrol eder. İkinci örnek nihai katsayı sınırlarının dışındadır, ancak sayma mantığını sınamak için yine de değerlidir.
\(A=999\) ve \(B=999\) olsun. Ham tarama \((2A+1)(2B+1)=1999^2\) adet katsayı çiftine bakar, ancak yalnızca \(b\) asal olan çiftler gerçek zincir sayımına girer. 999'a kadar yalnızca 168 pozitif asal bulunduğundan, pahalı kısım yaklaşık olarak
$$1999\times 168 \approx 3.36\times 10^5$$
aday ikinci dereceye iner.
Bir çift \(K\) terim boyunca yaşarsa ve test edilen en büyük değer yaklaşık \(M\) büyüklüğündeyse, deneme bölmesi maliyeti o çift için \(O(K\sqrt{M})\) olur. Bu problemde arama kutusu içinde \(K\) hiçbir zaman 71'i geçmez; dolayısıyla çalışma süresi rahatlıkla küçüktür. Bellek kullanımı \(O(1)\)'dir; yalnızca sayaçlar, güncel değer ve bulunan en iyi çift tutulur.
Estudiamos la familia cuadrática \(q_{a,b}(n)=n^2+an+b\) bajo las cotas \(|a| \lt 1000\) y \(|b| \le 1000\). Para cada elección de coeficientes se empieza en \(n=0\) y se pregunta cuánto tiempo los valores permanecen primos sin interrupción. La tarea consiste en encontrar el par \((a,b)\) con la racha inicial de primos más larga y devolver el producto \(ab\).
Dentro de esos límites, el mejor par es \(a=-61\) y \(b=971\). Genera 71 primos consecutivos para \(n=0,1,\dots,70\), de modo que el producto pedido es \(-59231\).
Sea \(\mathbb{P}\) el conjunto de los primos positivos, y sea \(L(a,b)\) la longitud de la racha inicial de primos producida por \(q_{a,b}(n)\):
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
Si los valores correspondientes a \(n=0,1,\dots,k-1\) son todos primos, entonces \(L(a,b)=k\). Por tanto, el problema es una maximización finita sobre todos los pares de coeficientes permitidos.
En \(n=0\) se obtiene
$$q_{a,b}(0)=b.$$
Así que \(b\) debe ser primo por sí mismo. Como la prueba de primalidad usada por las implementaciones rechaza todos los enteros menores que 2, en realidad \(b\) tiene que ser un primo positivo. Matemáticamente, esta simple observación reduce de inmediato casi todo el intervalo nominal \(|b|\le 1000\).
El siguiente término es
$$q_{a,b}(1)=1+a+b.$$
Si \(b\) es un primo impar, entonces \(1+b\) es par y \(q_{a,b}(1)\) tiene la misma paridad que \(a\). Para que este valor siga siendo primo y sea mayor que 2, normalmente conviene que sea impar, lo que empuja a \(a\) hacia valores impares cuando \(b>2\). Las implementaciones no usan este hecho como filtro, pero sí ayuda a entender la estructura aritmética del problema.
Al sustituir \(n=b\) aparece la factorización
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
Como \(b\) ya es primo, este término es automáticamente divisible por \(b\). Por eso una racha prima normalmente no puede sobrevivir hasta \(n=b\): el valor en ese punto queda forzado a ser compuesto. La única escapatoria es el caso excepcional
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
que vuelve a dar \(q_{a,b}(b)=b\), un primo. El código no usa esta identidad para podar la búsqueda, pero sí es un invariante real del problema y explica por qué las rachas largas son poco frecuentes.
La caja de coeficientes es pequeña y la mayoría de los pares fracasa muy pronto. Para cada par admisible se evalúan
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
hasta encontrar el primer valor no primo. Las tres implementaciones usan la misma prueba elemental de primalidad: rechazar \(n<2\), tratar aparte el caso par y luego probar divisores impares hasta \(\sqrt{n}\). Para este tamaño de entrada no hace falta ni cribado previo ni teoría más sofisticada.
El polinomio que maximiza la racha es
$$q(n)=n^2-61n+971.$$
Sus primeros valores son
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
y la racha de primos continúa hasta \(n=70\). El último primo de ese bloque inicial es
$$q(70)=70^2-61\cdot 70+971=1601,$$
mientras que el siguiente valor es
$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$
Así se obtienen exactamente 71 primos consecutivos, y ningún otro par admisible supera ese resultado.
Las implementaciones en C++, Python y Java recorren todos los enteros \(a\) entre \(-999\) y \(999\) y todos los enteros \(b\) entre \(-999\) y \(999\). Esto cubre de hecho el cuadro del problema, porque los únicos extremos omitidos son \(\pm 1000\) y ninguno de ellos es primo. Antes de contar una racha, la implementación comprueba si \(b\) es primo; si no lo es, descarta el par de inmediato.
Para cada par que sobrevive, la implementación empieza con \(n=0\), calcula \(n^2+an+b\) y se detiene en cuanto el valor deja de ser primo. Los valores negativos, 0 y 1 terminan el bucle inmediatamente. El número de iteraciones exitosas coincide exactamente con la cantidad matemática \(L(a,b)\).
Si un par nuevo produce una racha más larga que la mejor observada hasta ese momento, se actualizan los coeficientes almacenados. Además, las implementaciones incluyen comprobaciones opcionales con las cuadráticas clásicas \(n^2+n+41\) y \(n^2-79n+1601\), verificando longitudes 40 y 80 antes de ejecutar la búsqueda completa. El segundo ejemplo queda fuera del cuadro final de coeficientes, pero sigue siendo una excelente prueba de corrección.
Sea \(A=999\) y \(B=999\). El barrido bruto visita \((2A+1)(2B+1)=1999^2\) pares de coeficientes, pero solo los pares con \(b\) primo necesitan un conteo completo de racha. Como hay 168 primos positivos hasta 999, la parte más costosa se acerca más a
$$1999\times 168 \approx 3.36\times 10^5$$
cuadráticas candidatas.
Si un par sobrevive \(K\) términos y el mayor valor probado tiene tamaño aproximado \(M\), la división por prueba cuesta \(O(K\sqrt{M})\) para ese par. En este problema, dentro del cuadro de búsqueda, \(K\) nunca supera 71, así que el tiempo total es muy pequeño. El uso de memoria es \(O(1)\): solo se mantienen contadores, el valor actual del polinomio y el mejor par encontrado.
我们研究二次多项式族 \(q_{a,b}(n)=n^2+an+b\)，其中 \(|a| \lt 1000\)，\(|b| \le 1000\)。对每一组系数，都从 \(n=0\) 开始，考察它产生的数值能够连续保持为素数多久。目标是找出初始连续素数段最长的系数组 \((a,b)\)，并返回乘积 \(ab\)。
在这些范围内，最优系数是 \(a=-61\)、\(b=971\)。它对 \(n=0,1,\dots,70\) 一共给出 71 个连续素数，因此答案的乘积是 \(-59231\)。
记 \(\mathbb{P}\) 为正素数集合，\(L(a,b)\) 为 \(q_{a,b}(n)\) 生成的初始连续素数长度：
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
也就是说，如果 \(n=0,1,\dots,k-1\) 时对应的值全部是素数，那么 \(L(a,b)=k\)。因此，这道题本质上是在一个有限的系数矩形内寻找使 \(L(a,b)\) 最大的那一组参数。
当 \(n=0\) 时，多项式变成
$$q_{a,b}(0)=b.$$
所以 \(b\) 本身必须是素数。又因为实现中的素性判断会把所有小于 2 的整数直接判为非素数，所以 \(b\) 不仅要是素数，还必须是正素数。这个结论一下子就把名义上的 \(|b|\le 1000\) 搜索区间缩小到了很少的一批候选值。
下一项是
$$q_{a,b}(1)=1+a+b.$$
如果 \(b\) 是奇素数，那么 \(1+b\) 是偶数，于是 \(q_{a,b}(1)\) 与 \(a\) 具有相同的奇偶性。为了让这一项继续保持为大于 2 的素数，它通常应该是奇数，所以当 \(b>2\) 时，表现好的 \(a\) 往往是奇数。三个实现都没有把这个性质当成剪枝条件，但它确实解释了优胜系数为什么呈现出明显的奇偶结构。
把 \(n=b\) 代入，会得到一个非常关键的因式分解：
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
由于 \(b\) 已经是素数，这一项自动带有因子 \(b\)。因此，一条连续素数链通常不可能撑到 \(n=b\) 这一步，因为此时的值会被强制变成合数。唯一的例外是
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
在这种特殊情况下，\(q_{a,b}(b)=b\) 又重新回到素数。代码并没有利用这个关系做额外剪枝，但它是这道题真正的结构性质之一，也说明了为什么很长的素数链十分少见。
这道题的系数范围并不大，而且绝大多数候选对会很快失败。对每个可行的系数组合，只需顺次计算
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
直到第一次遇到非素数为止。三种语言的实现都采用同样的基础素性测试：先排除 \(n<2\)，再单独处理偶数，只对奇数试除到 \(\sqrt{n}\)。在这样的数据规模下，并不需要筛法、递推或更深的数论工具。
达到最大值的多项式是
$$q(n)=n^2-61n+971.$$
它的前几项为
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
而且这条素数链一直延续到 \(n=70\)。这一段中的最后一个素数是
$$q(70)=70^2-61\cdot 70+971=1601,$$
再往下一项则变成
$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$
因此这组系数恰好给出 71 个连续素数，而在允许的搜索范围内，没有任何别的系数对能超过它。
C++、Python 和 Java 实现都会遍历 \(-999\) 到 \(999\) 之间的所有整数 \(a\)，以及同一区间内的所有整数 \(b\)。这在效果上等同于完整覆盖题目的系数盒子，因为唯一没有显式包含的边界值是 \(\pm 1000\)，而它们都不是素数。在开始统计连续素数长度之前，程序会先检查 \(b\) 是否为素数；如果不是，就立刻跳过这一对系数。
对每一个保留下来的系数对，程序从 \(n=0\) 开始，计算 \(n^2+an+b\)，一旦结果未通过素性测试就停止。负数、0 和 1 都会立刻终止循环。因此，成功通过测试的迭代次数正好就是数学定义中的 \(L(a,b)\)。
如果某一组新系数产生的连续素数段长于当前记录，程序就更新保存的最优系数。除此之外，这些实现还支持在正式搜索前做两组自检：\(n^2+n+41\) 应该产生 40 项连续素数，\(n^2-79n+1601\) 应该产生 80 项连续素数。第二个例子虽然不在最终的系数范围内，但它仍然非常适合验证计数逻辑是否正确。
设 \(A=999\)、\(B=999\)。原始双重循环会访问 \((2A+1)(2B+1)=1999^2\) 个系数对，但只有 \(b\) 为素数的情形才会进入真正的连续素数计数。由于不超过 999 的正素数只有 168 个，更昂贵的部分实际上更接近
$$1999\times 168 \approx 3.36\times 10^5$$
个候选二次式。
如果某组系数能够维持 \(K\) 项，而被测试到的最大多项式值大约为 \(M\)，那么试除法对这一组的代价是 \(O(K\sqrt{M})\)。在本题的搜索范围内，\(K\) 的最大值就是 71，所以总运行时间非常轻松。额外空间复杂度是 \(O(1)\)，因为实现只保留若干计数器、当前值以及目前最优的系数对，并没有建立大型筛表或缓存结构。
Рассматривается семейство квадратных трёхчленов \(q_{a,b}(n)=n^2+an+b\) при ограничениях \(|a| \lt 1000\) и \(|b| \le 1000\). Для каждой пары коэффициентов нужно начать с \(n=0\) и посмотреть, как долго значения остаются простыми без разрыва. Требуется найти такую пару \((a,b)\), для которой начальная серия простых максимальна, и вернуть произведение \(ab\).
В этих пределах лучшая пара равна \(a=-61\) и \(b=971\). Она даёт 71 подряд идущий простой результат при \(n=0,1,\dots,70\), поэтому искомое произведение равно \(-59231\).
Обозначим через \(\mathbb{P}\) множество положительных простых чисел, а через \(L(a,b)\) длину начальной серии простых, которую порождает \(q_{a,b}(n)\):
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
Иначе говоря, если значения при \(n=0,1,\dots,k-1\) все простые, то \(L(a,b)=k\). Значит, задача сводится к конечной максимизации по всем допустимым коэффициентам.
При \(n=0\) имеем
$$q_{a,b}(0)=b.$$
Следовательно, само число \(b\) обязано быть простым. Поскольку используемая в реализациях проверка на простоту отвергает все целые числа меньше 2, отсюда сразу следует, что \(b\) должно быть положительным простым. С математической точки зрения это резко сокращает формальный диапазон \(|b|\le 1000\).
Следующий член равен
$$q_{a,b}(1)=1+a+b.$$
Если \(b\) является нечётным простым, то \(1+b\) чётно, а значит \(q_{a,b}(1)\) имеет ту же чётность, что и \(a\). Чтобы это значение оставалось простым и было больше 2, оно обычно должно быть нечётным, поэтому при \(b>2\) успешные коэффициенты \(a\), как правило, тоже нечётны. Код это наблюдение не использует, но оно хорошо описывает арифметическую структуру задачи.
Подстановка \(n=b\) даёт важное разложение
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
Так как \(b\) уже является простым, это значение автоматически делится на \(b\). Поэтому серия простых обычно не может дойти до шага \(n=b\): в этой точке значение почти неизбежно составное. Единственное исключение возникает в случае
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
когда снова получается \(q_{a,b}(b)=b\), то есть простое число. Реализации не используют это тождество для ускорения, но оно является настоящим инвариантом именно этой задачи и объясняет редкость длинных серий.
Область коэффициентов невелика, а большинство пар ломается очень быстро. Для каждой допустимой пары последовательно вычисляются
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
до первого непростого значения. Во всех трёх реализациях используется одна и та же элементарная проверка на простоту: отвергнуть \(n<2\), отдельно обработать чётные числа и затем проверять только нечётные делители до \(\sqrt{n}\). Для данного размера входа этого более чем достаточно.
Максимум достигается для полинома
$$q(n)=n^2-61n+971.$$
Первые значения равны
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
и серия простых продолжается до \(n=70\). Последний простой член начального блока равен
$$q(70)=70^2-61\cdot 70+971=1601,$$
а следующее значение уже составное:
$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$
Тем самым получаем ровно 71 подряд идущий простой результат, и никакая другая допустимая пара коэффициентов этого не превосходит.
Реализации на C++, Python и Java перебирают все целые \(a\) от \(-999\) до \(999\) и все целые \(b\) от \(-999\) до \(999\). Это фактически совпадает с областью Project Euler, потому что единственные неохваченные граничные значения равны \(\pm 1000\), а ни одно из них не является простым. Перед подсчётом серии программа сразу проверяет, простое ли \(b\); если нет, пара отбрасывается мгновенно.
Для каждой оставшейся пары программа стартует с \(n=0\), вычисляет \(n^2+an+b\) и останавливается, как только результат перестаёт быть простым. Отрицательные числа, 0 и 1 немедленно завершают цикл. Число успешных шагов в точности равно математической величине \(L(a,b)\).
Если новая пара даёт более длинную серию, чем текущий рекорд, сохранённые лучшие коэффициенты заменяются. Кроме того, реализации поддерживают необязательные контрольные проверки на двух классических примерах \(n^2+n+41\) и \(n^2-79n+1601\), подтверждая длины 40 и 80 до запуска полного поиска. Второй пример находится вне окончательных границ коэффициентов, но всё равно полезен как тест корректности логики подсчёта.
Пусть \(A=999\) и \(B=999\). Грубый перебор просматривает \((2A+1)(2B+1)=1999^2\) пар коэффициентов, но полный подсчёт серии нужен только для тех пар, где \(b\) простое. Так как среди положительных чисел не больше 999 имеется всего 168 простых, дорогая часть вычислений ближе к
$$1999\times 168 \approx 3.36\times 10^5$$
кандидатным квадратным трёхчленам.
Если некоторая пара живёт \(K\) шагов, а наибольшее проверенное значение имеет размер порядка \(M\), то пробное деление стоит \(O(K\sqrt{M})\) для этой пары. В пределах данной задачи \(K\) никогда не превышает 71, поэтому время работы очень мало. Память имеет порядок \(O(1)\): хранятся только счётчики, текущее значение и лучшая найденная пара.
ندرس عائلة الدوال التربيعية \(q_{a,b}(n)=n^2+an+b\) تحت الشرطين \(|a| \lt 1000\) و\(|b| \le 1000\). لكل اختيار للمعاملين نبدأ من \(n=0\) ونسأل: كم عدد القيم الأولى التي تبقى أولية من دون انقطاع؟ المطلوب هو إيجاد الزوج \((a,b)\) الذي يعطي أطول سلسلة أولية ابتدائية ثم إرجاع حاصل الضرب \(ab\).
داخل هذه الحدود، أفضل زوج هو \(a=-61\) و\(b=971\). هذا الزوج يولد 71 عددًا أوليًا متتاليًا عند \(n=0,1,\dots,70\)، ولذلك يكون الناتج المطلوب هو \(-59231\).
لنرمز إلى مجموعة الأعداد الأولية الموجبة بالرمز \(\mathbb{P}\)، وإلى طول السلسلة الأولية الابتدائية التي تنتجها \(q_{a,b}(n)\) بالرمز \(L(a,b)\):
$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$
أي إذا كانت القيم عند \(n=0,1,\dots,k-1\) كلها أولية، فإن \(L(a,b)=k\). وهكذا تتحول المسألة إلى تعظيم محدود على جميع أزواج المعاملات المسموح بها.
عند \(n=0\) نحصل على
$$q_{a,b}(0)=b.$$
إذًا لا بد أن يكون \(b\) نفسه عددًا أوليًا. وبما أن اختبار الأولية في التنفيذات يرفض كل عدد أصغر من 2، فهذا يعني أن \(b\) يجب أن يكون عددًا أوليًا موجبًا. هذه الملاحظة وحدها تقلص معظم المجال الاسمي \(|b|\le 1000\).
الحد التالي هو
$$q_{a,b}(1)=1+a+b.$$
إذا كان \(b\) عددًا أوليًا فرديًا، فإن \(1+b\) يكون زوجيًا، وبالتالي تكون \(q_{a,b}(1)\) لها نفس فردية \(a\). ولكي تبقى هذه القيمة أولية وأكبر من 2، فمن الأفضل عادة أن تكون فردية، وهذا يدفع \(a\) نحو القيم الفردية عندما يكون \(b>2\). التنفيذات لا تستخدم هذه الفكرة كمرشح صريح، لكنها تشرح لماذا تظهر البنية الفردية بوضوح في الأزواج الناجحة.
إذا عوضنا \(n=b\) نحصل على التحليل التالي:
$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$
بما أن \(b\) أولي أصلًا، فهذه القيمة تقبل القسمة على \(b\) تلقائيًا. لذلك فإن سلسلة الأعداد الأولية تنكسر عادة قبل الوصول إلى \(n=b\) أو عنده على الأكثر، لأن \(q_{a,b}(b)\) يصبح عددًا غير أولي في الوضع العادي. الاستثناء الوحيد هو الحالة
$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$
وفيها تصبح \(q_{a,b}(b)=b\) أولية من جديد. الشيفرة لا تستعمل هذه العلاقة لتقليص البحث، لكنها خاصية حقيقية مرتبطة بهذه المسألة بالذات وتوضح لماذا تكون السلاسل الطويلة نادرة.
مجال المعاملات صغير، ومعظم الأزواج يفشل بسرعة كبيرة. لكل زوج مقبول نحسب
$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$
حتى تظهر أول قيمة غير أولية. تستخدم التنفيذات الثلاثة الاختبار نفسه: رفض \(n<2\)، ومعالجة الأعداد الزوجية على نحو منفصل، ثم تجربة القواسم الفردية حتى \(\sqrt{n}\). لا نحتاج هنا إلى منخل أو إلى أدوات عددية أعمق، لأن حجم المسألة صغير بما يكفي.
الدالة التي تحقق القيمة العظمى هي
$$q(n)=n^2-61n+971.$$
وأولى قيمها هي
$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$
وتستمر السلسلة الأولية حتى \(n=70\). آخر قيمة أولية في هذا المقطع الابتدائي هي
$$q(70)=70^2-61\cdot 70+971=1601,$$
أما القيمة التالية فهي
$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$
إذن هذا الزوج يعطي بالضبط 71 عددًا أوليًا متتاليًا، ولا يوجد أي زوج مسموح به يتفوق عليه.
تقوم تنفيذات C++ وPython وJava بمسح جميع القيم الصحيحة لـ \(a\) من \(-999\) إلى \(999\)، وجميع القيم الصحيحة لـ \(b\) من \(-999\) إلى \(999\). وهذا يعادل عمليًا مجال المسألة بالكامل، لأن الطرفين الوحيدين غير المضمنين صراحة هما \(\pm 1000\)، وكلاهما غير أولي. قبل بدء أي عد للسلسلة، تتحقق الشيفرة من أولية \(b\) نفسها؛ فإذا لم تكن أولية يتم تجاهل الزوج فورًا.
لكل زوج ينجو من الفحص الأول، تبدأ الشيفرة من \(n=0\)، وتحسب \(n^2+an+b\)، ثم تتوقف بمجرد أن تفشل القيمة في اختبار الأولية. القيم السالبة و0 و1 تنهي الحلقة مباشرة. وعدد الخطوات الناجحة يساوي تمامًا الكمية الرياضية \(L(a,b)\).
إذا أعطى زوج جديد سلسلة أطول من أفضل سلسلة معروفة حتى تلك اللحظة، تُحدَّث المعاملات المخزنة. كما تتضمن التنفيذات اختبارات تحقق اختيارية باستخدام المثالين الكلاسيكيين \(n^2+n+41\) و\(n^2-79n+1601\)، للتأكد من طولين يساويان 40 و80 قبل تشغيل البحث الكامل. المثال الثاني يقع خارج حدود البحث النهائية، لكنه يظل فحصًا ممتازًا لصحة منطق العد.
لتكن \(A=999\) و\(B=999\). المسح الخام يزور \((2A+1)(2B+1)=1999^2\) زوجًا من المعاملات، لكن الأزواج التي تحتاج فعلًا إلى عد السلسلة هي فقط تلك التي يكون فيها \(b\) أوليًا. وبما أن عدد الأعداد الأولية الموجبة حتى 999 هو 168 فقط، فإن الجزء الأغلى من الحساب يقترب أكثر من
$$1999\times 168 \approx 3.36\times 10^5$$
دالة تربيعية مرشحة.
إذا استمر زوج معين لمدة \(K\) حدود، وكان أكبر مقدار تم اختباره بحجم يقارب \(M\)، فإن كلفة القسمة التجريبية لذلك الزوج هي \(O(K\sqrt{M})\). في هذه المسألة لا يتجاوز \(K\) داخل مجال البحث القيمة 71، لذلك يكون الزمن الكلي صغيرًا جدًا. أما الذاكرة فهي \(O(1)\)، لأن التنفيذات تحتفظ بعدادات قليلة وبالقيمة الحالية وبأفضل زوج تم العثور عليه فقط.