We seek five distinct primes with the property that every unordered pair \(\{p,q\}\) stays prime after concatenation in both directions. If \(p=7\) and \(q=109\), for example, then both \(7109\) and \(1097\) must be prime. Among all such 5-element sets, the goal is to minimize the sum of the five primes.
The implementations search primes below a configurable limit, with \(10{,}000\) as the default for the Euler instance. A smaller benchmark is already known: \(\{3,7,109,673\}\) satisfies the same pairwise condition for four primes and has sum \(792\), so any correct full solution should at least reproduce that checkpoint.
Let \(\mathcal{P}\) be the candidate primes below the search limit after removing values that can never belong to a valid pair. Define a symmetric compatibility relation \(p \sim q\) when both concatenations are prime. Problem 60 then becomes a minimum-weight clique problem on an undirected graph whose vertex weight is the prime itself.
If \(d(q)\) denotes the number of decimal digits of \(q\), then
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
So an edge test is purely arithmetic: for a pair \(p,q\), compute \(\operatorname{concat}(p,q)\) and \(\operatorname{concat}(q,p)\), and ask whether both are prime. With the default limit \(10{,}000\), every candidate has at most four digits, so the largest concatenations stay below \(10^8\); the implementations nevertheless use a 64-bit primality test so that larger optional limits remain safe.
The search discards \(2\) and \(5\) completely, and this is a theorem, not a heuristic. If \(q\) is any other prime, then \(\operatorname{concat}(q,2)\) ends in \(2\) and is larger than \(2\), so it is composite. Likewise \(\operatorname{concat}(q,5)\) ends in \(5\) and is larger than \(5\), so it is composite. Since a valid pair requires primality in both directions, no set of size at least \(2\) can contain \(2\) or \(5\).
Build an undirected graph \(G\) with vertex set \(\mathcal{P}\), and join \(p\) and \(q\) by an edge exactly when \(p \sim q\). A valid set of five primes is then a 5-clique in \(G\): every two chosen vertices are adjacent because every required concatenation test succeeds.
The objective is not merely to find any 5-clique, but to minimize
$$w(C)=\sum_{p\in C} p.$$
All vertex weights are positive, so partial sums already provide useful information for pruning: once a partial choice is too large, no extension can improve it.
The implementations use depth-first search on partial cliques. A recursive state consists of a chosen set \(C\), a candidate list \(R\), and the current sum \(s(C)\). The key invariant is
$$\text{every } r\in R \text{ is larger than all primes in } C \text{ and is adjacent to every element of } C.$$
Because primes are processed in increasing order, each clique is generated exactly once. If the next chosen prime is \(v\in R\), the recursive call keeps only those later candidates that remain compatible with the enlarged clique:
$$R_v=\{u\in R:u>v \text{ and } u\sim x \text{ for all } x\in C\cup\{v\}\}.$$
Reaching \(\lvert C\rvert=5\) produces a valid solution, and its sum is compared against the best sum found so far.
Two pruning rules in the code are mathematically safe. First, if \(\lvert R\rvert < 5-\lvert C\rvert\), then there are not enough remaining vertices to finish a 5-clique, so the branch is impossible. Second, if \(s(C)+v\geq S_{\mathrm{best}}\) for the next candidate \(v\), then every continuation of that branch has sum at least \(s(C)+v\), hence at least the best sum already found. Because all primes are positive, the branch can be discarded immediately.
This is a branch-and-bound argument specialized to a weighted clique search with positive vertex weights and an increasing-order traversal.
The set
$$\{3,7,109,673\}$$
is a 4-clique. For instance, \(3\) and \(109\) work because \(3109\) and \(1093\) are prime, while \(7\) and \(673\) work because \(7673\) and \(6737\) are prime. The same holds for the remaining four unordered pairs, so every pair inside the set is compatible.
Its sum is
$$3+7+109+673=792.$$
The implementations use this fact as a checkpoint for the smaller task of finding the minimum-sum 4-clique below \(1000\). The full Euler problem has exactly the same structure, just one level deeper: extend the search from 4 compatible primes to 5.
The C++, Python, and Java implementations first sieve all primes up to the chosen limit and omit \(2\) and \(5\). Every concatenated number is then tested with a deterministic 64-bit Miller-Rabin routine, after first checking divisibility by a short list of small primes. That combination is fast for the Euler input and remains correct if the search limit is raised.
After the prime list is prepared, the implementation checks each unordered pair once. If both concatenations are prime, the pair is recorded in a symmetric compatibility matrix. For the default limit \(10{,}000\), there are \(1227\) retained primes, so this stage performs
$$\binom{1227}{2}=752151$$
pair tests, each consisting of two primality checks.
The search starts with an empty clique and the full sorted prime list. At each level it picks one candidate, adds its value to the running sum, and scans only later candidates. A later prime survives to the next recursive call exactly when it is compatible with every currently chosen prime, which preserves the clique invariant at all times.
When five primes have been chosen, the implementation updates the best sum. It does not need to store the full best set to answer the Euler question, because the required output is the minimum sum alone.
Before solving the full instance, the implementations optionally verify the known 4-prime checkpoint \(792\). This guards against errors in concatenation arithmetic, primality testing, and recursive clique construction. Once that test passes, the same search logic runs with target size \(5\) and the default prime limit.
Let \(P=\lvert\mathcal{P}\rvert\) be the number of retained primes and let \(T\) denote the cost of one primality test. Building the compatibility matrix costs \(O(P^2T)\) time and \(O(P^2)\) space, because every unordered pair is tested once and the result is stored in a full symmetric table.
The recursive search is output-sensitive: its exact cost depends on how sparse the compatibility graph is. In the densest conceivable case with target size \(5\), it can behave like \(O(P^5)\), but the actual graph is sparse and each recursive call sharply shrinks the candidate list. The extra search memory beyond the matrix is only the recursion stack and temporary candidate lists, so the dominating storage term remains the \(O(P^2)\) compatibility table.
Gesucht sind fünf verschiedene Primzahlen mit der Eigenschaft, dass für jedes ungeordnete Paar \(\{p,q\}\) beide Verkettungen wieder prim sind. Wenn etwa \(p=7\) und \(q=109\) ist, dann müssen sowohl \(7109\) als auch \(1097\) prim sein. Unter allen solchen 5-elementigen Mengen ist diejenige mit der kleinsten Summe zu finden.
Die Implementierungen durchsuchen Primzahlen unterhalb einer einstellbaren Schranke; für die Euler-Aufgabe ist \(10{,}000\) der Standardwert. Ein kleineres Vergleichsbeispiel ist bereits bekannt: \(\{3,7,109,673\}\) erfüllt dieselbe paarweise Bedingung für vier Primzahlen und hat Summe \(792\). Jede korrekte Gesamtlösung sollte diesen Checkpoint also mindestens reproduzieren.
Sei \(\mathcal{P}\) die Menge der Kandidatenprimzahlen unterhalb der Suchgrenze, nachdem Werte entfernt wurden, die niemals zu einem gültigen Paar gehören können. Definiere eine symmetrische Kompatibilitätsrelation \(p \sim q\), falls beide Verkettungen prim sind. Damit wird Problem 60 zu einem Minimum-Gewicht-Clique-Problem auf einem ungerichteten Graphen, dessen Knotengewicht einfach der Primzahlwert selbst ist.
Bezeichne \(d(q)\) als die Anzahl der Dezimalstellen von \(q\). Dann gilt
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
Ein Kantentest ist also rein arithmetisch: Für ein Paar \(p,q\) berechnet man \(\operatorname{concat}(p,q)\) und \(\operatorname{concat}(q,p)\) und prüft, ob beide Zahlen prim sind. Bei der Standardschranke \(10{,}000\) hat jeder Kandidat höchstens vier Stellen, daher bleiben die größten Verkettungen unter \(10^8\); trotzdem verwenden die Implementierungen einen 64-Bit-Primzahltest, damit auch größere optionale Schranken sicher behandelt werden.
Die Suche verwirft \(2\) und \(5\) vollständig, und das ist kein heuristischer Trick, sondern eine mathematische Folgerung. Ist \(q\) eine andere Primzahl, dann endet \(\operatorname{concat}(q,2)\) auf \(2\) und ist größer als \(2\), also zusammengesetzt. Ebenso endet \(\operatorname{concat}(q,5)\) auf \(5\) und ist größer als \(5\), also ebenfalls zusammengesetzt. Da ein gültiges Paar Primzahligkeit in beiden Richtungen verlangt, kann keine Menge der Größe mindestens \(2\) die \(2\) oder die \(5\) enthalten.
Man konstruiert einen ungerichteten Graphen \(G\) mit Knotenmenge \(\mathcal{P}\) und verbindet \(p\) und \(q\) genau dann durch eine Kante, wenn \(p \sim q\) gilt. Eine gültige Fünfermenge ist dann genau eine 5-Clique in \(G\): Jede zwei gewählten Knoten sind benachbart, weil jeder geforderte Verkettungstest erfolgreich ist.
Gesucht ist nicht irgendeine 5-Clique, sondern diejenige mit minimalem Gewicht
$$w(C)=\sum_{p\in C} p.$$
Da alle Knotengewichte positiv sind, liefern partielle Summen sofort nützliche Schranken: Sobald eine Teilmenge schon zu groß ist, kann keine Erweiterung mehr optimal sein.
Die Implementierungen verwenden eine Tiefensuche auf partiellen Cliquen. Ein rekursiver Zustand besteht aus einer bereits gewählten Menge \(C\), einer Kandidatenliste \(R\) und der aktuellen Summe \(s(C)\). Die zentrale Invariante lautet
$$\text{jedes } r\in R \text{ ist größer als alle Primzahlen in } C \text{ und zu jedem Element von } C \text{ benachbart.}$$
Weil die Primzahlen in aufsteigender Reihenfolge verarbeitet werden, wird jede Clique genau einmal erzeugt. Ist \(v\in R\) die nächste gewählte Primzahl, dann behält der rekursive Aufruf nur diejenigen späteren Kandidaten, die mit der vergrößerten Clique kompatibel bleiben:
$$R_v=\{u\in R:u>v \text{ und } u\sim x \text{ für alle } x\in C\cup\{v\}\}.$$
Sobald \(\lvert C\rvert=5\) erreicht ist, liegt eine gültige Lösung vor, deren Summe mit der bisher besten Summe verglichen wird.
Zwei Beschneidungsregeln im Code sind mathematisch sauber. Erstens: Falls \(\lvert R\rvert < 5-\lvert C\rvert\), gibt es nicht mehr genug verbleibende Knoten, um eine 5-Clique zu vervollständigen; der Zweig ist also unmöglich. Zweitens: Falls für den nächsten Kandidaten \(v\) schon \(s(C)+v\geq S_{\mathrm{best}}\) gilt, dann hat jede Fortsetzung dieses Zweigs mindestens die Summe \(s(C)+v\) und damit mindestens die beste bereits bekannte Summe. Wegen der Positivität aller Primzahlen kann der Zweig sofort verworfen werden.
Das ist ein Branch-and-Bound-Argument, zugeschnitten auf eine gewichtete Clique-Suche mit positiven Knotengewichten und aufsteigender Traversierung.
Die Menge
$$\{3,7,109,673\}$$
ist eine 4-Clique. Zum Beispiel funktionieren \(3\) und \(109\), weil \(3109\) und \(1093\) prim sind; ebenso funktionieren \(7\) und \(673\), weil \(7673\) und \(6737\) prim sind. Dasselbe gilt für die übrigen vier ungeordneten Paare, also ist jedes Paar innerhalb der Menge kompatibel.
Ihre Summe ist
$$3+7+109+673=792.$$
Die Implementierungen verwenden genau diese Tatsache als Checkpoint für die kleinere Aufgabe, die Minimum-Summen-4-Clique unterhalb von \(1000\) zu finden. Die volle Euler-Aufgabe hat exakt dieselbe Struktur, nur eine Ebene tiefer: Aus vier kompatiblen Primzahlen müssen fünf werden.
Die C++-, Python- und Java-Implementierungen sieben zunächst alle Primzahlen bis zur gewählten Schranke und lassen \(2\) sowie \(5\) aus. Jede verkettete Zahl wird danach mit einem deterministischen 64-Bit-Miller-Rabin-Test geprüft, dem eine schnelle Teilbarkeitsprüfung durch einige kleine Primzahlen vorausgeht. Diese Kombination ist für die Euler-Eingabe schnell und bleibt auch bei größeren Suchgrenzen korrekt.
Nach der Erzeugung der Primzahlliste prüft die Implementierung jedes ungeordnete Paar genau einmal. Wenn beide Verkettungen prim sind, wird das Paar in einer symmetrischen Kompatibilitätsmatrix markiert. Bei der Standardschranke \(10{,}000\) bleiben \(1227\) Primzahlen übrig, daher umfasst diese Phase
$$\binom{1227}{2}=752151$$
Paarprüfungen, und jede davon enthält zwei Primzahltests.
Die Suche beginnt mit einer leeren Clique und der vollständig sortierten Primzahlliste. Auf jeder Ebene wird ein Kandidat gewählt, zu der laufenden Summe addiert und anschließend werden nur spätere Kandidaten betrachtet. Eine spätere Primzahl überlebt genau dann für den nächsten rekursiven Aufruf, wenn sie mit allen aktuell gewählten Primzahlen kompatibel ist; dadurch bleibt die Clique-Invariante jederzeit erhalten.
Sobald fünf Primzahlen gewählt wurden, aktualisiert die Implementierung die beste Summe. Die vollständige beste Menge muss nicht gespeichert werden, denn für die Project-Euler-Aufgabe ist nur die minimale Summe gefragt.
Bevor die volle Instanz gelöst wird, überprüfen die Implementierungen optional den bekannten Vierer-Checkpoint \(792\). Das schützt vor Fehlern in der Verkettungsarithmetik, im Primzahltest und im rekursiven Clique-Aufbau. Sobald dieser Test besteht, läuft dieselbe Suchlogik mit Zielgröße \(5\) und der Standardschranke weiter.
Sei \(P=\lvert\mathcal{P}\rvert\) die Anzahl der verbleibenden Primzahlen und \(T\) die Kosten eines einzelnen Primzahltests. Der Aufbau der Kompatibilitätsmatrix kostet \(O(P^2T)\) Zeit und \(O(P^2)\) Speicher, weil jedes ungeordnete Paar genau einmal getestet und das Ergebnis in einer vollständigen symmetrischen Tabelle abgelegt wird.
Die rekursive Suche ist ausgabeabhängig: Ihre genaue Laufzeit hängt davon ab, wie dünn der Kompatibilitätsgraph ist. Im dichtesten denkbaren Fall bei Zielgröße \(5\) kann sie sich wie \(O(P^5)\) verhalten, aber der tatsächliche Graph ist spärlich, und jede Rekursion verkleinert die Kandidatenliste deutlich. Der zusätzliche Suchspeicher jenseits der Matrix besteht nur aus Rekursionsstapel und temporären Kandidatenlisten, sodass der dominante Speicherturm weiterhin die \(O(P^2)\)-Kompatibilitätstabelle ist.
Aranan şey, her \(\{p,q\}\) çifti için iki yöndeki birleştirme de asal kalan beş farklı asal sayıdır. Örneğin \(p=7\) ve \(q=109\) ise hem \(7109\) hem de \(1097\) asal olmak zorundadır. Bu özelliği sağlayan tüm 5 elemanlı kümeler arasında toplamı en küçük olan küme istenir.
Uygulamalar, üst sınırı ayarlanabilir bir asal listesi üzerinde arama yapar; Euler örneği için varsayılan sınır \(10{,}000\)'dir. Daha küçük bir eşik için bilinen bir kontrol de vardır: \(\{3,7,109,673\}\) aynı koşulu dört asal için sağlar ve toplamı \(792\)'dir. Dolayısıyla tam çözümün en azından bu ara testi doğru üretmesi gerekir.
\(\mathcal{P}\), arama sınırının altındaki ve hiçbir geçerli çiftte yer alamayacak değerler çıkarıldıktan sonra kalan aday asallar kümesi olsun. Her iki birleştirme de asal olduğunda \(p \sim q\) diye simetrik bir uyumluluk ilişkisi tanımlayalım. Böylece Problem 60, düğüm ağırlığı doğrudan asalın kendisi olan bir yönsüz graf üzerinde minimum ağırlıklı klik problemine dönüşür.
\(d(q)\), \(q\) sayısının onluk basamak sayısı olsun. O zaman
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
Dolayısıyla bir kenar testi tamamen aritmetiktir: bir \(p,q\) çifti için \(\operatorname{concat}(p,q)\) ve \(\operatorname{concat}(q,p)\) hesaplanır, sonra ikisinin de asal olup olmadığına bakılır. Varsayılan sınır \(10{,}000\) iken her aday en fazla dört basamaklıdır; bu yüzden en büyük birleştirmeler \(10^8\)'in altında kalır. Yine de uygulamalar, sınır yükseltilse bile güvenli kalmak için 64 bitlik bir asallık testi kullanır.
Arama \(2\) ile \(5\)'i baştan eler; bu sezgisel bir kestirme değil, doğrudan bir matematik sonucudur. \(q\) başka herhangi bir asal olsun. \(\operatorname{concat}(q,2)\) sayısı \(2\) ile biter ve \(2\)'den büyüktür; dolayısıyla bileşiktir. Aynı şekilde \(\operatorname{concat}(q,5)\) sayısı \(5\) ile biter ve \(5\)'ten büyüktür; o da bileşiktir. Geçerli bir çift iki yönde de asallık istediği için, en az iki elemanlı hiçbir küme \(2\) veya \(5\) içeremez.
Düğüm kümesi \(\mathcal{P}\) olan yönsüz bir \(G\) grafiği kurulur ve \(p \sim q\) olduğunda \(p\) ile \(q\) arasında kenar konur. Böylece geçerli beşli asal küme, \(G\) içinde bir 5-kliktir: seçilen her iki düğüm komşudur, çünkü gerekli tüm birleştirme testleri geçmektedir.
Amaç yalnızca herhangi bir 5-klik bulmak değil,
$$w(C)=\sum_{p\in C} p$$
toplamını en aza indirmektir. Tüm düğüm ağırlıkları pozitif olduğu için kısmi toplamlar budama için hemen işe yarar; bir dal fazla büyüdüğünde sonraki eklemeler onu kurtaramaz.
Uygulamalar kısmi klikler üzerinde derinlik öncelikli arama kullanır. Bir özyineli durum, seçilmiş küme \(C\), aday listesi \(R\) ve mevcut toplam \(s(C)\) ile tanımlanır. Temel invariant şudur:
$$\text{\(R\) içindeki her } r,\ C \text{ içindeki tüm asallardan büyüktür ve } C \text{ içindeki her elemanla komşudur.}$$
Asallar artan sırada işlendiği için her klik tam olarak bir kez üretilir. Sıradaki seçim \(v\in R\) olduğunda, sonraki özyineli çağrı yalnızca büyütülmüş klikle uyumlu kalan daha sonraki adayları tutar:
$$R_v=\{u\in R:u>v \text{ ve } u\sim x \text{ tüm } x\in C\cup\{v\} \text{ için}\}.$$
\(\lvert C\rvert=5\) olduğunda geçerli bir çözüm elde edilir ve bu çözümün toplamı şimdiye kadarki en iyi değerle karşılaştırılır.
Koddaki iki budama kuralı matematiksel olarak güvenlidir. Birincisi, \(\lvert R\rvert < 5-\lvert C\rvert\) ise 5-kliki tamamlamak için yeterli aday kalmamıştır; bu dal imkansızdır. İkincisi, sıradaki aday \(v\) için \(s(C)+v\geq S_{\mathrm{best}}\) ise bu daldaki her devamın toplamı en az \(s(C)+v\) olacaktır; yani zaten bulunan en iyi toplamdan daha iyi olamaz. Tüm asallar pozitif olduğundan dal hemen kesilebilir.
Bu, pozitif düğüm ağırlıklı ve artan sıra ile gezilen bir klik aramasına uygulanmış klasik bir branch-and-bound argümanıdır.
Şu küme
$$\{3,7,109,673\}$$
bir 4-kliktir. Örneğin \(3\) ile \(109\) uyumludur; çünkü \(3109\) ve \(1093\) asaldır. Aynı şekilde \(7\) ile \(673\) de uyumludur; çünkü \(7673\) ve \(6737\) asaldır. Geri kalan dört sırasız çift için de aynı durum geçerlidir; dolayısıyla bu kümenin içindeki her çift uyumludur.
Toplamı
$$3+7+109+673=792$$
olur. Uygulamalar tam da bu bilgiyi, \(1000\)'in altındaki minimum toplamlı 4-kliki bulma görevi için kontrol testi olarak kullanır. Tam Euler problemi aynı yapının bir seviye daha derin halidir: dört uyumlu asaldan beş uyumlu asala çıkılır.
C++, Python ve Java uygulamaları önce seçilen sınıra kadar tüm asalları elekten geçirir ve \(2\) ile \(5\)'i dışarıda bırakır. Sonra her birleştirilmiş sayı, önce küçük birkaç asala bölünebilirlik açısından hızlıca elendikten sonra, deterministik 64 bit Miller-Rabin testi ile denetlenir. Bu birleşim Euler girdisi için hızlıdır ve arama sınırı büyütülürse de doğruluğunu korur.
Asal listesi hazırlandıktan sonra uygulama her sırasız çifti tam bir kez inceler. İki yöndeki birleştirme de asalsa, o çift simetrik bir uyumluluk matrisi içine işlenir. Varsayılan \(10{,}000\) sınırında elde \(1227\) aday asal kalır; dolayısıyla bu aşama
$$\binom{1227}{2}=752151$$
çift testi yapar ve her test iki asallık denetimi içerir.
Arama boş bir klik ve sıralı tam asal listesi ile başlar. Her seviyede bir aday seçilir, değeri çalışan toplama eklenir ve yalnızca daha sonraki adaylar taranır. Daha sonraki bir asal, ancak o ana kadar seçilmiş tüm asallarla uyumluysa bir sonraki özyineli çağrıya geçer; böylece klik invariantı her aşamada korunur.
Beş asal seçildiğinde uygulama en iyi toplamı günceller. Project Euler sorusunun istediği çıktı yalnızca minimum toplam olduğu için, en iyi kümenin tamamını ayrıca saklamak zorunda değildir.
Tam örnek çözülmeden önce uygulamalar isteğe bağlı olarak bilinen \(792\) kontrolünü doğrular. Bu, birleştirme aritmetiğinde, asallık testinde ve özyineli klik kurulumunda oluşabilecek hataları yakalar. Bu test geçtikten sonra aynı arama mantığı hedef boyut \(5\) ile ve varsayılan asal sınırıyla çalıştırılır.
\(P=\lvert\mathcal{P}\rvert\) kalan aday asal sayısı, \(T\) de tek bir asallık testinin maliyeti olsun. Uyumluluk matrisini kurmak \(O(P^2T)\) zaman ve \(O(P^2)\) bellek gerektirir; çünkü her sırasız çift bir kez sınanır ve sonuç tam simetrik bir tabloda saklanır.
Özyineli arama çıktıya duyarlıdır; tam maliyeti uyumluluk grafının ne kadar seyrek olduğuna bağlıdır. Hedef boyut \(5\) için teorik olarak en yoğun durumda \(O(P^5)\) davranışı görülebilir, ancak gerçek grafik seyrektir ve her özyineli çağrı aday listesini ciddi biçimde küçültür. Matris dışındaki ek bellek yalnızca çağrı yığını ve geçici aday listeleridir; bu yüzden baskın depolama terimi yine \(O(P^2)\) uyumluluk matrisidir.
Se buscan cinco números primos distintos con la propiedad de que, para cada par no ordenado \(\{p,q\}\), las dos concatenaciones sigan siendo primas. Si \(p=7\) y \(q=109\), por ejemplo, entonces tanto \(7109\) como \(1097\) deben ser primos. Entre todos los conjuntos de 5 elementos con esa propiedad, hay que minimizar la suma total.
Las implementaciones trabajan sobre los primos menores que un límite configurable; para la instancia de Euler el valor por defecto es \(10{,}000\). También existe un punto de control más pequeño: \(\{3,7,109,673\}\) cumple la misma condición por pares para cuatro primos y suma \(792\). Cualquier solución correcta del caso completo debería, como mínimo, reproducir ese resultado intermedio.
Sea \(\mathcal{P}\) el conjunto de primos candidatos por debajo del límite de búsqueda, una vez eliminados los valores que nunca pueden pertenecer a un par válido. Definimos una relación simétrica de compatibilidad \(p \sim q\) cuando ambas concatenaciones son primas. Así, el Problema 60 se convierte en un problema de clique de peso mínimo sobre un grafo no dirigido cuyo peso de vértice es simplemente el propio primo.
Si \(d(q)\) es el número de cifras decimales de \(q\), entonces
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
Por tanto, comprobar una arista es un asunto puramente aritmético: para un par \(p,q\), se calculan \(\operatorname{concat}(p,q)\) y \(\operatorname{concat}(q,p)\), y luego se verifica si ambas cantidades son primas. Con el límite por defecto \(10{,}000\), todos los candidatos tienen a lo sumo cuatro cifras, así que las concatenaciones más grandes permanecen por debajo de \(10^8\); aun así, las implementaciones utilizan una prueba de primalidad de 64 bits para seguir siendo correctas si el límite se amplía.
La búsqueda descarta por completo \(2\) y \(5\), y eso no es una heurística sino una consecuencia matemática. Si \(q\) es cualquier otro primo, entonces \(\operatorname{concat}(q,2)\) termina en \(2\) y es mayor que \(2\), luego es compuesto. Del mismo modo, \(\operatorname{concat}(q,5)\) termina en \(5\) y es mayor que \(5\), luego también es compuesto. Como un par válido exige primalidad en ambas direcciones, ningún conjunto de tamaño al menos \(2\) puede contener \(2\) ni \(5\).
Se construye un grafo no dirigido \(G\) con conjunto de vértices \(\mathcal{P}\), y se unen \(p\) y \(q\) exactamente cuando \(p \sim q\). Entonces un conjunto válido de cinco primos es una 5-clique en \(G\): cada dos vértices elegidos son adyacentes porque todos los tests de concatenación requeridos se cumplen.
El objetivo no es encontrar cualquier 5-clique, sino minimizar
$$w(C)=\sum_{p\in C} p.$$
Como todos los pesos de vértice son positivos, las sumas parciales ya dan información útil para podar: si una elección parcial ya es demasiado grande, ninguna ampliación posterior podrá mejorarla.
Las implementaciones usan búsqueda en profundidad sobre cliques parciales. Un estado recursivo está formado por un conjunto elegido \(C\), una lista de candidatos \(R\) y la suma actual \(s(C)\). El invariante clave es
$$\text{todo } r\in R \text{ es mayor que todos los primos de } C \text{ y es adyacente a cada elemento de } C.$$
Como los primos se recorren en orden creciente, cada clique se genera exactamente una vez. Si el siguiente primo elegido es \(v\in R\), la llamada recursiva conserva solo los candidatos posteriores que siguen siendo compatibles con la clique ampliada:
$$R_v=\{u\in R:u>v \text{ y } u\sim x \text{ para todo } x\in C\cup\{v\}\}.$$
Cuando \(\lvert C\rvert=5\), ya se ha construido una solución válida y su suma se compara con la mejor suma encontrada hasta ese momento.
Las dos reglas de poda del código son matemáticamente seguras. Primero, si \(\lvert R\rvert < 5-\lvert C\rvert\), ya no quedan suficientes vértices para completar una 5-clique, así que esa rama es imposible. Segundo, si para el siguiente candidato \(v\) se cumple \(s(C)+v\geq S_{\mathrm{best}}\), entonces cualquier continuación de esa rama tendrá suma al menos \(s(C)+v\), y por tanto no podrá mejorar la mejor suma conocida. Como todos los primos son positivos, la rama puede descartarse de inmediato.
Se trata de un argumento clásico de branch and bound aplicado a una búsqueda de cliques con pesos positivos y recorrido en orden creciente.
El conjunto
$$\{3,7,109,673\}$$
es una 4-clique. Por ejemplo, \(3\) y \(109\) funcionan porque \(3109\) y \(1093\) son primos, mientras que \(7\) y \(673\) funcionan porque \(7673\) y \(6737\) son primos. Lo mismo ocurre con los otros cuatro pares no ordenados, así que cada par dentro del conjunto es compatible.
Su suma es
$$3+7+109+673=792.$$
Las implementaciones usan este hecho como punto de control para la tarea más pequeña de hallar la 4-clique de suma mínima por debajo de \(1000\). El problema completo de Euler tiene exactamente la misma estructura, solo un nivel más profundo: pasar de cuatro primos compatibles a cinco.
Las implementaciones en C++, Python y Java primero generan mediante criba todos los primos hasta el límite elegido y omiten \(2\) y \(5\). Después, cada número concatenado se comprueba con un test determinista de Miller-Rabin para 64 bits, precedido por verificaciones rápidas de divisibilidad por varios primos pequeños. Esa combinación es rápida para la entrada de Euler y sigue siendo correcta si se aumenta el límite de búsqueda.
Una vez preparada la lista de primos, la implementación examina cada par no ordenado exactamente una vez. Si ambas concatenaciones son primas, el par se marca en una matriz de compatibilidad simétrica. Con el límite por defecto \(10{,}000\) quedan \(1227\) primos candidatos, de modo que esta fase realiza
$$\binom{1227}{2}=752151$$
pruebas de pares, y cada una contiene dos tests de primalidad.
La búsqueda comienza con una clique vacía y la lista completa de primos ordenados. En cada nivel toma un candidato, añade su valor a la suma acumulada y examina solo candidatos posteriores. Un primo posterior sobrevive a la siguiente llamada recursiva exactamente cuando es compatible con todos los primos ya elegidos, lo que mantiene el invariante de clique en todo momento.
Cuando ya se han elegido cinco primos, la implementación actualiza la mejor suma. No necesita almacenar el mejor conjunto completo para responder a la pregunta de Euler, porque la salida requerida es únicamente la suma mínima.
Antes de resolver la instancia completa, las implementaciones verifican opcionalmente el control conocido \(792\). Eso ayuda a detectar errores en la aritmética de concatenación, en el test de primalidad o en la construcción recursiva de cliques. Una vez superado ese control, la misma lógica de búsqueda se ejecuta con tamaño objetivo \(5\) y el límite de primos por defecto.
Sea \(P=\lvert\mathcal{P}\rvert\) el número de primos candidatos retenidos, y sea \(T\) el coste de un único test de primalidad. Construir la matriz de compatibilidad cuesta \(O(P^2T)\) tiempo y \(O(P^2)\) memoria, porque cada par no ordenado se prueba una vez y el resultado se guarda en una tabla simétrica completa.
La búsqueda recursiva depende de la salida: su coste exacto varía según la dispersión del grafo de compatibilidad. En el caso más denso imaginable, con tamaño objetivo \(5\), puede comportarse como \(O(P^5)\), pero el grafo real es disperso y cada llamada recursiva reduce mucho la lista de candidatos. La memoria adicional, aparte de la matriz, se limita a la pila recursiva y a listas temporales de candidatos, así que el término dominante sigue siendo la tabla de compatibilidad \(O(P^2)\).
目标是找到五个互不相同的素数，使得对任意一个无序对 \(\{p,q\}\)，把它们按两个方向拼接以后得到的数都仍然是素数。比如 \(p=7\)、\(q=109\) 时，既要 \(7109\) 是素数，也要 \(1097\) 是素数。在所有满足条件的五元集合中，我们要求它们的和最小。
实现采用一个可调的素数搜索上界；对 Project Euler 这一题，默认上界是 \(10{,}000\)。还有一个较小的已知校验点：\(\{3,7,109,673\}\) 对四个素数已经满足完全相同的两两条件，而且它们的和是 \(792\)。因此，任何正确的完整实现至少都应该先复现这个中间结果。
设 \(\mathcal{P}\) 是搜索上界以内、并且去掉那些不可能出现在有效集合中的数之后得到的候选素数集合。当且仅当两个方向的拼接都为素数时，定义对称关系 \(p \sim q\)。这样一来，Problem 60 就被改写成一个无向图上的最小权 clique 问题，其中每个顶点的权重就是它本身对应的素数值。
记 \(d(q)\) 为 \(q\) 的十进制位数，则
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
因此，一条边是否存在完全可以用算术来判定：给定一对 \(p,q\)，分别计算 \(\operatorname{concat}(p,q)\) 与 \(\operatorname{concat}(q,p)\)，再检查这两个数是否都为素数。默认上界 \(10{,}000\) 下，所有候选数最多只有四位，所以最大的拼接结果仍然小于 \(10^8\)；不过实现仍然采用 64 位范围内的素性测试，这样即使把搜索上界调大，算法也依然成立。
搜索过程一开始就完全跳过 \(2\) 和 \(5\)，这不是经验性剪枝，而是严格的数学结论。设 \(q\) 是任意其他素数，那么 \(\operatorname{concat}(q,2)\) 的末位是 \(2\)，并且它大于 \(2\)，所以一定是合数。同理，\(\operatorname{concat}(q,5)\) 的末位是 \(5\)，并且它大于 \(5\)，因此也一定是合数。由于题目要求一个有效的素数对在两个方向上的拼接都必须为素数，所以任何大小至少为 \(2\) 的有效集合都不可能包含 \(2\) 或 \(5\)。
构造一个无向图 \(G\)，其顶点集合为 \(\mathcal{P}\)。当且仅当 \(p \sim q\) 时，在 \(p\) 与 \(q\) 之间连一条边。于是，一个有效的五素数组合就等价于图 \(G\) 中的一个 5-团：任意两个被选中的顶点都相邻，也就是任意两个被选中的素数在两个方向上的拼接都通过素性检验。
我们不仅要找任意一个 5-团，还要使总权重
$$w(C)=\sum_{p\in C} p$$
最小。因为所有顶点权重都是正数，所以部分和本身就能提供有效的剪枝信息：一旦当前选择的和已经太大，后面再加入更多正数只会更差，不可能反超当前最好答案。
实现使用的是对部分团进行深度优先搜索。一个递归状态由已选集合 \(C\)、候选列表 \(R\) 以及当前和 \(s(C)\) 组成。核心不变量是
$$\text{\(R\) 中每个 } r \text{ 都比 } C \text{ 中所有素数大，而且与 } C \text{ 中每个元素都相邻。}$$
由于素数按递增顺序处理，每个 clique 只会被生成一次，不会因为选取顺序不同而重复枚举。若本层选择的下一个素数是 \(v\in R\)，那么下一层递归只保留那些仍然与扩展后团兼容的更大候选：
$$R_v=\{u\in R:u>v \text{ 且 } u\sim x \text{ 对所有 } x\in C\cup\{v\} \text{ 都成立}\}.$$
一旦达到 \(\lvert C\rvert=5\)，就构造出了一个合法答案，其总和随后与当前已知最优值比较。
代码中的两条剪枝规则都可以直接证明。第一条是：如果 \(\lvert R\rvert < 5-\lvert C\rvert\)，那么剩余候选数量已经不足以把当前部分团补成一个 5-团，这条分支必然失败。第二条是：若下一个候选 \(v\) 已满足 \(s(C)+v\geq S_{\mathrm{best}}\)，则该分支上的任何后续扩展总和都至少是 \(s(C)+v\)，因而不可能优于当前最好答案。因为加入的都是正素数，这个结论是立即成立的。
本质上，这就是针对正权团搜索的一种 branch-and-bound 论证，并且配合递增顺序枚举，使得搜索树既不重复，也可以较早剪掉明显无望的分支。
集合
$$\{3,7,109,673\}$$
就是一个 4-团。例如 \(3\) 与 \(109\) 兼容，因为 \(3109\) 与 \(1093\) 都是素数；同样，\(7\) 与 \(673\) 兼容，因为 \(7673\) 与 \(6737\) 都是素数。其余四个无序对也都满足相同性质，所以这个集合内部任意两点之间都有边。
它的和为
$$3+7+109+673=792.$$
实现正是把这一事实当作较小规模任务的校验：在上界 \(1000\) 内寻找最小和的 4-团时，答案必须是 \(792\)。完整的 Euler 问题结构完全相同，只是把目标从四个互相兼容的素数再推进到五个。
C++、Python 和 Java 三个实现都会先用筛法生成不超过给定上界的所有素数，并显式略过 \(2\) 与 \(5\)。随后，对每一个拼接得到的数，先用若干个小素数做快速整除筛查，再用确定性的 64 位 Miller-Rabin 测试做最终判断。对于本题默认参数，这样做已经足够快；而当搜索上界被调大时，这种做法仍然保持正确。
有了素数列表以后，实现会对每个无序对恰好检查一次。若两个方向的拼接都为素数，就在一个对称的兼容性矩阵中把这对素数标记为相邻。默认上界 \(10{,}000\) 时，共保留 \(1227\) 个候选素数，因此这一阶段要处理
$$\binom{1227}{2}=752151$$
个素数对，而每个素数对都对应两次素性测试。
搜索从空团和完整的有序素数列表开始。每进入一层，就选取一个候选素数，把它加入当前和，并且只继续考察它后面的候选。某个更大的素数只有在与当前已经选中的所有素数都兼容时，才会进入下一层递归，这样 clique 的不变量始终成立。
当已经选到五个素数时，实现就用它们的和更新当前最优值。由于题目最终只要求最小和，而不是显式输出那五个素数，因此程序无需额外保存完整的最优集合。
在求解完整实例之前，三个实现都可以先验证已知的四素数校验值 \(792\)。这一步能够帮助发现拼接公式、素性判断或递归构团过程中的错误。校验通过后，同一套搜索逻辑就会以目标大小 \(5\) 和默认上界继续运行。
设 \(P=\lvert\mathcal{P}\rvert\) 为保留下来的候选素数个数，\(T\) 为一次素性测试的代价。构造兼容性矩阵需要 \(O(P^2T)\) 时间和 \(O(P^2)\) 空间，因为每个无序对只测试一次，而结果要存进完整的对称表中。
递归搜索的精确开销取决于兼容图到底有多稀疏，因此它更适合用输出敏感的角度来理解。若把目标大小固定为 \(5\)，在极端稠密的最坏情况下，搜索行为可以接近 \(O(P^5)\)；但真实图非常稀疏，而且每一次递归都会显著缩小候选列表。除兼容性矩阵外，额外空间主要只是递归栈和临时候选列表，所以主导存储项仍然是 \(O(P^2)\) 的矩阵。
Нужно найти пять различных простых чисел с таким свойством: для каждой неупорядоченной пары \(\{p,q\}\) оба числа, полученные конкатенацией в двух направлениях, тоже должны быть простыми. Если \(p=7\) и \(q=109\), то простыми обязаны быть и \(7109\), и \(1097\). Среди всех таких 5-элементных наборов требуется минимизировать сумму.
Реализации перебирают простые числа ниже настраиваемой границы; для задачи Euler по умолчанию берется \(10{,}000\). Есть и меньшая контрольная точка: \(\{3,7,109,673\}\) удовлетворяет тому же попарному условию для четырех простых чисел и имеет сумму \(792\). Значит, любая корректная полная программа как минимум должна воспроизводить этот промежуточный результат.
Обозначим через \(\mathcal{P}\) множество кандидатных простых чисел ниже поисковой границы после удаления значений, которые заведомо не могут входить в допустимую пару. Введем симметричное отношение совместимости \(p \sim q\), если обе конкатенации просты. Тогда задача 60 превращается в задачу о клике минимального веса в неориентированном графе, где вес вершины равен самому простому числу.
Пусть \(d(q)\) означает число десятичных цифр в \(q\). Тогда
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
Значит, проверка ребра полностью арифметическая: для пары \(p,q\) вычисляются \(\operatorname{concat}(p,q)\) и \(\operatorname{concat}(q,p)\), после чего проверяется простота обеих величин. При стандартной границе \(10{,}000\) каждый кандидат имеет не более четырех цифр, поэтому максимальные конкатенации остаются ниже \(10^8\); тем не менее реализации используют 64-битный тест простоты, чтобы корректность сохранялась и при увеличении предела поиска.
Числа \(2\) и \(5\) исключаются из поиска полностью, и это не эвристика, а строгий вывод. Пусть \(q\) — любое другое простое число. Тогда \(\operatorname{concat}(q,2)\) оканчивается на \(2\) и больше \(2\), следовательно, оно составное. Точно так же \(\operatorname{concat}(q,5)\) оканчивается на \(5\) и больше \(5\), значит, тоже составное. Поскольку допустимая пара требует простоты в обоих направлениях, ни один набор размера хотя бы \(2\) не может содержать \(2\) или \(5\).
Строится неориентированный граф \(G\) с множеством вершин \(\mathcal{P}\), где вершины \(p\) и \(q\) соединяются ребром тогда и только тогда, когда выполнено \(p \sim q\). Тогда допустимый набор из пяти простых чисел — это просто 5-клика в \(G\): любые две выбранные вершины смежны, потому что все требуемые конкатенации проходят проверку на простоту.
Нужно найти не просто любую 5-клику, а минимизировать
$$w(C)=\sum_{p\in C} p.$$
Все веса вершин положительны, поэтому частичные суммы сразу дают полезное ограничение для отсечения: если текущий частичный выбор уже слишком велик, дальнейшее расширение не сможет сделать его оптимальным.
Реализации используют поиск в глубину по частичным кликам. Рекурсивное состояние состоит из выбранного множества \(C\), списка кандидатов \(R\) и текущей суммы \(s(C)\). Ключевой инвариант имеет вид
$$\text{каждый } r\in R \text{ больше всех простых чисел в } C \text{ и смежен с каждым элементом } C.$$
Поскольку простые числа рассматриваются в возрастающем порядке, каждая клика порождается ровно один раз. Если следующим выбранным простым является \(v\in R\), то рекурсивный вызов сохраняет только те более поздние кандидаты, которые остаются совместимыми с расширенной кликой:
$$R_v=\{u\in R:u>v \text{ и } u\sim x \text{ для всех } x\in C\cup\{v\}\}.$$
Когда достигается \(\lvert C\rvert=5\), построено допустимое решение, и его сумма сравнивается с лучшей найденной до этого.
Две правила отсечения в коде математически безупречны. Во-первых, если \(\lvert R\rvert < 5-\lvert C\rvert\), то оставшихся вершин недостаточно, чтобы достроить 5-клику, значит ветвь невозможна. Во-вторых, если для следующего кандидата \(v\) уже выполняется \(s(C)+v\geq S_{\mathrm{best}}\), то любое продолжение этой ветви имеет сумму не меньше \(s(C)+v\), а следовательно, не сможет улучшить лучший уже найденный ответ. Так как все простые числа положительны, ветвь можно немедленно отбросить.
Это типичный аргумент branch and bound, адаптированный к поиску взвешенной клики с положительными весами вершин и обходом в возрастающем порядке.
Множество
$$\{3,7,109,673\}$$
образует 4-клику. Например, \(3\) и \(109\) совместимы, потому что числа \(3109\) и \(1093\) просты; аналогично, \(7\) и \(673\) совместимы, потому что просты \(7673\) и \(6737\). То же верно и для остальных четырех неупорядоченных пар, так что внутри множества каждая пара соединена ребром.
Сумма равна
$$3+7+109+673=792.$$
Именно этот факт используется в реализациях как проверка для меньшей задачи: минимальная по сумме 4-клика ниже \(1000\) должна давать \(792\). Полная задача Euler имеет ту же структуру, только на один уровень глубже: нужно перейти от четырех совместимых простых к пяти.
Реализации на C++, Python и Java сначала просеивают все простые числа до выбранной границы и исключают \(2\) и \(5\). Затем каждое число, полученное конкатенацией, сначала быстро проверяется на делимость несколькими малыми простыми, а затем проходит детерминированный тест Миллера-Рабина для 64-битных чисел. Для входа Euler такая схема быстра, и при увеличении поискового предела она сохраняет корректность.
После подготовки списка простых реализация рассматривает каждую неупорядоченную пару ровно один раз. Если обе конкатенации просты, пара помечается в симметричной матрице совместимости. При стандартной границе \(10{,}000\) остается \(1227\) кандидатных простых, поэтому на этом этапе выполняется
$$\binom{1227}{2}=752151$$
проверка пар, и каждая содержит два теста простоты.
Поиск начинается с пустой клики и полного отсортированного списка простых. На каждом уровне выбирается один кандидат, его значение добавляется к текущей сумме, а затем просматриваются только более поздние кандидаты. Более позднее простое число проходит в следующий рекурсивный вызов только тогда, когда оно совместимо со всеми уже выбранными простыми, так что инвариант клики сохраняется на каждом шаге.
Когда выбраны пять простых чисел, реализация обновляет лучшую сумму. Хранить полностью лучший набор не требуется, потому что в задаче Euler нужен только минимальный суммарный ответ.
Перед решением полной версии реализации по желанию проверяют известный контрольный результат \(792\). Это помогает отловить ошибки в арифметике конкатенации, в проверке простоты и в рекурсивном построении клик. После успешной проверки та же логика поиска запускается с целевым размером \(5\) и стандартным пределом простых.
Пусть \(P=\lvert\mathcal{P}\rvert\) — число оставшихся кандидатных простых, а \(T\) — стоимость одного теста простоты. Построение матрицы совместимости требует \(O(P^2T)\) времени и \(O(P^2)\) памяти, поскольку каждая неупорядоченная пара проверяется один раз, а результат сохраняется в полной симметричной таблице.
Рекурсивный поиск зависит от структуры выхода: его точная стоимость определяется тем, насколько разрежен граф совместимости. В наиболее плотном вообразимом случае при целевом размере \(5\) он может вести себя как \(O(P^5)\), но реальный граф разрежен, и каждый рекурсивный вызов заметно сокращает список кандидатов. Дополнительная память помимо матрицы — это лишь стек рекурсии и временные списки кандидатов, так что доминирующим слагаемым памяти остается матрица совместимости \(O(P^2)\).
نريد إيجاد خمسة أعداد أولية مختلفة بحيث إن كل زوج غير مرتب \(\{p,q\}\) يبقى أوليًا بعد دمج العددين في الاتجاهين معًا. فإذا كان \(p=7\) و\(q=109\)، فيجب أن يكون كل من \(7109\) و\(1097\) عددًا أوليًا. ومن بين جميع المجموعات ذات العناصر الخمسة التي تحقق هذا الشرط، نبحث عن المجموعة ذات أصغر مجموع.
تعتمد التطبيقات على البحث بين الأعداد الأولية الأصغر من حد قابل للضبط، والحد الافتراضي في مسألة Euler هو \(10{,}000\). وهناك نقطة تحقق أصغر معروفة مسبقًا: المجموعة \(\{3,7,109,673\}\) تحقق الشرط نفسه لأربعة أعداد أولية ويكون مجموعها \(792\). لذلك يجب على أي حل صحيح للمسألة الكاملة أن ينجح على الأقل في إعادة إنتاج هذا الاختبار الوسيط.
لنرمز بـ \(\mathcal{P}\) إلى مجموعة الأعداد الأولية المرشحة تحت حد البحث بعد حذف القيم التي يستحيل أن تنتمي إلى زوج صالح. ونعرّف علاقة توافق متناظرة \(p \sim q\) عندما يكون الدمج في الاتجاهين عددين أوليين. عندئذٍ تتحول المسألة 60 إلى مسألة إيجاد زمرة ذات وزن أدنى في رسم بياني غير موجه، حيث يكون وزن كل رأس هو قيمة العدد الأولي نفسه.
إذا كان \(d(q)\) هو عدد الأرقام العشرية في \(q\)، فإن
$$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$$
إذن فاختبار وجود حافة هو اختبار حسابي مباشر: نعطي الزوج \(p,q\)، ثم نحسب \(\operatorname{concat}(p,q)\) و\(\operatorname{concat}(q,p)\)، وبعدها نتحقق من أولية العددين. مع الحد الافتراضي \(10{,}000\) تكون جميع المرشحات ذات أربع خانات على الأكثر، ولذلك تبقى أكبر أعداد الدمج دون \(10^8\)؛ ومع ذلك تستعمل التطبيقات اختبار أولية ضمن مجال 64 بت لكي تبقى صحيحة حتى لو رُفع حد البحث.
تستبعد عملية البحث العددين \(2\) و\(5\) كليًا، وهذا ليس تقريبًا عمليًا بل نتيجة رياضية صريحة. إذا كان \(q\) عددًا أوليًا آخر، فإن \(\operatorname{concat}(q,2)\) ينتهي بالرقم \(2\) وهو أكبر من \(2\)، وبالتالي فهو عدد مركب. وبالمثل فإن \(\operatorname{concat}(q,5)\) ينتهي بالرقم \(5\) وهو أكبر من \(5\)، فيكون مركبًا أيضًا. وبما أن الزوج الصالح يتطلب الأولية في الاتجاهين معًا، فلا يمكن لأي مجموعة حجمها على الأقل \(2\) أن تحتوي \(2\) أو \(5\).
نبني رسمًا بيانيًا غير موجه \(G\) تكون مجموعة رؤوسه هي \(\mathcal{P}\)، ونصل بين \(p\) و\(q\) بحافة إذا وفقط إذا تحقق \(p \sim q\). عندئذٍ تكون أي مجموعة صالحة من خمسة أعداد أولية عبارة عن زمرة من الحجم \(5\) داخل \(G\): فكل رأسين مختارين متجاوران لأن جميع اختبارات الدمج المطلوبة تنجح.
الهدف ليس مجرد العثور على أي زمرة من الحجم \(5\)، بل تصغير
$$w(C)=\sum_{p\in C} p.$$
وبما أن جميع الأوزان موجبة، فإن المجاميع الجزئية تعطي وسيلة فورية للتقليم: إذا أصبحت المجموعة الجزئية كبيرة أكثر من اللازم، فلن تستطيع أي إضافات لاحقة أن تجعلها أفضل من الجواب الحالي.
تستعمل التطبيقات بحثًا بالعمق على زمر جزئية. تتكون الحالة التراجعية من مجموعة مختارة \(C\)، وقائمة مرشحين \(R\)، والمجموع الحالي \(s(C)\). أما الثابت الأساسي فهو
$$r\in R \Longrightarrow (\forall c\in C,\ r>c \text{ and } r\sim c).$$
ولأن الأعداد الأولية تُفحص بترتيب تصاعدي، فإن كل زمرة تُولد مرة واحدة فقط. وإذا كان العدد الأولي التالي المختار هو \(v\in R\)، فإن الاستدعاء التراجعي التالي يحتفظ فقط بالمرشحين اللاحقين الذين يبقون متوافقين مع الزمرة الموسعة:
$$R_v=\{u\in R:u>v \text{ and } (\forall x\in C\cup\{v\},\ u\sim x)\}.$$
وعندما نصل إلى \(\lvert C\rvert=5\)، نكون قد بنينا حلًا صالحًا، ثم نقارن مجموعه بأفضل مجموع عُثر عليه حتى تلك اللحظة.
قاعدتا التقليم الموجودتان في الشيفرة صحيحتان رياضيًا. الأولى: إذا كان \(\lvert R\rvert < 5-\lvert C\rvert\)، فليس هناك عدد كاف من الرؤوس المتبقية لإكمال زمرة من الحجم \(5\)، وبالتالي يكون هذا الفرع مستحيلًا. الثانية: إذا تحقق للمرشح التالي \(v\) أن \(s(C)+v\geq S_{\mathrm{best}}\)، فإن أي استمرار لهذا الفرع ستكون كلفته على الأقل \(s(C)+v\)، ومن ثم لا يمكن أن يحسن أفضل مجموع معروف. وبما أن جميع الأعداد الأولية موجبة، فيمكن حذف الفرع مباشرة.
هذا بالضبط برهان من نوع branch and bound، لكنه مخصص هنا لبحث زمرة موزونة ذات أوزان موجبة مع تعداد تصاعدي.
المجموعة
$$\{3,7,109,673\}$$
هي زمرة من الحجم \(4\). فمثلًا العددان \(3\) و\(109\) متوافقان لأن \(3109\) و\(1093\) أوليان، وكذلك \(7\) و\(673\) متوافقان لأن \(7673\) و\(6737\) أوليان. وينطبق الأمر نفسه على الأزواج الأربعة غير المرتبة الباقية، ولذلك تكون كل الأزواج داخل هذه المجموعة متصلة بحواف.
ومجموعها هو
$$3+7+109+673=792.$$
وتستخدم التطبيقات هذه الحقيقة كنقطة تحقق للمهمة الأصغر، وهي إيجاد زمرة من الحجم \(4\) ذات أصغر مجموع تحت \(1000\). أما مسألة Euler الكاملة فلها البنية نفسها تمامًا، ولكن على مستوى أعمق بمقدار خطوة واحدة: ننتقل من أربعة أعداد أولية متوافقة إلى خمسة.
تقوم تطبيقات C++ وPython وJava أولًا بتوليد جميع الأعداد الأولية حتى الحد المختار بواسطة الغربال، ثم تستبعد \(2\) و\(5\). وبعد ذلك يُفحص كل عدد ناتج عن الدمج أولًا عبر اختبارات سريعة للقابلية للقسمة على بعض الأعداد الأولية الصغيرة، ثم عبر اختبار Miller-Rabin حتمي ضمن 64 بت. هذا المزيج سريع بالنسبة إلى مدخلات Euler، ويبقى صحيحًا إذا زيد حد البحث.
بعد تجهيز قائمة الأعداد الأولية، تفحص الشيفرة كل زوج غير مرتب مرة واحدة فقط. وإذا كان الدمج في الاتجاهين أوليًا، يُعلَّم الزوج داخل مصفوفة توافق متناظرة. ومع الحد الافتراضي \(10{,}000\) يبقى لدينا \(1227\) عددًا أوليًا مرشحًا، ولذلك تنفذ هذه المرحلة
$$\binom{1227}{2}=752151$$
اختبارًا للأزواج، ويتضمن كل اختبار منهما فحصي أولية.
يبدأ البحث بزمرة فارغة وبالقائمة الكاملة المرتبة من الأعداد الأولية. في كل مستوى يُختار مرشح واحد، وتضاف قيمته إلى المجموع الجاري، ثم تُفحص المرشحات اللاحقة فقط. ولا ينتقل عدد أولي لاحق إلى الاستدعاء التالي إلا إذا كان متوافقًا مع جميع الأعداد الأولية المختارة حتى تلك اللحظة، وبذلك يبقى ثابت الزمرة محفوظًا دائمًا.
وعندما تُختار خمسة أعداد أولية، تُحدَّث أفضل قيمة للمجموع. ولا تحتاج الشيفرة إلى حفظ المجموعة المثلى كاملة، لأن المطلوب في السؤال هو أقل مجموع فقط.
قبل حل النسخة الكاملة، تستطيع التطبيقات أن تتحقق من القيمة المعروفة \(792\) الخاصة بأربعة أعداد أولية. هذه الخطوة تلتقط الأخطاء في صيغة الدمج أو في اختبار الأولية أو في بناء الزمر تراجعيًا. وبعد نجاح الاختبار، تُشغَّل آلية البحث نفسها مع حجم هدف يساوي \(5\) ومع حد الأعداد الأولية الافتراضي.
ليكن \(P=\lvert\mathcal{P}\rvert\) عدد الأعداد الأولية المرشحة المتبقية، ولتكن \(T\) كلفة اختبار أولية واحد. إن بناء مصفوفة التوافق يحتاج إلى زمن \(O(P^2T)\) ومساحة \(O(P^2)\)، لأن كل زوج غير مرتب يختبر مرة واحدة وتخزن النتيجة في جدول متناظر كامل.
أما البحث التراجعي فتعقيده الدقيق يعتمد على مدى تخلخل رسم التوافق. ففي الحالة القصوى المتخيلة، ومع حجم هدف ثابت يساوي \(5\)، قد يتصرف كأنه \(O(P^5)\)، لكن الرسم الحقيقي متناثر وتتناقص قائمة المرشحين بقوة في كل استدعاء. والمساحة الإضافية خارج المصفوفة تقتصر على مكدس الاستدعاءات والقوائم المؤقتة للمرشحين، لذلك يبقى الحد المهيمن للتخزين هو مصفوفة التوافق \(O(P^2)\).