The code searches for special integers called engineers' paradises. A candidate \(n\) must satisfy two independent conditions:
1. four consecutive primes centered around \(n\) must form a prime chain with gap 6, and
2. the five numbers \(n-8, n-4, n, n+4, n+8\) must all be practical numbers.
The solver finds the first \(k\) such paradises and sums them.
The first filter is purely prime-based. The program keeps a sliding window of four consecutive primes \(p_0,p_1,p_2,p_3\) and checks
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
If this holds, then the four primes are exactly
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
so the candidate center is
$$n=p_0+9.$$
Equivalently, the prime pattern is centered at
$$n-9,\ n-3,\ n+3,\ n+9.$$
This is the expensive combinatorial pattern the code looks for first, because only such windows can possibly produce a paradise.
A concrete miniature example is the first prime window with this shape:
$$251,\ 257,\ 263,\ 269.$$
It yields the center
$$n=251+9=260.$$
The practical-number stage then checks
$$252,\ 256,\ 260,\ 264,\ 268.$$
The first four values are practical, but 268 is not, so 260 is rejected. This shows the full logic of the search: the prime window is only a necessary condition, and the five local practical tests decide whether the candidate is really a paradise.
A positive integer \(m\) is practical if every integer from \(1\) to \(m\) can be written as a sum of distinct divisors of \(m\).
The code only needs the practical-number test for five nearby values around a candidate \(n\):
$$n-8,\ n-4,\ n,\ n+4,\ n+8.$$
This is why the candidate must satisfy \(n\ge 9\): otherwise \(n-8\) would be non-positive.
Let a number have prime factorization
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
Define the prefix product
$$A_i=\prod_{j=1}^{i} q_j^{a_j},$$
and its divisor sum
$$S_i=\sigma(A_i).$$
The Stewart-Sierpiński theorem says that \(N\) is practical if and only if \(q_1=2\) and
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
In words: once the first prime factor is 2, every next prime factor must not jump too far beyond the divisor-sum coverage already built by the prefix.
The code does not recompute \(\sigma(A_i)\) from scratch at every step. It factors the number in increasing prime order and maintains a running prefix value.
For a prime power,
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
So after factoring \(N\), the solver only needs to multiply the current prefix by \(\sigma(q_i^{a_i})\) and compare the next prime with \(S_i+1\).
A simple worked example shows the idea:
$$12=2^2\cdot 3.$$
For the prefix \(2^2\),
$$S_1=\sigma(2^2)=1+2+4=7,$$
and the next prime factor is \(3\), which satisfies \(3\le 7+1\). So 12 is practical.
By contrast,
$$14=2\cdot 7$$
fails because the prefix after \(2\) is \(S_1=3\), but \(7>3+1\). So 14 is not practical.
The implementation also includes a reference test for practical numbers. It enumerates all divisors, runs a subset-sum style reachability DP, and verifies that every value from 1 to \(n\) is reachable as a sum of distinct divisors.
This slow method is used only for verification on small inputs. The program checks that the Stewart-Sierpiński criterion and the brute-force definition agree for every \(n\le 400\).
This checkpoint is stronger than a casual spot-check. It compares the exact implementation of is_practical against the definition itself for every integer in the whole range \(1\le n\le 400\), so mistakes in factor handling, divisor generation, or subset-sum reachability are caught before the large search starts.
Prime generation is split into two layers.
First, the code computes all base primes up to \(\sqrt{\text{limit}+9}\) with an ordinary sieve. Those primes are used both for segmented sieving and for factoring candidate numbers.
Then the search range \([3,\text{limit}+9]\) is processed in segments. Each segment stores only odd numbers, so the sieve memory stays small. Segment batches can be processed in parallel, but the primes inside each batch are still handled in increasing order so the sliding window stays correct.
The function find_paradises reads the prime stream and maintains a deque of the last four primes. Whenever the last four primes satisfy the gap-6 pattern, the code forms the candidate
$$n=p_0+9$$
and then tests the five practical-number conditions.
If they all pass, the candidate is recorded, added to the running sum, and printed as a found paradise.
The code stops once it has found the requested number of paradises. The first two known values are used as checkpoints:
$$219869980,\qquad 312501820.$$
Threading is used only for segmented sieve batches. Candidate validation itself is kept ordered and deterministic because the prime-window scan is sequential. The helper choose_thread_count caps the number of workers by the workload and the hardware.
This separation is important: the sieve can be parallelized safely, while the window scan must preserve prime order.
The solver parses options such as --limit, --target, --segment, --threads, --single-thread, and --skip-checkpoints. It builds the base-prime list once, runs the practical-number cross-check up to 400 unless disabled, and then calls find_paradises.
The practical test is implemented in is_practical. The brute-force reference is is_practical_bruteforce. The segmented sieve lives in sieve_segment. The final search loop is a four-prime sliding window in find_paradises.
One subtle detail is that segment batches may be sieved in parallel, but the lambda process_prime still consumes the resulting prime lists in increasing segment order. That preserves the meaning of “four consecutive primes”, which would be broken by an unordered merge.
At the end, the program prints the sum of the first requested paradises and also reports elapsed time.
The ordinary sieve up to \(\sqrt{\text{limit}+9}\) is tiny compared with the full search. The segmented sieve is close to
$$O(L\log\log L)$$
for limit \(L\), while using only segment-sized working memory. The practical-number test for a candidate factors five nearby numbers and applies the multiplicative criterion, so candidate checks are sparse and relatively cheap.
The brute-force practical-number check is much slower, but it runs only on the small checkpoint range \(1\le n\le 400\). That makes it a safe validator without affecting the main asymptotics.
Gesucht werden besondere Zahlen \(n\), die der Code als engineers' paradises bezeichnet. Ein Kandidat muss zwei Bedingungen erfüllen: vier aufeinanderfolgende Primzahlen um \(n\) herum müssen ein 6-6-6-Muster bilden, und die fünf Zahlen \(n-8, n-4, n, n+4, n+8\) müssen praktisch sein. Die ersten \(k\) solchen Zahlen werden summiert.
Der erste Filter arbeitet nur mit Primzahlen. Das Programm hält ein Fenster aus vier aufeinanderfolgenden Primzahlen \(p_0,p_1,p_2,p_3\) und prüft
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
Dann sind die vier Primzahlen genau
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
und der Kandidat ist
$$n=p_0+9.$$
Äquivalent liegt das Primmuster zentriert bei
$$n-9,\ n-3,\ n+3,\ n+9.$$
Ein konkretes Miniaturbeispiel ist das erste Primfenster dieser Form:
$$251,\ 257,\ 263,\ 269.$$
Daraus folgt der Mittelpunkt
$$n=251+9=260.$$
Danach prüft die Praktikalitätsstufe die fünf Zahlen
$$252,\ 256,\ 260,\ 264,\ 268.$$
Die ersten vier sind praktisch, 268 jedoch nicht. Also wird 260 verworfen. Genau daran sieht man die Gesamtlogik der Suche: Das Primfenster ist nur eine notwendige Bedingung; erst die fünf lokalen Praktikalitätstests entscheiden über ein echtes paradise.
Eine positive ganze Zahl \(m\) heißt praktisch, wenn sich jede Zahl von 1 bis \(m\) als Summe verschiedener Teiler von \(m\) darstellen lässt.
Für einen Kandidaten \(n\) müssen die fünf Zahlen
$$n-8,\ n-4,\ n,\ n+4,\ n+8$$
praktisch sein. Daher muss \(n\ge 9\) gelten.
Sei
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
Definiere den Prefix
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
und die zugehörige Teilersumme
$$S_i=\sigma(A_i).$$
Dann ist \(N\) genau dann praktisch, wenn \(q_1=2\) und
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
Die Idee ist, dass der Prefix bereits genug Teilersummen abdeckt, damit der nächste Primfaktor keine Lücke erzeugt.
Der Code berechnet \(\sigma(A_i)\) nicht von Grund auf neu. Er faktorisiert die Zahl in aufsteigender Primordnung und hält einen laufenden Prefixwert.
Für eine Primzahlpotenz gilt
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
Beispiel:
$$12=2^2\cdot 3.$$
Für den Prefix \(2^2\) ist
$$S_1=\sigma(2^2)=1+2+4=7,$$
und der nächste Primfaktor ist 3. Da \(3\le 7+1\), ist 12 praktisch.
Dagegen gilt für
$$14=2\cdot 7$$
mit \(S_1=3\) die Ungleichung \(7>3+1\), also ist 14 nicht praktisch.
Zusätzlich gibt es einen Referenztest. Dabei werden alle Teiler erzeugt, anschließend wird per Teilmengen-DP geprüft, ob sich jede Zahl von 1 bis \(n\) als Summe verschiedener Teiler darstellen lässt.
Diese langsame Methode dient nur der Validierung. Der Code vergleicht das Kriterium mit der Brute-Force-Definition für alle \(n\le 400\).
Dieser Checkpoint ist stärker als ein bloßer Stichprobentest. Er vergleicht die konkrete Implementierung von is_practical für jede ganze Zahl im Bereich \(1\le n\le 400\) mit der Definition selbst, sodass Fehler in der Faktorisierung, Divisorenerzeugung oder Teilmengen-DP vor der großen Suche auffallen.
Die Primzahlen werden in zwei Schichten erzeugt.
Zuerst berechnet der Code alle Basisprimzahlen bis \(\sqrt{\text{limit}+9}\) mit einem gewöhnlichen Sieb. Diese Liste wird sowohl zum segmentierten Sieben als auch zum Faktorisieren verwendet.
Danach wird der Bereich \([3,\text{limit}+9]\) in Segmente zerlegt. Jedes Segment enthält nur ungerade Zahlen, damit der Speicher klein bleibt. Die Segmente können parallel verarbeitet werden, aber innerhalb eines Segments werden die Primzahlen geordnet ausgegeben.
find_paradises liest den Primzahlstrom und hält ein Fenster der letzten vier Primzahlen. Sobald dieses Fenster das 6-6-6-Muster erfüllt, wird der Kandidat
$$n=p_0+9$$
gebildet und auf die fünf Praktikalitätsbedingungen geprüft.
Besteht der Kandidat, wird er gespeichert, zur laufenden Summe addiert und ausgegeben. Die Suche stoppt, sobald die gewünschte Anzahl gefunden wurde.
Die ersten beiden bekannten Werte dienen als Checkpoint:
$$219869980,\qquad 312501820.$$
Parallelisierung wird nur für die segmentierte Siebphase verwendet. Die eigentliche Fensterprüfung bleibt sequentiell, weil die Primzahlen in zunehmender Reihenfolge verarbeitet werden müssen.
Die Funktion choose_thread_count begrenzt die Anzahl der Worker anhand der Arbeitslast und der Hardware.
Der Solver parst Optionen wie --limit, --target, --segment, --threads, --single-thread und --skip-checkpoints. Danach werden die Basisprimzahlen erzeugt, der praktische Gegencheck bis 400 ausgeführt, sofern er nicht deaktiviert wurde, und schließlich find_paradises aufgerufen.
is_practical implementiert das Stewart-Sierpiński-Kriterium. is_practical_bruteforce ist die Referenzdefinition über Teiler-Teilmenge-Summen. sieve_segment erzeugt die Primzahlen eines Segments. find_paradises führt die vierfache Primfenstersuche aus.
Ein wichtiges Detail ist, dass Segmentbatches zwar parallel gesiebt werden können, die Lambda-Funktion process_prime die resultierenden Primlisten aber weiterhin in Segmentreihenfolge konsumiert. Nur so bleibt die Bedeutung von „vier aufeinanderfolgenden Primzahlen“ erhalten.
Das Vorberechnen der Basisprimzahlen bis \(\sqrt{\text{limit}+9}\) ist klein gegenüber der Gesamtsuche. Das segmentierte Sieb liegt nahe bei
$$O(L\log\log L)$$
für Obergrenze \(L\) und benötigt nur segmentgroßen Arbeitsspeicher. Die Praktikalitätsprüfung eines Kandidaten faktorisiert fünf nahe Zahlen und wendet das multiplikative Kriterium an, also sind die Kandidatenprüfungen selten und billig.
Der Brute-Force-Check ist deutlich langsamer, läuft aber nur für \(n\le 400\). Dadurch bleibt er ein sicherer Validator ohne Einfluss auf die Hauptkomplexität.
Kod, engineers' paradise denilen özel tam sayıları arar. Bir aday \(n\) için iki şart vardır: \(n\) merkezli dört asalın 6-6-6 aralıklı bir pencere oluşturması ve \(n-8, n-4, n, n+4, n+8\) sayılarının hepsinin pratik sayı olması gerekir. İlk \(k\) aday toplanır.
İlk filtre tamamen asallara dayanır. Program dört ardışık asal \(p_0,p_1,p_2,p_3\) için
$$p_1-p_0=p_2-p_1=p_3-p_2=6$$
eşitliğini kontrol eder. Bu sağlanırsa asal dörtgen şu biçimdedir:
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18.$$
Bu durumda aday merkez
$$n=p_0+9$$
olur. Aynı şey
$$n-9,\ n-3,\ n+3,\ n+9$$
şeklinde de okunabilir.
Somut bir mini örnek olarak bu biçimdeki ilk asal pencere
$$251,\ 257,\ 263,\ 269$$
olur. Buradan merkez
$$n=251+9=260$$
çıkar. Pratik sayı aşaması bu kez
$$252,\ 256,\ 260,\ 264,\ 268$$
değerlerini test eder. İlk dört sayı pratiktir, fakat 268 pratik değildir; dolayısıyla 260 elenir. Bu örnek tüm arama mantığını gösterir: asal pencere yalnızca gerekli bir koşuldur, gerçek paradise kararı beş yerel pratiklik testinden sonra verilir.
Pozitif bir \(m\) sayısı, 1'den \(m\)'ye kadar her sayının \(m\)'nin farklı bölenlerinin toplamı olarak yazılabildiği durumda pratik sayı adını alır.
Aday \(n\) için şu beş sayının tamamı pratik olmalıdır:
$$n-8,\ n-4,\ n,\ n+4,\ n+8.$$
Bu yüzden adayın en az 9 olması gerekir.
Şöyle bir ayrışım düşünelim:
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
Prefix çarpımı
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
ve onun bölen toplamı
$$S_i=\sigma(A_i)$$
olsun. O zaman \(N\) ancak ve ancak \(q_1=2\) ve
$$q_{i+1}\le S_i+1\qquad(1\le i<r)$$
sağlanıyorsa pratiktir.
Kod \(\sigma(A_i)\)'yi sıfırdan tekrar hesaplamaz; sayıyı artan asal sırada çarpanlarına ayırır ve bir prefix değeri taşır.
Bir asal kuvvet için
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
Örnek:
$$12=2^2\cdot 3.$$
Prefix \(2^2\) için
$$S_1=\sigma(2^2)=1+2+4=7$$
ve sonraki asal çarpan 3'tür. \(3\le 7+1\) olduğu için 12 pratiktir.
Karşı örnek:
$$14=2\cdot 7$$
için prefix değeri \(S_1=3\) olur, ama \(7>3+1\). Dolayısıyla 14 pratik değildir.
Uygulama ayrıca referans bir test içerir. Bölenler üretilir, sonra altkümeler toplamı tipi bir DP ile 1'den \(n\)'ye kadar tüm sayıların farklı bölenlerin toplamı olarak yazılıp yazılamadığı kontrol edilir.
Bu yavaş yöntem sadece doğrulama içindir. Kod, Stewart-Sierpiński ölçütünün brute-force tanım ile \(n\le 400\) aralığında aynı sonucu verdiğini kontrol eder.
Bu checkpoint yalnızca birkaç örneği denemek anlamına gelmez. is_practical uygulamasını \(1\le n\le 400\) aralığındaki her tam sayı için doğrudan tanımla karşılaştırır; böylece çarpanlara ayırma, bölen üretimi ya da altküme-toplam DP'sindeki bir hata büyük arama başlamadan yakalanır.
Asallar iki katmanda üretilir. Önce \(\sqrt{\text{limit}+9}\)'a kadar klasik elekle temel asallar bulunur. Bu liste hem segmentli eleme hem de çarpanlara ayırma için kullanılır.
Sonra \([3,\text{limit}+9]\) aralığı segmentlere bölünür. Her segment yalnızca tek sayıları tutar, böylece bellek küçülür. Segmentler paralel işlenebilir; fakat her segmentin içindeki asallar artan sırada ele alınır.
find_paradises fonksiyonu asal akışını okur ve son dört asalı bir kuyrukta tutar. Pencere 6-6-6 desenini sağladığı anda
$$n=p_0+9$$
adayı üretilir ve beş pratiklik koşulu test edilir.
Aday geçerse kaydedilir, toplama eklenir ve bulunduğu yazdırılır. Arama istenen sayıda paradise bulununca durur.
İlk iki bilinen değer checkpoint olarak kullanılır:
$$219869980,\qquad 312501820.$$
Paralellik yalnızca segmentli eleme aşamasında kullanılır. Asal pencere taraması sıralı kalır; çünkü asalların artan sırada işlenmesi gerekir.
choose_thread_count yardımcı fonksiyonu iş yüküne ve donanıma göre işçi sayısını sınırlar.
Kod; --limit, --target, --segment, --threads, --single-thread ve --skip-checkpoints gibi seçenekleri okur. Ardından temel asallar üretilir, kapatılmadıysa 400'e kadar pratiklik kontrolü yapılır ve find_paradises çağrılır.
is_practical Stewart-Sierpiński ölçütünü uygular. is_practical_bruteforce referans tanımdır. sieve_segment bir segmentin asal listesini çıkarır. find_paradises ise dört asallı pencere taramasını yapar.
Önemli bir ayrıntı şudur: segmentler paralel elense bile process_prime lambda'sı ortaya çıkan asal listelerini yine artan segment sırasıyla tüketir. “Dört ardışık asal” koşulunun anlamını koruyan şey bu sıralı birleştirmedir.
\(\sqrt{\text{limit}+9}\)'a kadar olan klasik eleme küçüktür. Segmentli asal üretim yaklaşık
$$O(L\log\log L)$$
maliyetlidir ve çalışma belleği yalnızca segment büyüklüğündedir. Bir adayın pratiklik testi beş yakın sayıyı çarpanlara ayırır ve çarpımsal kriteri uygular; bu yüzden aday kontrolleri seyrek ve ucuzdur.
Brute-force kontrol daha yavaştır, fakat yalnızca \(n\le 400\) için çalışır. Bu yüzden ana asimptotiği etkilemeyen güvenli bir doğrulayıcıdır.
El programa busca enteros especiales llamados engineers' paradises. Un candidato \(n\) debe cumplir dos condiciones: cuatro primos consecutivos alrededor de \(n\) deben formar una ventana con saltos de 6, y los cinco números \(n-8, n-4, n, n+4, n+8\) deben ser números prácticos. El solver suma los primeros \(k\) paradises que encuentra.
El primer filtro usa solo primos. El programa mantiene una ventana deslizante de cuatro primos consecutivos \(p_0,p_1,p_2,p_3\) y verifica
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
Entonces los cuatro primos son
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
y el centro candidato es
$$n=p_0+9.$$
Equivalentemente, la ventana se centra en
$$n-9,\ n-3,\ n+3,\ n+9.$$
Un ejemplo en miniatura es la primera ventana prima con esta forma:
$$251,\ 257,\ 263,\ 269.$$
Esto produce el centro
$$n=251+9=260.$$
La etapa de números prácticos comprueba entonces
$$252,\ 256,\ 260,\ 264,\ 268.$$
Los cuatro primeros son prácticos, pero 268 no lo es, así que 260 se descarta. Este ejemplo muestra toda la lógica de la búsqueda: la ventana prima es solo una condición necesaria; el estado de paradise se decide únicamente después de las cinco pruebas locales de practicidad.
Un entero positivo \(m\) es práctico si todo número entre 1 y \(m\) puede escribirse como suma de divisores distintos de \(m\).
Para un candidato \(n\), los cinco números
$$n-8,\ n-4,\ n,\ n+4,\ n+8$$
deben ser prácticos. Por eso \(n\) tiene que ser al menos 9.
Sea
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
Definimos el prefijo
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
y su suma de divisores
$$S_i=\sigma(A_i).$$
Entonces \(N\) es práctico si y solo si \(q_1=2\) y
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
El código no recalcula \(\sigma(A_i)\) desde cero en cada paso. Factoriza el número en orden creciente de primos y mantiene un valor acumulado.
Para una potencia prima,
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
Ejemplo:
$$12=2^2\cdot 3.$$
Para el prefijo \(2^2\),
$$S_1=\sigma(2^2)=1+2+4=7,$$
y el siguiente primo es 3. Como \(3\le 7+1\), 12 es práctico.
En cambio,
$$14=2\cdot 7$$
falla porque el prefijo tras \(2\) es \(S_1=3\), pero \(7>3+1\).
La implementación incluye una prueba de referencia. Se generan todos los divisores y luego se usa una DP de suma de subconjuntos para comprobar que cada valor de 1 a \(n\) es alcanzable como suma de divisores distintos.
Este método lento solo se usa para validación. El programa comprueba que el criterio de Stewart-Sierpiński coincide con la definición brute force para todo \(n\le 400\).
Este checkpoint hace más que verificar unos pocos casos aislados. Compara la implementación concreta de is_practical con la definición para cada entero en \(1\le n\le 400\), de modo que un error en la factorización, en la generación de divisores o en la DP de sumas de subconjuntos aparece antes de arrancar la búsqueda grande.
La generación de primos se divide en dos capas. Primero, el código calcula todos los primos base hasta \(\sqrt{\text{limit}+9}\) con una criba normal. Esa lista se usa tanto para la criba segmentada como para factorizar candidatos.
Después, el rango \([3,\text{limit}+9]\) se procesa por segmentos. Cada segmento guarda solo números impares, así que la memoria se mantiene pequeña. Los segmentos pueden paralelizarse, pero dentro de cada uno los primos se emiten en orden creciente.
find_paradises lee el flujo de primos y conserva una ventana de los últimos cuatro primos. Cuando la ventana cumple el patrón 6-6-6, forma el candidato
$$n=p_0+9$$
y verifica las cinco condiciones de practicidad.
Si pasa, el valor se guarda, se suma al acumulado y se imprime como paradise encontrado. La búsqueda se detiene cuando se han encontrado los primeros \(k\) pedidos.
Los dos primeros valores conocidos se usan como checkpoint:
$$219869980,\qquad 312501820.$$
La paralelización solo se usa en la fase de criba segmentada. El barrido de la ventana prima sigue siendo secuencial, porque los primos deben procesarse en orden creciente.
La función choose_thread_count limita el número de hilos según la carga y el hardware.
El solver analiza opciones como --limit, --target, --segment, --threads, --single-thread y --skip-checkpoints. Luego construye los primos base, ejecuta la verificación práctica hasta 400 salvo que se desactive y llama a find_paradises.
is_practical implementa el criterio de Stewart-Sierpiński. is_practical_bruteforce es la definición de referencia. sieve_segment genera los primos de un segmento. find_paradises lleva a cabo el barrido de cuatro primos.
Un detalle importante es que los lotes segmentados pueden cribarse en paralelo, pero la lambda process_prime sigue consumiendo las listas resultantes en orden creciente de segmentos. Eso conserva el significado de “cuatro primos consecutivos”, que se perdería con una mezcla desordenada.
La criba base hasta \(\sqrt{\text{limit}+9}\) es pequeña. La criba segmentada cuesta aproximadamente
$$O(L\log\log L)$$
para límite \(L\), y usa solo memoria del tamaño del segmento. La prueba de practicidad de un candidato factoriza cinco números cercanos y aplica el criterio multiplicativo, así que las comprobaciones son poco frecuentes y baratas.
La verificación brute-force es mucho más lenta, pero solo corre para \(n\le 400\). Por eso sirve como validador seguro sin afectar la complejidad principal.
程序寻找一类特殊整数，称为 engineers' paradises。一个候选数 \(n\) 必须同时满足两件事：以 \(n\) 为中心的四个连续质数要形成间隔为 6 的窗口；并且 \(n-8, n-4, n, n+4, n+8\) 这五个数都必须是实用数。程序找出前 \(k\) 个这样的数并求和。
第一个筛选器只看质数。程序维护一个由四个连续质数 \(p_0,p_1,p_2,p_3\) 组成的滑动窗口，并检查
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
若成立，则四个质数恰好是
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
候选中心就是
$$n=p_0+9.$$
等价地，这个窗口以
$$n-9,\ n-3,\ n+3,\ n+9$$
为中心。
一个很具体的小例子是第一个满足这种形状的质数窗口：
$$251,\ 257,\ 263,\ 269.$$
它给出中心
$$n=251+9=260.$$
随后实用数阶段检查
$$252,\ 256,\ 260,\ 264,\ 268.$$
前四个值都是实用数，但 268 不是，所以 260 被淘汰。这个例子正好说明整条搜索链：质数窗口只是必要条件，是否真的是 paradise 要由后面的五个局部实用数测试决定。
正整数 \(m\) 若能把 1 到 \(m\) 之间的每个整数表示成 \(m\) 的不同因子的和，则称为实用数。
对候选 \(n\)，必须检查五个数：
$$n-8,\ n-4,\ n,\ n+4,\ n+8.$$
因此 \(n\) 至少要是 9。
设
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
定义前缀乘积
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
及其约数和
$$S_i=\sigma(A_i).$$
那么 \(N\) 是实用数，当且仅当 \(q_1=2\) 且
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
程序不会在每一步都从头计算 \(\sigma(A_i)\)。它按从小到大的质因数分解，并维护一个累积前缀值。
对于素数幂，
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
例如：
$$12=2^2\cdot 3.$$
前缀 \(2^2\) 时，
$$S_1=\sigma(2^2)=1+2+4=7,$$
下一个质因子是 3，满足 \(3\le 7+1\)，因此 12 是实用数。
而
$$14=2\cdot 7$$
则失败，因为前缀后 \(S_1=3\)，但 \(7>3+1\)。
实现里还包含一个参考实现。它枚举所有因子，然后用类似子集和的 DP 检查 1 到 \(n\) 的每个值是否都能表示成不同因子的和。
这个慢方法只用于验证。程序会检查 Stewart-Sierpiński 判据和 brute-force 定义在 \(n\le 400\) 上完全一致。
这个 checkpoint 不只是随手抽查几个例子。它把 is_practical 的具体实现与定义本身在整个 \(1\le n\le 400\) 区间逐一比对，因此无论是分解、因子生成还是子集和 DP 出错，都会在大规模搜索开始前暴露出来。
质数生成分成两层。先用普通筛法求出 \(\sqrt{\text{limit}+9}\) 以内的基础质数，这些质数同时用于分段筛和候选数分解。
然后把 \([3,\text{limit}+9]\) 分成若干段。每段只存奇数，所以内存较小。段可以并行处理，但每段内部仍按升序输出质数。
find_paradises 读取质数流，维护最近四个质数的窗口。只要窗口满足 6-6-6 模式，就构造
$$n=p_0+9$$
并检查五个实用数条件。
如果都通过，就记录、累加并输出该 paradise。搜索会在找到所需数量后停止。
前两个已知值作为 checkpoint：
$$219869980,\qquad 312501820.$$
并行只用于分段筛阶段。质数窗口扫描仍然是顺序的，因为必须按递增顺序处理质数。
choose_thread_count 会根据工作量和硬件限制线程数。
程序会解析 --limit、--target、--segment、--threads、--single-thread 和 --skip-checkpoints 等选项。然后构造基础质数列表，在未关闭时运行到 400 为止的实用数校验，再调用 find_paradises。
is_practical 实现 Stewart-Sierpiński 判据。is_practical_bruteforce 是参考定义。sieve_segment 生成某个分段的质数。find_paradises 则执行四质数窗口扫描。
一个重要细节是：虽然各个分段可以并行筛出质数，但 lambda process_prime 仍按分段的递增顺序消费这些质数列表。只有这样，“四个连续质数”的语义才不会被乱序合并破坏。
到 \(\sqrt{\text{limit}+9}\) 为止的基础筛非常小。分段筛的复杂度近似为
$$O(L\log\log L)$$
其中 \(L\) 是上界，而且只需要分段大小的工作内存。候选的实用性测试只涉及 5 个附近数的分解，因此检查很稀疏，代价也很低。
brute-force 校验更慢，但只在 \(n\le 400\) 上运行，所以不会影响主程序的整体复杂度。
Программа ищет особые числа, называемые engineers' paradises. Кандидат \(n\) должен одновременно удовлетворять двум условиям: четыре последовательных простых вокруг \(n\) должны образовывать окно с шагом 6, а числа \(n-8, n-4, n, n+4, n+8\) должны быть практическими. Затем суммируются первые \(k\) таких чисел.
Первый фильтр работает только по простым. Программа хранит скользящее окно из четырёх последовательных простых \(p_0,p_1,p_2,p_3\) и проверяет
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
Тогда эти четыре простых равны
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
а центр кандидата равен
$$n=p_0+9.$$
Эквивалентно, окно центрируется в точках
$$n-9,\ n-3,\ n+3,\ n+9.$$
Конкретный мини-пример даёт первое окно простых такого вида:
$$251,\ 257,\ 263,\ 269.$$
Оно даёт центр
$$n=251+9=260.$$
Далее этап проверки практичности рассматривает
$$252,\ 256,\ 260,\ 264,\ 268.$$
Первые четыре числа практические, а 268 нет, поэтому 260 отбрасывается. Этот пример хорошо показывает общую логику поиска: окно простых является лишь необходимым условием, а статус paradise определяется только после пяти локальных проверок практичности.
Положительное целое \(m\) называется практическим, если каждое число от 1 до \(m\) можно представить как сумму различных делителей \(m\).
Для кандидата \(n\) нужно проверить пять чисел:
$$n-8,\ n-4,\ n,\ n+4,\ n+8.$$
Поэтому \(n\) должно быть не меньше 9.
Пусть
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
Определим префикс
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
и сумму делителей
$$S_i=\sigma(A_i).$$
Тогда \(N\) практическое тогда и только тогда, когда \(q_1=2\) и
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
Код не пересчитывает \(\sigma(A_i)\) с нуля на каждом шаге. Он факторизует число по возрастанию простых и поддерживает накопленный префикс.
Для степени простого
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
Пример:
$$12=2^2\cdot 3.$$
Для префикса \(2^2\)
$$S_1=\sigma(2^2)=1+2+4=7,$$
и следующий простой множитель равен 3. Поскольку \(3\le 7+1\), число 12 практическое.
А вот
$$14=2\cdot 7$$
не проходит: после префикса \(2\) имеем \(S_1=3\), но \(7>3+1\).
В реализации есть эталонная проверка. Она перечисляет все делители и затем запускает DP по подмножествам, чтобы убедиться, что каждое число от 1 до \(n\) представимо как сумма различных делителей.
Этот медленный метод используется только для валидации. Программа проверяет, что критерий Стюарта-Шерпинского совпадает с brute-force определением для всех \(n\le 400\).
Этот checkpoint делает больше, чем простая выборочная проверка. Он сравнивает конкретную реализацию is_practical с определением для каждого целого в диапазоне \(1\le n\le 400\), так что ошибка в факторизации, генерации делителей или DP по суммам подмножеств обнаруживается ещё до большого поиска.
Генерация простых разделена на две части. Сначала обычным решетом вычисляются базовые простые до \(\sqrt{\text{limit}+9}\). Этот список используется и для сегментированного решета, и для факторизации кандидатов.
Затем диапазон \([3,\text{limit}+9]\) обрабатывается по сегментам. В каждом сегменте хранятся только нечётные числа, поэтому память остаётся небольшой. Сегменты можно обрабатывать параллельно, но внутри каждого сегмента простые выдаются по возрастанию.
find_paradises читает поток простых и хранит окно из последних четырёх простых. Как только окно удовлетворяет шаблону 6-6-6, строится кандидат
$$n=p_0+9$$
и проверяются пять условий практичности.
Если все они выполнены, кандидат записывается, добавляется к сумме и печатается как найденный paradise. Поиск останавливается, когда найдено нужное число значений.
Первые два известных значения используются как checkpoint:
$$219869980,\qquad 312501820.$$
Параллелизм используется только в сегментированном решете. Обход окна простых остаётся последовательным, потому что простые должны обрабатываться в порядке возрастания.
choose_thread_count ограничивает число потоков по нагрузке и возможностям железа.
Программа разбирает параметры --limit, --target, --segment, --threads, --single-thread и --skip-checkpoints. Затем строится список базовых простых, запускается проверка практичности до 400, если она не отключена, и вызывается find_paradises.
is_practical реализует критерий Стюарта-Шерпинского. is_practical_bruteforce служит эталонным определением. sieve_segment генерирует простые внутри сегмента. find_paradises выполняет поиск по четырём простым в окне.
Важная тонкость состоит в том, что сегменты можно просеивать параллельно, но лямбда process_prime всё равно потребляет полученные списки простых в порядке возрастания сегментов. Именно это сохраняет смысл условия «четыре последовательных простых».
Базовое решето до \(\sqrt{\text{limit}+9}\) мало по сравнению с основной задачей. Сегментированное решето работает примерно за
$$O(L\log\log L)$$
для границы \(L\) и использует лишь память размера сегмента. Проверка практичности кандидата факторизует пять близких чисел и применяет мультипликативный критерий, поэтому такие проверки редки и дешевы.
Brute-force проверка намного медленнее, но запускается только для \(n\le 400\). Это делает её безопасным валидатором, не влияющим на основную асимптотику.
يبحث البرنامج عن أعداد خاصة تسمى engineers' paradises. يجب أن يحقق المرشح \(n\) شرطين مستقلين: أربع أعداد أولية متتالية حول \(n\) يجب أن تشكل نافذة بفواصل 6، والأعداد \(n-8, n-4, n, n+4, n+8\) يجب أن تكون كلها أعدادًا عملية. ثم تُجمع أول \(k\) قيم تحقق ذلك.
أول مرشح يعتمد على الأعداد الأولية فقط. يحتفظ البرنامج بنافذة منزلقة من أربعة أعداد أولية متتالية \(p_0,p_1,p_2,p_3\) ويتحقق من
$$p_1-p_0=p_2-p_1=p_3-p_2=6.$$
إذا تحقق ذلك، فإن الأعداد الأربعة تكون بالضبط
$$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$$
ويكون المركز المرشح هو
$$n=p_0+9.$$
وبصورة مكافئة، تتمركز النافذة حول
$$n-9,\ n-3,\ n+3,\ n+9.$$
يوجد مثال صغير ملموس هو أول نافذة أولية بهذا الشكل:
$$251,\ 257,\ 263,\ 269.$$
ومنها نحصل على المركز
$$n=251+9=260.$$
ثم تختبر مرحلة الأعداد العملية القيم
$$252,\ 256,\ 260,\ 264,\ 268.$$
القيم الأربع الأولى عملية، لكن 268 ليس عددًا عمليًا، ولذلك يُرفض 260. يوضح هذا المثال منطق البحث كله: نافذة الأعداد الأولية شرط لازم فقط، أما قرار كون العدد paradise فعلًا فلا يُحسم إلا بعد اختبارات العملية الخمسة المحلية.
يُسمى العدد الصحيح الموجب \(m\) عمليًا إذا أمكن كتابة كل عدد من 1 إلى \(m\) كمجموع لعوامل مختلفة من عوامل \(m\).
بالنسبة إلى المرشح \(n\)، يجب التحقق من خمسة أعداد:
$$n-8,\ n-4,\ n,\ n+4,\ n+8.$$
لذلك يجب أن يكون \(n\ge 9\).
ليكن
$$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$$
وعرّف حاصل الضرب الجزئي
$$A_i=\prod_{j=1}^{i} q_j^{a_j}$$
ومجموع القواسم
$$S_i=\sigma(A_i).$$
عندئذٍ يكون \(N\) عمليًا إذا وفقط إذا كان \(q_1=2\) و
$$q_{i+1}\le S_i+1\qquad(1\le i<r).$$
لا يعيد الكود حساب \(\sigma(A_i)\) من البداية في كل خطوة، بل يقوم بتحليل العدد إلى عوامله الأولية بالترتيب التصاعدي ويحافظ على قيمة تراكمية.
ولقوة أولية \(p^a\)، لدينا
$$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1}.$$
مثال:
$$12=2^2\cdot 3.$$
للمقطع \(2^2\) نحصل على
$$S_1=\sigma(2^2)=1+2+4=7,$$
والعامل الأولي التالي هو 3، وبما أن \(3\le 7+1\) فإن 12 عدد عملي.
أما
$$14=2\cdot 7$$
فتفشل، لأن \(S_1=3\) بعد العامل 2، ولكن \(7>3+1\).
يتضمن التنفيذ فحصًا مرجعيًا. فهو يولد جميع القواسم، ثم يستخدم DP شبيهًا بمجموع المجموعات للتأكد من أن كل عدد من 1 إلى \(n\) يمكن تمثيله كمجموع لعوامل مختلفة.
هذه الطريقة البطيئة تُستخدم فقط للتحقق. ويقارن البرنامج معيار Stewart-Sierpiński بالتعريف brute-force لكل \(n\le 400\).
ونقطة التحقق هذه ليست مجرد فحص لعدة أمثلة عشوائية. فهي تقارن تنفيذ is_practical نفسه بالتعريف المباشر لكل عدد في المجال \(1\le n\le 400\)، ولذلك فإن أي خطأ في التحليل إلى عوامل أو توليد القواسم أو DP الخاص بمجاميع المجموعات يظهر قبل بدء البحث الكبير.
توليد الأعداد الأولية يتم على طبقتين. أولًا يُحسب جميع الأعداد الأولية الأساسية حتى \(\sqrt{\text{limit}+9}\) باستخدام غربال عادي. وتُستخدم هذه القائمة في الغربال المقطّع وفي تحليل المرشحين إلى عوامل.
بعد ذلك يُقسَّم المجال \([3,\text{limit}+9]\) إلى مقاطع. كل مقطع يحتفظ بالأعداد الفردية فقط، لذلك تبقى الذاكرة صغيرة. ويمكن معالجة المقاطع بالتوازي، لكن داخل كل مقطع تُخرج الأعداد الأولية بترتيب تصاعدي.
تقرأ الدالة find_paradises تيار الأعداد الأولية وتحافظ على نافذة من آخر أربعة أعداد أولية. متى ما حققت النافذة نمط 6-6-6، يُبنى المرشح
$$n=p_0+9$$
وتُفحص شروط العملية الخمسة.
إذا نجح المرشح، يُخزن ويُضاف إلى المجموع الجاري ويُطبع بوصفه paradise تم العثور عليه. وتتوقف العملية عندما يتم العثور على العدد المطلوب.
وتُستخدم أول قيمتين معروفتين كنقطة تحقق:
$$219869980,\qquad 312501820.$$
يُستخدم التوازي فقط في مرحلة الغربال المقطّع. أما مسح النافذة الأولية فيبقى تسلسليًا، لأن الأعداد الأولية يجب أن تُعالج بترتيب تصاعدي.
وتحد الدالة choose_thread_count عدد الخيوط بحسب الحمل وقدرة الجهاز.
يحلل البرنامج الخيارات --limit و--target و--segment و--threads و--single-thread و--skip-checkpoints. ثم يُبنى جدول الأعداد الأولية الأساسية، ويُجرى فحص العملية حتى 400 ما لم يُعطَّل، ثم تُستدعى find_paradises.
is_practical يطبق معيار Stewart-Sierpiński. وis_practical_bruteforce هو التعريف المرجعي. وsieve_segment يولد الأعداد الأولية داخل المقطع. أما find_paradises فينفذ المسح بنافذة من أربعة أعداد أولية.
ومن التفاصيل المهمة أن المقاطع قد تُغربل بالتوازي، لكن lambda المسماة process_prime تستهلك قوائم الأعداد الأولية الناتجة مع ذلك بترتيب المقاطع التصاعدي. هذا هو ما يحافظ على معنى شرط «أربعة أعداد أولية متتالية».
الغربال الأساسي حتى \(\sqrt{\text{limit}+9}\) صغير مقارنة بالمهمة الرئيسية. الغربال المقطّع يكلف تقريبًا
$$O(L\log\log L)$$
لحد \(L\)، ويستخدم فقط ذاكرة بحجم المقطع. وفحص العملية لمرشح ما يحلل خمسة أعداد قريبة ويطبق معيارًا ضربيًا، لذلك تبقى الفحوصات نادرة ورخيصة.
أما brute-force فهو أبطأ بكثير، لكنه يعمل فقط لـ \(n\le 400\). لذلك فهو أداة تحقق آمنة لا تؤثر في التعقيد الرئيسي.