An even integer \(n\) is called admissible when it is either a power of \(2\) or, equivalently for even numbers, its distinct prime factors form a consecutive prefix of the prime list \(2,3,5,7,\ldots\). For every admissible \(n < 10^9\), define \(M(n)\) as the smallest integer \(m>1\) such that \(n+m\) is prime. The task is to sum the distinct values of \(M(n)\).
Because \(n\) is even, the first prime \(2\) must appear. If the distinct prime factors are consecutive, then every admissible number has the form
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
The special case "power of \(2\)" is simply the case \(k=1\). So admissible numbers are described completely by choosing a prime prefix and choosing a positive exponent for each prime in that prefix.
This already gives a strong bound on the search space. The product of the first nine primes is
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
while including the next prime gives
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
Therefore no admissible number below \(10^9\) can contain \(29\) or any later prime as a distinct factor. The code keeps a slightly longer fixed prime list, but recursion automatically prunes everything beyond the limit.
The recursive generator works on the ordered prime list \((2,3,5,7,\ldots)\). Suppose we are currently at prime \(p_i\) with a partial product built from the earlier prefix. The loop repeatedly multiplies by \(p_i\):
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
as long as the product stays below the limit. Every time at least one copy of \(p_i\) has been chosen, the recursion may continue to the next prime \(p_{i+1}\).
This does exactly what we need:
Positive exponents. Once a prime is included, it appears with exponent at least \(1\).
Consecutive prefix only. The recursion may move from \(p_i\) to \(p_{i+1}\) only after choosing \(p_i\), so later primes can never appear while skipping an earlier one.
No duplicates. Each exponent vector \((a_1,\ldots,a_k)\) corresponds to one unique recursion path.
So the DFS enumerates every admissible number once and only once, without scanning all even integers up to \(10^9\).
By definition, \(M(n)\) is the smallest integer \(m>1\) such that \(n+m\) is prime. Since every admissible \(n\) is even, any prime larger than \(2\) has to be odd, so \(m\) must be odd as well. Therefore the candidates are exactly
$$m = 3,5,7,9,\ldots$$
and the code tests them in increasing order until \(n+m\) is prime.
For example, \(16\) is admissible because it is a power of \(2\). We cannot use \(m=1\) because the definition requires \(m>1\). Then
$$16+3 = 19,$$
which is prime, so
$$M(16)=3.$$
Likewise, \(630 = 2\cdot 3^2\cdot 5\cdot 7\) is admissible because its distinct primes are \(2,3,5,7\). Testing odd values gives
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
all composite, while
$$630+11=641$$
is prime, hence
$$M(630)=11.$$
The problem asks for the sum of distinct values \(M(n)\), not the sum over all admissible \(n\). Different admissible numbers can share the same pseudo-Fortunate value, so the implementation inserts each result into a set first:
$$\mathcal{M} = \{M(n) : n \text{ admissible},\ n < 10^9\}.$$
The final answer is then
$$\sum_{m \in \mathcal{M}} m.$$
This is mathematically important: without deduplication we would answer a different question.
After admissible numbers have been generated, the expensive repeated task is to test whether \(n+m\) is prime. The code uses deterministic Miller-Rabin for 64-bit integers, so each test is exact in this range and still very fast. That makes the straightforward odd-step search practical.
The implementation verifies itself with three simple checks:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
The first two confirm the pseudo-Fortunate search itself. The third compares the efficient DFS enumeration against a brute-force admissibility test on a smaller limit, which is a strong check that the generator is complete and duplicate-free.
prime_prefix() provides a fixed initial segment of the prime list. generate_admissible(...) performs the DFS over exponent choices and stores every admissible product in a set. For each stored \(n\), pseudo_fortunate(n) checks odd \(m=3,5,7,\ldots\) until \(n+m\) is prime. These \(M(n)\) values are inserted into another set, and the program sums that set at the end.
Let \(A\) be the number of admissible numbers below the limit, and let \(T(n)\) be the number of odd candidates tested before finding \(M(n)\). Then the total running time is roughly
$$O\!\left(A + \sum_{n \in \text{admissible}} T(n)\cdot C_{\text{prime}}\right),$$
where \(C_{\text{prime}}\) is the cost of one primality test. Memory usage is \(O(A + |\mathcal{M}|)\) for the two sets. The crucial gain comes from generating only admissible numbers rather than scanning all even numbers up to \(10^9\).
Eine gerade Zahl \(n\) heißt zulässig, wenn sie entweder eine Zweierpotenz ist oder, äquivalent für gerade Zahlen, ihre verschiedenen Primfaktoren einen zusammenhängenden Präfix der Primzahlen \(2,3,5,7,\ldots\) bilden. Für jedes zulässige \(n < 10^9\) ist \(M(n)\) die kleinste Zahl \(m>1\), für die \(n+m\) prim ist. Gesucht ist die Summe der verschiedenen Werte \(M(n)\).
Weil \(n\) gerade ist, muss der erste Primfaktor \(2\) vorkommen. Sind die verschiedenen Primfaktoren aufeinanderfolgend, dann hat jede zulässige Zahl die Form
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
Der Spezialfall "Zweierpotenz" ist genau der Fall \(k=1\). Zulässige Zahlen entstehen also durch Wahl eines Primpräfixes und positiver Exponenten für alle Primzahlen dieses Präfixes.
Damit ist der Suchraum bereits stark beschränkt. Das Produkt der ersten neun Primzahlen ist
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
aber mit der nächsten Primzahl erhält man
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
Daher kann keine zulässige Zahl unter \(10^9\) den Primfaktor \(29\) oder einen späteren Primfaktor enthalten. Der Code benutzt dennoch eine etwas längere feste Primliste; die Rekursion schneidet übergroße Produkte automatisch ab.
Der rekursive Generator arbeitet auf der geordneten Primliste \((2,3,5,7,\ldots)\). Angenommen, wir stehen gerade bei \(p_i\) und haben bereits ein Teilprodukt aus dem früheren Präfix aufgebaut. Dann multipliziert die Schleife wiederholt mit \(p_i\):
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
solange das Produkt unterhalb der Grenze bleibt. Jedes Mal, wenn mindestens eine Kopie von \(p_i\) gewählt wurde, darf die Rekursion zu \(p_{i+1}\) weitergehen.
Genau dadurch gelten die gewünschten Eigenschaften:
Positive Exponenten. Sobald eine Primzahl aufgenommen wird, ist ihr Exponent mindestens \(1\).
Nur zusammenhängende Präfixe. Zu \(p_{i+1}\) darf man erst gehen, nachdem \(p_i\) gewählt wurde; spätere Primzahlen können also nie unter Auslassung einer früheren erscheinen.
Keine Duplikate. Jeder Exponentenvektor \((a_1,\ldots,a_k)\) entspricht genau einem Rekursionspfad.
Die DFS erzeugt also jede zulässige Zahl genau einmal, ohne alle geraden Zahlen bis \(10^9\) durchsuchen zu müssen.
Per Definition ist \(M(n)\) die kleinste Zahl \(m>1\), so dass \(n+m\) prim ist. Da jedes zulässige \(n\) gerade ist, muss jede Primzahl größer als \(2\) ungerade sein; also muss auch \(m\) ungerade sein. Die Kandidaten sind daher genau
$$m = 3,5,7,9,\ldots$$
und der Code prüft sie der Reihe nach, bis \(n+m\) prim ist.
Beispiel: \(16\) ist zulässig, weil es eine Zweierpotenz ist. \(m=1\) ist nicht erlaubt, da die Definition \(m>1\) verlangt. Dann gilt
$$16+3 = 19,$$
also
$$M(16)=3.$$
Ebenso ist \(630 = 2\cdot 3^2\cdot 5\cdot 7\) zulässig, weil seine verschiedenen Primzahlen \(2,3,5,7\) sind. Die ersten ungeraden Tests liefern
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
alles zusammengesetzte Zahlen, aber
$$630+11=641$$
ist prim, also
$$M(630)=11.$$
Gesucht ist die Summe der verschiedenen Werte \(M(n)\), nicht die Summe über alle zulässigen \(n\). Verschiedene zulässige Zahlen können denselben pseudo-Fortunate-Wert besitzen, daher legt die Implementierung alle Ergebnisse zunächst in einer Menge ab:
$$\mathcal{M} = \{M(n) : n \text{ zulässig},\ n < 10^9\}.$$
Die Endantwort ist dann
$$\sum_{m \in \mathcal{M}} m.$$
Ohne diese Deduplikation würde man also eine andere Aufgabe lösen.
Nachdem die zulässigen Zahlen erzeugt wurden, besteht der teure Teil darin zu prüfen, ob \(n+m\) prim ist. Dafür verwendet der Code den deterministischen Miller-Rabin-Test für 64-Bit-Zahlen. Jede Prüfung ist in diesem Bereich exakt und gleichzeitig schnell genug, um die lineare Suche über ungerade \(m\) praktikabel zu machen.
Die Implementierung kontrolliert sich mit drei einfachen Tests:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
Die ersten beiden Tests prüfen die pseudo-Fortunate-Suche selbst. Der dritte vergleicht die effiziente DFS-Erzeugung mit einer Brute-Force-Zulässigkeitsprüfung auf kleinerem Bereich und ist damit eine starke Bestätigung, dass der Generator vollständig und duplikatfrei ist.
prime_prefix() liefert einen festen Anfang der Primliste. generate_admissible(...) führt die DFS über die Exponentenwahl aus und speichert jedes zulässige Produkt in einer Menge. Für jedes solche \(n\) testet pseudo_fortunate(n) die ungeraden Werte \(m=3,5,7,\ldots\), bis \(n+m\) prim ist. Diese \(M(n)\)-Werte landen in einer zweiten Menge, die am Ende aufsummiert wird.
Sei \(A\) die Anzahl zulässiger Zahlen unter der Schranke und \(T(n)\) die Anzahl ungerader Kandidaten, die geprüft werden, bis \(M(n)\) gefunden ist. Dann ist die Laufzeit grob
$$O\!\left(A + \sum_{n \in \text{zulässig}} T(n)\cdot C_{\text{prime}}\right),$$
wobei \(C_{\text{prime}}\) die Kosten eines Primtests bezeichnet. Der Speicherbedarf ist \(O(A + |\mathcal{M}|)\) für die beiden Mengen. Der entscheidende Gewinn kommt daher, dass nur zulässige Zahlen erzeugt werden und nicht alle geraden Zahlen bis \(10^9\) durchlaufen werden.
Bir çift sayı \(n\), ya bir \(2\) kuvveti ise ya da eşdeğer biçimde ayrık asal bölenleri \(2,3,5,7,\ldots\) asal listesinin ardışık bir prefiksini oluşturuyorsa admissible kabul edilir. Her admissible \(n < 10^9\) için \(M(n)\), \(n+m\) sayısını asal yapan en küçük \(m>1\) değeridir. İstenen şey, farklı \(M(n)\) değerlerinin toplamıdır.
\(n\) çift olduğu için ilk asal olan \(2\) mutlaka bulunur. Ayrık asal çarpanlar ardışık olmak zorundaysa her admissible sayı şu formdadır:
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
"\(2\) kuvveti" denen özel durum aslında yalnızca \(k=1\) halidir. Yani admissible sayılar, bir asal prefiksi seçip o prefiksteki her asal için pozitif üs seçmekten ibarettir.
Bu gözlem arama uzayını ciddi biçimde daraltır. İlk dokuz asalın çarpımı
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9$$
iken bir sonraki asal da eklenirse
$$223092870 \cdot 29 = 6469693230 > 10^9$$
olur. Dolayısıyla \(10^9\) altında kalan hiçbir admissible sayı \(29\) ya da daha büyük bir asalı ayrık bölen olarak içeremez. Kod biraz daha uzun bir sabit asal listesi kullanır, fakat özyineleme limit aşıldığında zaten otomatik budanır.
Özyinelemeli üretici, sıralı asal listesi \((2,3,5,7,\ldots)\) üzerinde çalışır. Diyelim ki şu anda \(p_i\) asalındayız ve daha önceki prefiksten gelen bir kısmi çarpımımız var. Döngü bu çarpımı tekrar tekrar \(p_i\) ile çarpar:
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
ürün limit altında kaldığı sürece devam eder. \(p_i\)'den en az bir tane seçildiği her noktada özyineleme bir sonraki asala \(p_{i+1}\)'e geçebilir.
Böylece şu üç özellik aynı anda sağlanır:
Pozitif üsler. Bir asal dahil edildiyse üssü en az \(1\) olur.
Sadece ardışık prefiks. \(p_{i+1}\)'e ancak \(p_i\) seçildikten sonra geçilebildiği için daha sonraki bir asal, önceki biri atlanarak gelemez.
Tekillik. Her üs vektörü \((a_1,\ldots,a_k)\) tam olarak tek bir özyineleme yoluna karşılık gelir.
Bu yüzden DFS, \(10^9\) altındaki tüm çift sayıları taramadan her admissible sayıyı bir kez ve yalnızca bir kez üretir.
Tanım gereği \(M(n)\), \(n+m\) sayısını asal yapan en küçük \(m>1\) değeridir. Her admissible \(n\) çift olduğundan, \(2\)'den büyük bir asal elde etmek için \(m\)'in de tek olması gerekir. Dolayısıyla adaylar tam olarak
$$m = 3,5,7,9,\ldots$$
şeklindedir ve kod bunları küçükten büyüğe dener.
Örneğin \(16\), bir \(2\) kuvveti olduğu için admissible'dır. \(m=1\) kullanılamaz; çünkü tanım \(m>1\) ister. O zaman
$$16+3 = 19$$
asal olduğu için
$$M(16)=3$$
olur. Benzer biçimde \(630 = 2\cdot 3^2\cdot 5\cdot 7\) admissible'dır; çünkü ayrık asalları \(2,3,5,7\) prefiksini verir. İlk tek denemeler
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639$$
bileşik çıkar; fakat
$$630+11=641$$
asaldır. Demek ki
$$M(630)=11.$$
Problem, tüm admissible sayılar üzerindeki toplamı değil, farklı pseudo-Fortunate değerlerinin toplamını ister. Farklı admissible sayılar aynı \(M(n)\) sonucunu üretebilir. Bu yüzden kod her sonucu önce bir kümeye yerleştirir:
$$\mathcal{M} = \{M(n) : n \text{ admissible},\ n < 10^9\}.$$
Son cevap da
$$\sum_{m \in \mathcal{M}} m$$
olur. Bu deduplikasyon yapılmazsa bambaşka bir soru çözülmüş olur.
Admissible sayılar üretildikten sonra pahalı tekrar işlemi, \(n+m\)'in asal olup olmadığını sınamaktır. Kod bunun için 64-bit aralıkta deterministik Miller-Rabin testi kullanır. Böylece her test bu aralıkta tamamen doğrudur ve yine de çok hızlıdır; bu da tek sayıları sırayla deneyen doğrudan aramayı pratik hale getirir.
Uygulama kendini üç basit kontrolle doğrular:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
İlk iki kontrol pseudo-Fortunate aramasının kendisini test eder. Üçüncüsü ise hızlı DFS üretimini, daha küçük limitte brute-force admissible testiyle karşılaştırır; bu da üreticinin hem eksiksiz hem de tekrarsız olduğuna dair güçlü bir kontroldür.
prime_prefix() asal listesinin sabit bir başlangıç kesitini verir. generate_admissible(...), üs seçimleri üzerinde DFS yaparak her admissible çarpımı kümeye ekler. Ardından her \(n\) için pseudo_fortunate(n) fonksiyonu \(m=3,5,7,\ldots\) değerlerini dener ve \(n+m\) asal olduğunda durur. Bu \(M(n)\) değerleri ikinci bir kümeye atılır; program en sonda bu kümenin toplamını yazdırır.
Limit altındaki admissible sayı sayısı \(A\), \(M(n)\) bulunana kadar denenmesi gereken tek aday sayısı \(T(n)\) olsun. Toplam süre yaklaşık
$$O\!\left(A + \sum_{n \in \text{admissible}} T(n)\cdot C_{\text{prime}}\right)$$
şeklindedir; burada \(C_{\text{prime}}\) tek bir asal testinin maliyetidir. Bellek kullanımı iki küme nedeniyle \(O(A + |\mathcal{M}|)\) olur. Asıl kazanç, tüm çift sayıları taramak yerine yalnızca admissible sayıları üretmekten gelir.
Un entero par \(n\) se llama admisible si es una potencia de \(2\) o, de forma equivalente para números pares, si sus factores primos distintos forman un prefijo consecutivo de la lista de primos \(2,3,5,7,\ldots\). Para cada admisible \(n < 10^9\), se define \(M(n)\) como el menor entero \(m>1\) tal que \(n+m\) es primo. Hay que sumar los valores distintos de \(M(n)\).
Como \(n\) es par, el primer primo \(2\) debe aparecer. Si los primos distintos son consecutivos, entonces todo número admisible tiene la forma
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
El caso especial "potencia de \(2\)" es simplemente \(k=1\). Por tanto, los números admisibles se describen eligiendo un prefijo de primos y un exponente positivo para cada primo de ese prefijo.
Esto reduce mucho el espacio de búsqueda. El producto de los nueve primeros primos es
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
mientras que al incluir el siguiente primo obtenemos
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
Así, ningún admisible menor que \(10^9\) puede contener \(29\) ni un primo posterior como factor distinto. El código conserva una lista fija algo más larga, pero la recursión poda automáticamente todo lo que supera el límite.
El generador recursivo trabaja sobre la lista ordenada de primos \((2,3,5,7,\ldots)\). Supongamos que estamos en el primo \(p_i\) con un producto parcial construido a partir del prefijo anterior. El bucle multiplica repetidamente por \(p_i\):
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
mientras el producto permanezca por debajo del límite. Cada vez que se ha elegido al menos una copia de \(p_i\), la recursión puede continuar con el siguiente primo \(p_{i+1}\).
Eso garantiza exactamente lo necesario:
Exponentes positivos. Si un primo aparece, su exponente es al menos \(1\).
Solo prefijos consecutivos. Solo se puede pasar a \(p_{i+1}\) después de haber elegido \(p_i\), así que nunca aparecen primos posteriores saltándose uno anterior.
Sin duplicados. Cada vector de exponentes \((a_1,\ldots,a_k)\) corresponde a una única ruta recursiva.
En consecuencia, el DFS enumera cada número admisible exactamente una vez y evita recorrer todos los pares hasta \(10^9\).
Por definición, \(M(n)\) es el menor entero \(m>1\) tal que \(n+m\) es primo. Como todo admisible \(n\) es par, cualquier primo mayor que \(2\) es impar, luego \(m\) también debe ser impar. Los candidatos son exactamente
$$m = 3,5,7,9,\ldots$$
y el código los prueba en orden creciente hasta que \(n+m\) resulte primo.
Por ejemplo, \(16\) es admisible porque es una potencia de \(2\). No podemos usar \(m=1\) porque la definición exige \(m>1\). Entonces
$$16+3 = 19,$$
que es primo, así que
$$M(16)=3.$$
De forma similar, \(630 = 2\cdot 3^2\cdot 5\cdot 7\) es admisible porque sus primos distintos son \(2,3,5,7\). Las primeras pruebas impares dan
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
todas compuestas, mientras que
$$630+11=641$$
sí es primo, y por tanto
$$M(630)=11.$$
El problema pide la suma de los valores distintos \(M(n)\), no la suma sobre todos los \(n\) admisibles. Distintos números admisibles pueden producir el mismo valor pseudo-Fortunate, así que la implementación inserta cada resultado en un conjunto:
$$\mathcal{M} = \{M(n) : n \text{ admisible},\ n < 10^9\}.$$
La respuesta final es
$$\sum_{m \in \mathcal{M}} m.$$
Sin esta deduplicación se estaría resolviendo otra pregunta.
Una vez generados los números admisibles, la tarea costosa repetida es comprobar si \(n+m\) es primo. El código usa Miller-Rabin determinista para enteros de 64 bits, de modo que cada prueba es exacta en este rango y sigue siendo muy rápida. Eso vuelve práctica la búsqueda directa sobre impares consecutivos.
La implementación se valida con tres comprobaciones sencillas:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
Las dos primeras verifican la propia búsqueda pseudo-Fortunate. La tercera compara la enumeración eficiente por DFS con una comprobación por fuerza bruta de admisibilidad en un límite pequeño; es una confirmación fuerte de que el generador es completo y no produce duplicados.
prime_prefix() proporciona un segmento fijo inicial de los primos. generate_admissible(...) recorre por DFS las elecciones de exponentes y guarda cada producto admisible en un conjunto. Para cada \(n\) guardado, pseudo_fortunate(n) prueba \(m=3,5,7,\ldots\) hasta que \(n+m\) sea primo. Esos valores \(M(n)\) se insertan en otro conjunto y finalmente se suman.
Sea \(A\) el número de admisibles bajo el límite y sea \(T(n)\) el número de candidatos impares probados antes de encontrar \(M(n)\). Entonces el tiempo total es aproximadamente
$$O\!\left(A + \sum_{n \in \text{admisible}} T(n)\cdot C_{\text{prime}}\right),$$
donde \(C_{\text{prime}}\) es el coste de una prueba de primalidad. La memoria es \(O(A + |\mathcal{M}|)\) por los dos conjuntos. La mejora esencial proviene de generar solo números admisibles en lugar de recorrer todos los pares hasta \(10^9\).
如果一个偶数 \(n\) 是 \(2\) 的幂，或者等价地说它的不同质因子正好构成质数序列 \(2,3,5,7,\ldots\) 的一个连续前缀，那么称 \(n\) 为 admissible。对每个 admissible 的 \(n < 10^9\)，定义 \(M(n)\) 为满足 \(n+m\) 为素数的最小整数 \(m>1\)。题目要求把所有不同的 \(M(n)\) 相加。
由于 \(n\) 是偶数，第一个质因子 \(2\) 必然出现。如果不同质因子必须连续，那么每个 admissible 数都可写成
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
所谓“\(2\) 的幂”只是 \(k=1\) 的特殊情形。因此 admissible 数完全由“选择一个质数前缀，再给前缀中的每个质数选一个正指数”来描述。
这已经大幅缩小了搜索范围。前九个质数的乘积为
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
再乘以下一个质数就得到
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
所以任何小于 \(10^9\) 的 admissible 数都不可能把 \(29\) 或更大的质数当作不同质因子。代码虽然保留了更长的固定质数表，但递归会自动把超界分支剪掉。
递归生成器按有序质数表 \((2,3,5,7,\ldots)\) 工作。假设当前走到质数 \(p_i\)，并且已经有一个由前面前缀构成的部分乘积。循环会不断乘上 \(p_i\)：
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
只要乘积还没有超过上界就继续。每当已经选了至少一个 \(p_i\) 时，就允许递归进入下一个质数 \(p_{i+1}\)。
这恰好保证了三件事：
指数为正。 某个质数一旦被选入，指数至少为 \(1\)。
只能是连续前缀。 只有选了 \(p_i\) 才能进入 \(p_{i+1}\)，所以不可能跳过某个前面的质数而直接使用后面的质数。
没有重复。 每个指数向量 \((a_1,\ldots,a_k)\) 对应唯一的一条递归路径。
因此，DFS 会把每个 admissible 数恰好生成一次，而不必扫描所有不超过 \(10^9\) 的偶数。
按照定义，\(M(n)\) 是使 \(n+m\) 成为素数的最小整数 \(m>1\)。每个 admissible 的 \(n\) 都是偶数，而大于 \(2\) 的素数必为奇数，因此 \(m\) 也必须是奇数。候选值恰好就是
$$m = 3,5,7,9,\ldots$$
代码按从小到大的顺序检查这些奇数，直到 \(n+m\) 为素数为止。
例如 \(16\) 是 admissible，因为它是 \(2\) 的幂。不能取 \(m=1\)，因为定义要求 \(m>1\)。于是
$$16+3 = 19,$$
它是素数，所以
$$M(16)=3.$$
再看 \(630 = 2\cdot 3^2\cdot 5\cdot 7\)，它的不同质因子是 \(2,3,5,7\)，因此也是 admissible。最开始几个奇数会得到
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
全都是合数，而
$$630+11=641$$
是素数，因此
$$M(630)=11.$$
题目要求的是 不同 的 \(M(n)\) 之和，而不是对所有 admissible \(n\) 逐个把 \(M(n)\) 累加。不同的 admissible 数可能给出相同的 pseudo-Fortunate 值，因此程序先把所有结果放进集合
$$\mathcal{M} = \{M(n) : n \text{ admissible},\ n < 10^9\}.$$
最后答案就是
$$\sum_{m \in \mathcal{M}} m.$$
如果不去重，求出的就是另一道题。
在生成完 admissible 数之后，真正反复昂贵的步骤是判断 \(n+m\) 是否为素数。代码使用 64 位范围内确定性的 Miller-Rabin 素性测试，因此每次判断在这个范围内都是精确的，同时又足够快，使得按奇数递增直接搜索成为可行方案。
实现用三个简单检查来验证自己：
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
前两个检查验证 pseudo-Fortunate 搜索本身。第三个检查把高效 DFS 枚举与小范围上的暴力 admissible 检测进行比较，这是对“生成完整且无重复”的强力确认。
prime_prefix() 提供一个固定的质数前缀列表。generate_admissible(...) 对指数选择做 DFS，把每个 admissible 乘积存入集合。对每个得到的 \(n\)，pseudo_fortunate(n) 依次测试 \(m=3,5,7,\ldots\)，直到 \(n+m\) 为素数。得到的 \(M(n)\) 被插入第二个集合，最后程序把这个集合求和。
设上界下 admissible 数的个数为 \(A\)，在找到 \(M(n)\) 前要尝试的奇数个数为 \(T(n)\)。总时间大致为
$$O\!\left(A + \sum_{n \in \text{admissible}} T(n)\cdot C_{\text{prime}}\right),$$
其中 \(C_{\text{prime}}\) 表示一次素性测试的代价。空间复杂度为 \(O(A + |\mathcal{M}|)\)，对应两个集合。关键优化在于只生成 admissible 数，而不是枚举所有不超过 \(10^9\) 的偶数。
Чётное число \(n\) называется допустимым, если оно либо является степенью \(2\), либо, что для чётных чисел эквивалентно, его различные простые делители образуют непрерывный префикс последовательности простых \(2,3,5,7,\ldots\). Для каждого допустимого \(n < 10^9\) величина \(M(n)\) определяется как наименьшее число \(m>1\), при котором \(n+m\) простое. Требуется просуммировать различные значения \(M(n)\).
Поскольку \(n\) чётно, первый простой множитель \(2\) обязан присутствовать. Если различные простые множители идут подряд, то любое допустимое число имеет вид
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
Частный случай «степень двойки» здесь просто соответствует \(k=1\). Значит, допустимые числа полностью задаются выбором префикса простых и положительных показателей для каждого простого в этом префиксе.
Это уже сильно ограничивает поиск. Произведение первых девяти простых равно
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
а с добавлением следующего простого получается
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
Следовательно, никакое допустимое число меньше \(10^9\) не может содержать \(29\) или более поздний простой как различный множитель. В коде используется немного более длинный фиксированный список простых, но рекурсия автоматически отсекает всё, что превышает лимит.
Рекурсивный генератор работает по упорядоченному списку простых \((2,3,5,7,\ldots)\). Предположим, что мы находимся на простом \(p_i\) и уже построили частичное произведение из более раннего префикса. Цикл многократно умножает его на \(p_i\):
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
пока произведение не превышает предел. Каждый раз, когда выбрана хотя бы одна копия \(p_i\), рекурсия может перейти к следующему простому \(p_{i+1}\).
Именно поэтому выполняются нужные свойства:
Положительные показатели. Если простой включён, его показатель не меньше \(1\).
Только непрерывный префикс. К \(p_{i+1}\) можно перейти только после выбора \(p_i\), поэтому поздние простые не могут появиться, если какой-то более ранний пропущен.
Без дубликатов. Каждый вектор показателей \((a_1,\ldots,a_k)\) соответствует единственному пути рекурсии.
Значит, DFS перечисляет каждое допустимое число ровно один раз и не требует перебора всех чётных чисел до \(10^9\).
По определению, \(M(n)\) — это наименьшее число \(m>1\), при котором \(n+m\) простое. Так как любое допустимое \(n\) чётно, а любой простой больше \(2\) нечётен, число \(m\) тоже должно быть нечётным. Поэтому кандидаты имеют вид
$$m = 3,5,7,9,\ldots$$
и код проверяет их по возрастанию, пока \(n+m\) не окажется простым.
Например, \(16\) допустимо как степень \(2\). Значение \(m=1\) запрещено, потому что в определении требуется \(m>1\). Тогда
$$16+3 = 19,$$
поэтому
$$M(16)=3.$$
Аналогично, \(630 = 2\cdot 3^2\cdot 5\cdot 7\) допустимо, потому что его различные простые множители — это \(2,3,5,7\). Первые нечётные проверки дают
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
все составные, а
$$630+11=641$$
уже простое, значит
$$M(630)=11.$$
Задача просит сумму различных значений \(M(n)\), а не сумму по всем допустимым \(n\). Разные допустимые числа могут давать одно и то же значение pseudo-Fortunate, поэтому реализация сначала помещает результаты в множество:
$$\mathcal{M} = \{M(n) : n \text{ допустимо},\ n < 10^9\}.$$
Итоговый ответ равен
$$\sum_{m \in \mathcal{M}} m.$$
Без удаления повторов решалась бы уже другая задача.
После генерации допустимых чисел основная повторяющаяся затратная операция — проверка, является ли \(n+m\) простым. Для этого код использует детерминированный тест Миллера-Рабина для 64-битных чисел. В этом диапазоне он точен и достаточно быстр, чтобы прямой перебор нечётных \(m\) был практически применим.
Реализация проверяет себя тремя простыми условиями:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
Первые два теста проверяют сам поиск pseudo-Fortunate. Третий сравнивает быструю DFS-генерацию с брутфорсной проверкой допустимости на меньшем пределе; это сильное подтверждение полноты генератора и отсутствия дубликатов.
prime_prefix() возвращает фиксированный начальный отрезок списка простых. generate_admissible(...) выполняет DFS по выбору показателей и кладёт каждое допустимое произведение в множество. Для каждого такого \(n\) функция pseudo_fortunate(n) проверяет \(m=3,5,7,\ldots\), пока \(n+m\) не станет простым. Значения \(M(n)\) попадают во второе множество, а затем суммируются.
Пусть \(A\) — число допустимых чисел ниже лимита, а \(T(n)\) — число нечётных кандидатов, которые нужно проверить до нахождения \(M(n)\). Тогда время работы примерно равно
$$O\!\left(A + \sum_{n \in \text{допустимые}} T(n)\cdot C_{\text{prime}}\right),$$
где \(C_{\text{prime}}\) — стоимость одной проверки простоты. Память равна \(O(A + |\mathcal{M}|)\) из-за двух множеств. Ключевой выигрыш достигается тем, что генерируются только допустимые числа, а не все чётные числа до \(10^9\).
يُسمّى العدد الزوجي \(n\) admissible إذا كان قوةً للعدد \(2\)، أو بصورة مكافئة في حالة الأعداد الزوجية إذا كانت عوامله الأولية المميزة تشكل بادئة متتالية من قائمة الأعداد الأولية \(2,3,5,7,\ldots\). ولكل \(n < 10^9\) من هذا النوع نعرّف \(M(n)\) بأنه أصغر عدد صحيح \(m>1\) يجعل \(n+m\) عددًا أوليًا. المطلوب هو جمع القيم المختلفة لـ \(M(n)\).
بما أن \(n\) زوجي، فلا بد أن يظهر العامل الأولي \(2\). وإذا كانت العوامل الأولية المميزة متتالية، فإن كل عدد admissible يكتب بالشكل
$$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$
أما الحالة الخاصة "قوة للعدد \(2\)" فهي ببساطة الحالة \(k=1\). إذن جميع الأعداد admissible توصف باختيار بادئة من الأعداد الأولية ثم اختيار أس موجب لكل أولي داخل تلك البادئة.
وهذا يقيّد فضاء البحث كثيرًا. فحاصل ضرب أول تسعة أعداد أولية هو
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$
لكن عند إضافة الأولي التالي نحصل على
$$223092870 \cdot 29 = 6469693230 > 10^9.$$
لذلك لا يمكن لأي عدد admissible أصغر من \(10^9\) أن يحتوي على \(29\) أو أي أولي بعده كعامل مميز. يستخدم الكود قائمة أولية ثابتة أطول قليلًا، لكن الاستدعاء الذاتي يقطع تلقائيًا كل فرع يتجاوز الحد.
يعمل المولد التكراري على قائمة الأعداد الأولية المرتبة \((2,3,5,7,\ldots)\). لنفترض أننا عند الأولي \(p_i\) ومعنا حاصل ضرب جزئي مبني من البادئة السابقة. تقوم الحلقة بالضرب المتكرر في \(p_i\):
$$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$$
ما دام الناتج لا يتجاوز الحد. وفي كل مرة نكون قد اخترنا نسخة واحدة على الأقل من \(p_i\)، يُسمح للاستدعاء الذاتي بالانتقال إلى الأولي التالي \(p_{i+1}\).
وهذا يضمن بالضبط ما نحتاجه:
أسس موجبة. إذا دخل أولي في العدد فأسه لا يقل عن \(1\).
بادئة متتالية فقط. لا يمكن الانتقال إلى \(p_{i+1}\) إلا بعد اختيار \(p_i\)، لذلك يستحيل ظهور أولي لاحق مع تخطي أولي سابق.
لا توجد تكرارات. كل متجه أسس \((a_1,\ldots,a_k)\) يقابل مسارًا تكراريًا واحدًا فقط.
إذن DFS يولد كل عدد admissible مرة واحدة بالضبط، من دون فحص جميع الأعداد الزوجية حتى \(10^9\).
بحسب التعريف، \(M(n)\) هو أصغر عدد \(m>1\) يجعل \(n+m\) أوليًا. وكل عدد admissible زوجي، وأي عدد أولي أكبر من \(2\) يكون فرديًا، لذلك يجب أن يكون \(m\) فرديًا أيضًا. ومن ثم تكون القيم المرشحة هي
$$m = 3,5,7,9,\ldots$$
ويجرّبها الكود بالترتيب حتى يصبح \(n+m\) أوليًا.
على سبيل المثال، العدد \(16\) admissible لأنه قوة للعدد \(2\). ولا يمكن استخدام \(m=1\) لأن التعريف يطلب \(m>1\). عندئذ
$$16+3 = 19,$$
وهو عدد أولي، لذلك
$$M(16)=3.$$
وبالمثل فإن \(630 = 2\cdot 3^2\cdot 5\cdot 7\) admissible لأن عوامله الأولية المميزة هي \(2,3,5,7\). التجارب الفردية الأولى تعطي
$$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$$
وكلها مركبة، بينما
$$630+11=641$$
عدد أولي، ومن ثم
$$M(630)=11.$$
المسألة تطلب مجموع القيم المختلفة لـ \(M(n)\)، لا مجموع \(M(n)\) على جميع الأعداد admissible. قد تعطي أعداد admissible مختلفة القيمة نفسها، لذلك يضع التنفيذ كل نتيجة أولًا في مجموعة:
$$\mathcal{M} = \{M(n) : n \text{ admissible},\ n < 10^9\}.$$
ثم تكون الإجابة النهائية
$$\sum_{m \in \mathcal{M}} m.$$
ومن دون حذف التكرارات سنكون قد حللنا مسألة مختلفة.
بعد توليد الأعداد admissible، تصبح العملية المكلفة المتكررة هي فحص ما إذا كان \(n+m\) أوليًا. يستخدم الكود اختبار Miller-Rabin الحتمي للأعداد ذات 64 بت، ولذلك يكون الفحص دقيقًا في هذا المجال وسريعًا في الوقت نفسه. وهذا ما يجعل البحث المباشر عبر الأعداد الفردية المتتالية عمليًا.
يتحقق التنفيذ من نفسه بثلاث نقاط بسيطة:
$$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$$
النقطتان الأوليان تتحققان من بحث pseudo-Fortunate نفسه. أما الثالثة فتقارن التوليد السريع بـ DFS مع اختبار brute-force للأعداد admissible على حد صغير، وهي مراجعة قوية تؤكد أن المولد كامل ولا ينتج تكرارات.
تُرجع الدالة prime_prefix() مقطعًا ثابتًا من بداية قائمة الأعداد الأولية. ثم تنفذ generate_admissible(...) بحث DFS على اختيارات الأسس وتضع كل حاصل ضرب admissible في مجموعة. ولكل \(n\) مخزن، تجرّب الدالة pseudo_fortunate(n) القيم \(m=3,5,7,\ldots\) حتى يصبح \(n+m\) أوليًا. ثم تُدرج هذه القيم \(M(n)\) في مجموعة ثانية ويجمعها البرنامج في النهاية.
إذا كان \(A\) هو عدد الأعداد admissible تحت الحد، وكان \(T(n)\) هو عدد المرشحات الفردية التي نختبرها قبل الوصول إلى \(M(n)\)، فإن الزمن الكلي يقارب
$$O\!\left(A + \sum_{n \in \text{admissible}} T(n)\cdot C_{\text{prime}}\right),$$
حيث تمثل \(C_{\text{prime}}\) كلفة اختبار أولية واحد. أما الذاكرة فهي \(O(A + |\mathcal{M}|)\) بسبب المجموعتين. والفائدة الحاسمة تأتي من توليد الأعداد admissible فقط بدل مسح جميع الأعداد الزوجية حتى \(10^9\).