We must use the digits \(1,2,\dots,9\) exactly once in total, split them into several decimal integers, and require every resulting integer to be prime. The goal is to count how many sets of primes are possible, so the collection \(\{23,461,5879\}\) is the same set regardless of the order in which its members are discovered.
The brute-force view is enormous: every ordered string of distinct digits might be one block in the partition, and a full solution must somehow organize all compatible prime blocks into unordered covers of \(\{1,\dots,9\}\). The implementations solve this by separating the problem into two layers: first generate every prime whose digits are distinct and taken from \(1\) through \(9\), then count exact covers of the digit set with a memoized recurrence.
The decisive mathematical objects are the family of admissible prime blocks and a recurrence on the remaining digit set. Once those are identified, the whole problem becomes a small exact-cover dynamic program on \(2^9\) masks.
Let \(\mathcal{P}\) be the set of all primes whose decimal expansion uses distinct digits drawn from \(\{1,\dots,9\}\). For each \(p\in\mathcal{P}\), let \(D(p)\subseteq\{1,\dots,9\}\) be the set of digits appearing in \(p\).
Every valid pandigital prime set is therefore a collection \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) such that
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\},$$
where \(\sqcup\) denotes disjoint union. So the original problem is equivalent to counting all exact covers of the digit set by digit-disjoint members of \(\mathcal{P}\).
The recursive generator used in the implementations produces \(\mathcal{P}\) directly: start from the empty string, append one unused digit at a time, and whenever the current prefix is prime, store it as an admissible block. Because every ordered sequence of distinct digits is reached exactly once, every possible prime block appears exactly once in this search tree.
For any subset \(S\subseteq\{1,\dots,9\}\), define \(F(S)\) to be the number of pandigital prime sets that use exactly the digits in \(S\). The target is \(F(\{1,\dots,9\})\), and the empty set has the natural base value
$$F(\varnothing)=1,$$
because there is exactly one way to cover no digits: choose no more primes.
Now let \(m(S)=\min S\), the smallest remaining digit. In any valid partition of \(S\), exactly one prime block contains that digit. This gives the recurrence
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
This is the key invariant behind the code. It removes duplicate counting without imposing any ordering on prime values: every unordered prime set has a unique first step, namely the block that contains the smallest still-uncovered digit. The implementations realize the same idea with a bitmask and its least significant set bit.
Suppose a valid solution is the set \(\{p_1,\dots,p_r\}\). If we tried to build it by freely choosing the next block, the same set would appear in \(r!\) different orders. The anchor rule avoids that completely. At the top level, the chosen block must be the unique one containing digit \(1\). After removing that block, the next chosen block must be the unique one containing the smallest digit not yet used, and so on.
So every valid set determines exactly one path through the recurrence, and every path clearly reconstructs a valid set of digit-disjoint primes. That proves a bijection between solutions and recursion paths.
The prime generator explores every non-empty ordered string of distinct digits from \(1\) through \(9\). The exact number of such prefixes is
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
Only a small fraction survive the primality test; for the full problem the candidate list contains 43089 admissible primes. Also, no 9-digit candidate can survive, because every permutation of \(1,\dots,9\) has digit sum \(45\) and is therefore divisible by \(9\). Once the candidate list is known, the counting phase has only \(2^9=512\) remaining-digit states.
The smaller instance on digits \(\{1,2,3,4\}\) is useful because the same recurrence already shows the whole mechanism. Here the smallest remaining digit is always the anchor digit \(1\) at the top level. The admissible prime blocks containing \(1\) are
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
The first two leave the digit set \(\{2,4\}\), which has no prime cover, so those branches contribute \(0\). The others give
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
Now \(F(\{3\})=1\) because \(\{3\}\) itself is prime, \(F(\{2\})=1\), and
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
coming from the covers \(\{2,3\}\) and \(\{23\}\). Therefore
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
The nine corresponding sets are \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\), and \(\{4231\}\). This is exactly the checkpoint used by the parameterized implementation before it runs the full \(1\) through \(9\) case.
The C++, Python, and Java implementations first enumerate digit strings recursively. Starting from value \(0\) and an empty used-digit mask, they append one unused digit to the right, forming a new decimal prefix. Whenever that prefix is prime, the implementation stores the pair consisting of the prime value and the mask of digits used by that value. The recursion then continues, because a prime prefix can still be extended into a longer prime built from additional unused digits.
After generation, the candidate list is normalized to unique pairs before the counting stage. Conceptually, this list is just the finite set \(\mathcal{P}\) together with the digit set \(D(p)\) attached to each member.
The second phase replaces digit subsets by 9-bit masks. A mask represents the digits that still need to be covered. The empty mask returns \(1\). For any non-empty mask, the implementation extracts its least significant set bit, which is the smallest remaining digit, and scans the stored prime blocks. A block contributes only if its digit mask is a subset of the remaining mask and also contains the anchor bit.
Whenever those two conditions hold, the code removes that block's digits from the remaining mask and recurses. The result is memoized by mask, so each remaining-digit state is solved once. This is a direct bit-level implementation of the recurrence for \(F(S)\) above.
The C++ and Java implementations use straightforward trial division up to \(\sqrt{n}\). That is sufficient here because every candidate is less than \(10^9\), so \(\sqrt{n}\lt 31623\). The Python implementation uses a library primality routine, but the surrounding combinatorics and the mask recurrence are the same in all three languages.
Candidate generation visits exactly 986409 non-empty digit prefixes. If we write \(T_{\mathrm{prime}}(x)\) for the cost of one primality test at magnitude \(x\), the generation phase is
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
In the concrete implementations, trial division makes \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\) in C++ and Java, while Python delegates this step to its primality library.
After that, the dynamic program has only 512 memo states. The stored candidate list has 43089 prime blocks, and each state performs a linear scan through that list with constant-time mask tests. So the counting phase is \(O(512\cdot 43089)\) simple compatibility checks for the full problem, with memory \(O(512+43089)\).
More generally, if the digit set were \(\{1,\dots,n\}\), the same method would use \(2^n\) memo states and enumerate \(\sum_{k=1}^{n} P(n,k)\) candidate prefixes. For \(n=9\), that fixed search space is small enough that this exact-cover approach is entirely practical.
Wir sollen die Ziffern \(1,2,\dots,9\) insgesamt genau einmal benutzen, sie in mehrere Dezimalzahlen zerlegen und verlangen, dass jede dieser Zahlen prim ist. Gesucht ist die Anzahl aller solchen Mengen von Primzahlen. Die Reihenfolge der Elemente spielt also keine Rolle; \(\{23,461,5879\}\) und \(\{5879,23,461\}\) sind dieselbe Lösung.
Als rohes Suchproblem ist das riesig: Jeder geordnete String aus verschiedenen Ziffern könnte ein Block der Zerlegung sein, und am Ende müssen diese Blöcke die Ziffernmenge \(\{1,\dots,9\}\) disjunkt überdecken. Die Implementierungen zerlegen das deshalb in zwei klar getrennte Schritte: zuerst alle Primzahlen mit paarweise verschiedenen Ziffern aus \(1\) bis \(9\) erzeugen, dann exakte Überdeckungen dieser Ziffernmenge mit einer memoisierten Rekursion zählen.
Die entscheidenden Objekte sind die Menge aller zulässigen Primzahlblöcke und eine Rekurrenz auf der noch nicht verbrauchten Ziffernmenge. Hat man diese Formulierung, schrumpft das Problem auf eine kleine Exact-Cover-Dynamik über \(2^9\) Masken.
Sei \(\mathcal{P}\) die Menge aller Primzahlen, deren Dezimalschreibweise nur verschiedene Ziffern aus \(\{1,\dots,9\}\) enthält. Für \(p\in\mathcal{P}\) bezeichne \(D(p)\subseteq\{1,\dots,9\}\) die Menge der in \(p\) vorkommenden Ziffern.
Jede gültige pandigitale Primzahlmenge ist dann eine Sammlung \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) mit
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}.$$
Das Originalproblem ist also äquivalent dazu, alle exakten Überdeckungen der Ziffernmenge durch zifferndisjunkte Elemente von \(\mathcal{P}\) zu zählen.
Die rekursive Erzeugung in den Implementierungen baut \(\mathcal{P}\) direkt auf: Man startet mit dem leeren String, hängt jeweils eine noch unbenutzte Ziffer rechts an und speichert jeden Präfix, der prim ist, als zulässigen Block. Da jede geordnete Folge verschiedener Ziffern genau einmal entsteht, erscheint auch jeder mögliche Primzahlblock genau einmal.
Für jede Teilmenge \(S\subseteq\{1,\dots,9\}\) sei \(F(S)\) die Anzahl der Primzahlmengen, die genau die Ziffern aus \(S\) verwenden. Gesucht ist also \(F(\{1,\dots,9\})\). Für die leere Menge gilt
$$F(\varnothing)=1,$$
denn es gibt genau eine Möglichkeit, keine Ziffern mehr zu überdecken: man wählt keine weiteren Primzahlen.
Nun setze \(m(S)=\min S\), also die kleinste noch übrige Ziffer. In jeder gültigen Zerlegung von \(S\) gibt es genau einen Primzahlblock, der diese Ziffer enthält. Daraus folgt die Rekurrenz
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
Genau dies ist die zentrale Invariante des Codes. Doppelte Zählung wird nicht durch eine Sortierung nach Primzahlwerten vermieden, sondern dadurch, dass immer der eindeutig bestimmte Block gewählt wird, der die kleinste noch freie Ziffer enthält. Im Bitmasken-Code ist das das niederwertigste gesetzte Bit.
Nehmen wir eine gültige Lösung \(\{p_1,\dots,p_r\}\). Ohne Zusatzregel könnte dieselbe Menge in \(r!\) verschiedenen Reihenfolgen aufgebaut werden. Die Ankerregel verhindert das vollständig. Auf der obersten Ebene muss der gewählte Block die Ziffer \(1\) enthalten. Danach muss der nächste Block die kleinste noch unbenutzte Ziffer enthalten, und so weiter.
Damit bestimmt jede gültige Menge genau einen Rekursionspfad, und umgekehrt rekonstruiert jeder Pfad eindeutig eine gültige Menge zifferndisjunkter Primzahlen. Das ist die gewünschte Bijektion zwischen Lösungen und Pfaden.
Der Generator besucht jeden nichtleeren geordneten String aus verschiedenen Ziffern von \(1\) bis \(9\). Die exakte Anzahl dieser Präfixe ist
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
Nur ein kleiner Teil davon besteht den Primzahltest; für das volle Problem bleiben 43089 zulässige Primzahlen übrig. Außerdem kann kein 9-stelliger Kandidat prim sein, denn jede Permutation von \(1,\dots,9\) hat die Quersumme \(45\) und ist daher durch \(9\) teilbar. Ist die Kandidatenliste einmal erzeugt, besitzt die Zählphase nur noch \(2^9=512\) Zustände der Restziffern.
Die kleinere Instanz mit \(\{1,2,3,4\}\) zeigt bereits die vollständige Mechanik. Auf der obersten Ebene ist die kleinste verbleibende Ziffer \(1\), also müssen wir nur Primzahlblöcke betrachten, die \(1\) enthalten. Das sind
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
Die ersten beiden lassen die Restmenge \(\{2,4\}\) zurück, und diese besitzt keine Primzahlüberdeckung. Ihr Beitrag ist also \(0\). Für die übrigen Kandidaten erhält man
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
Hier ist \(F(\{3\})=1\), \(F(\{2\})=1\), und
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
denn \(\{2,3\}\) kann entweder als zwei einstellige Primzahlen oder als \(\{23\}\) überdeckt werden. Also folgt
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
Die neun Mengen sind \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\) und \(\{4231\}\). Genau dieser Wert \(9\) dient in der parametrisierbaren Implementierung als Kontrollpunkt, bevor der volle Fall \(1\) bis \(9\) berechnet wird.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst rekursiv Dezimalstrings. Ausgehend von Wert \(0\) und leerer Ziffernmaske wird jeweils eine noch unbenutzte Ziffer rechts angehängt. Sobald der aktuelle Präfix prim ist, speichert die Implementierung das Paar aus Primzahlwert und der dazugehörigen Ziffernmaske. Die Rekursion läuft trotzdem weiter, weil ein primärer Präfix noch zu einer längeren Primzahl mit zusätzlichen freien Ziffern erweitert werden kann.
Nach der Erzeugung wird die Kandidatenliste auf eindeutige Paare normalisiert. Inhaltlich ist diese Liste einfach die endliche Menge \(\mathcal{P}\) zusammen mit der zu jeder Primzahl gehörenden Ziffernmenge \(D(p)\).
In der zweiten Phase werden Ziffernteilmengen durch 9-Bit-Masken repräsentiert. Eine Maske beschreibt die Ziffern, die noch zu überdecken sind. Die leere Maske liefert \(1\). Für jede nichtleere Maske extrahiert der Code ihr niederwertigstes gesetztes Bit; das ist genau die kleinste noch übrige Ziffer. Dann werden alle gespeicherten Primzahlblöcke durchlaufen.
Ein Block trägt genau dann zur Summe bei, wenn seine Ziffernmaske eine Teilmenge der Restmaske ist und zugleich das Ankerbit enthält. In diesem Fall werden diese Ziffern aus der Restmaske entfernt und der Rest rekursiv gezählt. Das Ergebnis wird pro Maske memoisiert, sodass jeder Zustand nur einmal gelöst wird. Auf Bitebene ist das exakt die oben angegebene Rekurrenz für \(F(S)\).
Die C++- und Java-Implementierungen verwenden naive Teilbarkeitstests bis \(\sqrt{n}\). Das genügt hier vollkommen, weil jeder Kandidat kleiner als \(10^9\) ist und also \(\sqrt{n}\lt 31623\) gilt. Die Python-Implementierung verwendet eine Bibliotheksroutine für Primzahltests; die umgebende Kombinatorik und die Maskenrekurrenz sind jedoch in allen drei Sprachen dieselben.
Die Kandidatenerzeugung besucht exakt 986409 nichtleere Ziffernpräfixe. Schreibt man \(T_{\mathrm{prime}}(x)\) für die Kosten eines Primzahltests bei Größenordnung \(x\), dann kostet die Erzeugungsphase
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
Mit Teilbarkeitsprüfung ist in C++ und Java \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\); Python delegiert diesen Schritt an seine Primzahlbibliothek.
Danach besitzt das dynamische Programm nur 512 Memo-Zustände. Die Kandidatenliste enthält 43089 Primzahlblöcke, und jeder Zustand testet diese Liste mit konstanten Maskenoperationen auf Verträglichkeit. Für das volle Problem ist die Zählphase also \(O(512\cdot 43089)\) an einfachen Kompatibilitätsprüfungen, bei Speicherbedarf \(O(512+43089)\).
Allgemeiner würde man für die Ziffernmenge \(\{1,\dots,n\}\) genau \(2^n\) Memo-Zustände und \(\sum_{k=1}^{n} P(n,k)\) erzeugte Präfixe erhalten. Für \(n=9\) ist dieser feste Suchraum klein genug, dass der Exact-Cover-Ansatz praktisch sofort funktioniert.
\(1,2,\dots,9\) rakamlarını toplamda tam birer kez kullanacağız, bunları birkaç onluk sayıya ayıracağız ve ortaya çıkan her sayının asal olmasını isteyeceğiz. Amaç, bu koşulu sağlayan asal sayı kümelerinin kaç tane olduğunu saymaktır. Yani \(\{23,461,5879\}\) ile \(\{5879,23,461\}\) aynı çözümdür; sıranın önemi yoktur.
Ham kuvvetle bakıldığında arama uzayı çok büyüktür: farklı rakamlardan oluşan her sıralı dize olası bir blok olabilir ve sonunda bu blokların \(\{1,\dots,9\}\) kümesini çakışmasız biçimde kaplaması gerekir. Uygulamalar bunu iki katmana ayırır: önce rakamları farklı olan bütün asal blokları üretir, sonra bu bloklarla rakam kümesinin tam kaplamalarını memoized bir özyineleme ile sayar.
Bu problemde asıl matematiksel nesneler, izin verilen asal bloklar ailesi ile kalan rakam kümesi üzerinde çalışan yinelemedir. Bu formülasyon kurulduğunda tüm görev, \(2^9\) maskeli küçük bir exact-cover dinamik programına dönüşür.
\(\mathcal{P}\), onluk yazımı yalnızca \(\{1,\dots,9\}\) içinden gelen ve birbirini tekrar etmeyen rakamlardan oluşan tüm asal sayıların kümesi olsun. Her \(p\in\mathcal{P}\) için \(D(p)\subseteq\{1,\dots,9\}\), \(p\)'de geçen rakamların kümesini göstersin.
O halde her geçerli pandijital asal küme,
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}$$
eşitliğini sağlayan bir \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) koleksiyonudur. Buradaki \(\sqcup\), birleşimin ayrık olduğunu ifade eder. Dolayısıyla orijinal soru, \(\{1,\dots,9\}\) rakam kümesini \(\mathcal{P}\)'nin rakam bakımından ayrık elemanlarıyla tam olarak kaç farklı biçimde örtebildiğimizi sormaktadır.
Uygulamalardaki özyinelemeli üretici \(\mathcal{P}\)'yi doğrudan üretir: boş dizeden başlanır, her adımda kullanılmamış bir rakam sağa eklenir ve oluşan önek asal ise geçerli bir blok olarak saklanır. Farklı rakamlardan oluşan her sıralı dize arama ağacında tam bir kez ortaya çıktığı için, her olası asal blok da tam bir kez üretilir.
\(\{1,\dots,9\}\)'un her \(S\) altkümesi için, \(F(S)\) tam olarak \(S\)'deki rakamları kullanan pandijital asal kümelerin sayısı olsun. Aradığımız nicelik \(F(\{1,\dots,9\})\)'dur. Boş küme için doğal başlangıç değeri
$$F(\varnothing)=1$$
olur; çünkü hiç rakam kalmadığında yapılacak tek şey başka sayı seçmemektir.
Şimdi \(m(S)=\min S\) olsun; yani elde kalan en küçük rakam. \(S\)'nin herhangi bir geçerli parçalanışında bu rakamı içeren tam bir blok vardır. Bu gözlem şu yinelemeyi verir:
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
Bu, kodun kullandığı temel değişmezdir. Tekrarlı sayımı önlemek için asal değerleri büyüklüğe göre sıralamaya gerek yoktur; bunun yerine her adımda henüz kapatılmamış en küçük rakamı içeren tek blok seçilir. Bit maskesi düzeyinde bu, en düşük anlamlı 1 bitinin zorunlu olarak seçilmesidir.
Bir çözüm \(\{p_1,\dots,p_r\}\) olsun. Eğer bir sonraki bloğu serbestçe seçseydik aynı küme \(r!\) farklı sırayla üretilebilirdi. Çapa kuralı bunu tamamen yok eder. En üst seviyede seçilecek blok mutlaka \(1\) rakamını içermelidir. O blok çıkarıldıktan sonra sıradaki seçim, henüz kullanılmamış en küçük rakamı içeren blok olmak zorundadır; süreç aynı şekilde devam eder.
Böylece her geçerli küme tam olarak tek bir özyineleme yoluna karşılık gelir ve her yol da açıkça rakamları ayrık asal sayılardan oluşan tek bir kümeyi yeniden kurar. Yani çözümler ile özyineleme yolları arasında bire bir eşleme vardır.
Üretici, \(1\) ile \(9\) arasındaki rakamlardan oluşan her boş olmayan sıralı öneki gezer. Bu öneklerin tam sayısı
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409$$
olur. Bunların yalnızca küçük bir bölümü asallık testini geçer; tam problemde saklanan aday blok sayısı 43089'dur. Ayrıca 9 basamaklı hiçbir aday asal olamaz, çünkü \(1,\dots,9\)'un her permütasyonunun rakam toplamı \(45\)'tir ve bu yüzden sayı \(9\)'a bölünür. Aday listesi bir kez hazırlandıktan sonra sayma aşamasında yalnızca \(2^9=512\) kalan-rakam durumu vardır.
\(\{1,2,3,4\}\) alt problemi aynı mekanizmayı daha küçük ölçekte gösterir. En üst seviyede çapa rakamı \(1\)'dir. Bu nedenle yalnızca \(1\)'i içeren asal bloklara bakarız:
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
İlk iki seçenek geriye \(\{2,4\}\) bırakır; bu kümenin asal bir kaplaması yoktur, yani katkıları \(0\)'dır. Kalan dallar için
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing) \end{aligned}$$
elde edilir. Burada \(F(\{3\})=1\), \(F(\{2\})=1\) ve
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2$$
çünkü \(\{2,3\}\) ya iki tek basamaklı asal olarak ya da \(\{23\}\) olarak kaplanabilir. Sonuç:
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
Buna karşılık gelen dokuz küme \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\) ve \(\{4231\}\)'dir. Parametreli uygulama tam \(1\) ile \(9\) durumuna geçmeden önce bu değeri kontrol noktası olarak doğrular.
C++, Python ve Java uygulamaları önce rakam dizilerini özyinelemeli olarak üretir. Başlangıçta değer \(0\) ve kullanılan-rakam maskesi boştur. Her adımda kullanılmamış bir rakam sağa eklenerek yeni bir onluk önek oluşturulur. Bu önek asal ise, uygulama asal değeri ve o değerin kullandığı rakam maskesini saklar. Arama burada durmaz; çünkü asal bir önek, ek kullanılmamış rakamlarla daha uzun bir asala dönüşebilir.
Üretimden sonra aday listesi eşsiz çiftlere indirgenir. Kavramsal olarak bu liste, her elemanına \(D(p)\) rakam kümesi bağlanmış sonlu \(\mathcal{P}\) kümesinden ibarettir.
İkinci aşamada rakam altkümeleri 9 bitlik maskelerle temsil edilir. Bir maske, hâlâ kapatılması gereken rakamları gösterir. Boş maske \(1\) döndürür. Boş olmayan bir maske için kod, en düşük anlamlı 1 bitini çıkarır; bu bit tam olarak elde kalan en küçük rakama karşılık gelir. Sonra saklanan tüm asal bloklar sırayla incelenir.
Bir blok ancak iki koşulda katkı yapar: rakam maskesi mevcut maskenin altkümesi olmalı ve çapa bitini içermelidir. Bu sağlanınca o bloğun rakamları maskeden çıkarılır ve kalan durum özyinelemeli olarak sayılır. Sonuç maske bazında önbelleğe alındığı için her kalan-rakam durumu yalnızca bir kez çözülür. Bu, yukarıdaki \(F(S)\) yinelemesinin tam bit-seviyesindeki karşılığıdır.
C++ ve Java sürümleri \(\sqrt{n}\)'e kadar basit bölen denemesi kullanır. Burada bu tamamen yeterlidir; çünkü her aday \(10^9\)'dan küçüktür ve dolayısıyla \(\sqrt{n}\lt 31623\). Python sürümü bir kütüphane asallık testi kullanır, fakat etrafındaki kombinatorik yapı ve maskeli yineleme üç dilde de aynıdır.
Aday üretim aşaması tam olarak 986409 boş olmayan rakam öneğini ziyaret eder. Büyüklüğü \(x\) olan bir sayının asallık testi maliyetine \(T_{\mathrm{prime}}(x)\) dersek, üretim aşamasının maliyeti
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right)$$
olur. C++ ve Java için bölen denemesiyle \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\), Python'da ise bu adım kütüphaneye devredilir.
Bundan sonra dinamik programın yalnızca 512 memo durumu vardır. Saklanan aday blok sayısı 43089'dur ve her durum bu listenin tamamında sabit zamanlı maske kontrolleri yapar. Bu yüzden tam problemde sayma aşaması \(O(512\cdot 43089)\) düzeyinde basit uyumluluk testi yapar; bellek kullanımı ise \(O(512+43089)\)'dur.
Daha genel olarak rakam kümesi \(\{1,\dots,n\}\) olsaydı yöntem \(2^n\) memo durumu ve \(\sum_{k=1}^{n} P(n,k)\) aday önek üretirdi. \(n=9\) için bu sabit arama uzayı exact-cover yaklaşımını oldukça pratik hale getirir.
Debemos usar los dígitos \(1,2,\dots,9\) exactamente una vez en total, separarlos en varios enteros decimales y exigir que cada entero resultante sea primo. La tarea consiste en contar cuántos conjuntos de primos cumplen eso. Por tanto, \(\{23,461,5879\}\) y \(\{5879,23,461\}\) representan la misma solución: importa el conjunto, no el orden en que se construye.
Visto de forma directa, el espacio de búsqueda es grande: cualquier cadena ordenada de dígitos distintos podría ser un bloque de la partición, y al final esos bloques tienen que cubrir \(\{1,\dots,9\}\) sin solapamientos. Las implementaciones separan el problema en dos capas: primero generan todos los primos cuyas cifras son distintas y pertenecen a \(1\) a \(9\); después cuentan las coberturas exactas del conjunto de dígitos con una recurrencia memoizada.
Los objetos matemáticos decisivos son la familia de bloques primos admisibles y una recurrencia sobre el conjunto de dígitos que aún faltan por cubrir. Una vez escrita así, la tarea se convierte en un pequeño programa dinámico de exact cover sobre \(2^9\) máscaras.
Sea \(\mathcal{P}\) el conjunto de todos los números primos cuya expansión decimal usa dígitos distintos tomados de \(\{1,\dots,9\}\). Para cada \(p\in\mathcal{P}\), denotemos por \(D(p)\subseteq\{1,\dots,9\}\) el conjunto de dígitos que aparecen en \(p\).
Cada conjunto pandigital primo válido es entonces una colección \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) tal que
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}.$$
Es decir, el problema original equivale a contar todas las coberturas exactas del conjunto de dígitos mediante elementos de \(\mathcal{P}\) cuyas cifras no se superponen.
El generador recursivo de las implementaciones construye \(\mathcal{P}\) directamente: parte de la cadena vacía, añade un dígito no usado a la derecha y, cada vez que el prefijo actual es primo, lo guarda como bloque admisible. Como cada secuencia ordenada de dígitos distintos aparece exactamente una vez, cada bloque primo posible también aparece exactamente una vez.
Para cada subconjunto \(S\subseteq\{1,\dots,9\}\), definimos \(F(S)\) como el número de conjuntos de primos pandigitales que usan exactamente los dígitos de \(S\). El objetivo es \(F(\{1,\dots,9\})\). Para el conjunto vacío se tiene
$$F(\varnothing)=1,$$
porque hay una única forma de cubrir cero dígitos: no elegir más primos.
Sea ahora \(m(S)=\min S\), el dígito más pequeño que queda. En cualquier partición válida de \(S\), existe exactamente un bloque primo que contiene ese dígito. Eso produce la recurrencia
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
Ésta es la invariante clave del código. La eliminación de duplicados no se logra imponiendo un orden numérico a los primos, sino seleccionando siempre el bloque que contiene el menor dígito todavía libre. En la implementación con máscaras, eso es exactamente el bit menos significativo encendido.
Supongamos que una solución válida es el conjunto \(\{p_1,\dots,p_r\}\). Si permitiéramos elegir libremente el siguiente bloque, el mismo conjunto aparecería en \(r!\) órdenes distintos. La regla del ancla evita eso por completo. En el nivel superior, el bloque elegido debe contener el dígito \(1\). Tras retirarlo, el siguiente bloque debe contener el menor dígito que aún no ha sido usado, y así sucesivamente.
Por tanto, cada conjunto válido determina un único camino en la recurrencia, y cada camino reconstruye de forma inequívoca un conjunto válido de primos con dígitos disjuntos. Eso establece la biyección necesaria entre soluciones y caminos de búsqueda.
El generador recorre todas las cadenas no vacías ordenadas de dígitos distintos tomados de \(1\) a \(9\). El número exacto de esos prefijos es
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
Sólo una pequeña fracción supera el test de primalidad; para el problema completo quedan 43089 primos candidatos. Además, ningún candidato de 9 cifras puede ser primo, porque cualquier permutación de \(1,\dots,9\) tiene suma de cifras \(45\) y, por tanto, es divisible por \(9\). Una vez conocida la lista de candidatos, la fase de conteo sólo tiene \(2^9=512\) estados de dígitos restantes.
La instancia reducida sobre \(\{1,2,3,4\}\) ya muestra el mecanismo completo. En el nivel superior, el dígito ancla es \(1\). Así que sólo hay que considerar los bloques primos que contienen ese dígito:
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
Los dos primeros dejan \(\{2,4\}\), y ese conjunto no admite una cobertura prima, así que su contribución es \(0\). Para las demás ramas se obtiene
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
Aquí \(F(\{3\})=1\), \(F(\{2\})=1\), y
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
porque \(\{2,3\}\) puede cubrirse como dos primos de una cifra o como \(\{23\}\). En consecuencia,
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
Los nueve conjuntos son \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\) y \(\{4231\}\). Ese mismo valor \(9\) es el punto de control que usa la implementación parametrizada antes de ejecutar el caso completo con \(1\) a \(9\).
Las implementaciones en C++, Python y Java empiezan enumerando cadenas de dígitos de forma recursiva. Parten del valor \(0\) y de una máscara vacía de dígitos usados, y en cada paso añaden a la derecha un dígito aún no utilizado. Cuando el prefijo formado es primo, guardan el par compuesto por el valor primo y la máscara de dígitos que usa ese valor. La búsqueda no se detiene ahí, porque un prefijo primo todavía puede prolongarse hasta dar otro primo más largo usando dígitos restantes.
Después de generar la lista, ésta se normaliza a pares únicos antes de empezar el conteo. Matemáticamente, esa estructura no es más que el conjunto finito \(\mathcal{P}\) con el conjunto \(D(p)\) asociado a cada elemento.
La segunda fase sustituye los subconjuntos de dígitos por máscaras de 9 bits. Una máscara representa los dígitos que aún faltan por cubrir. La máscara vacía devuelve \(1\). Para cualquier máscara no vacía, la implementación extrae su bit menos significativo encendido, que corresponde al menor dígito restante, y recorre los bloques primos almacenados.
Un bloque contribuye sólo si su máscara de dígitos es un subconjunto de la máscara restante y además contiene el bit ancla. Cuando ambas condiciones se cumplen, esos dígitos se eliminan de la máscara y el resto se cuenta de forma recursiva. El resultado se memoriza por máscara, de modo que cada estado se resuelve una sola vez. Eso es exactamente la realización a nivel de bits de la recurrencia para \(F(S)\).
Las versiones en C++ y Java usan división por prueba hasta \(\sqrt{n}\). Aquí es suficiente porque todo candidato es menor que \(10^9\), así que \(\sqrt{n}\lt 31623\). La versión en Python delega la primalidad en una rutina de biblioteca, pero la combinatoria y la recurrencia sobre máscaras son las mismas en los tres lenguajes.
La generación de candidatos visita exactamente 986409 prefijos no vacíos. Si \(T_{\mathrm{prime}}(x)\) denota el coste de un test de primalidad para magnitud \(x\), la fase de generación cuesta
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
Con división por prueba, C++ y Java tienen \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\); Python delega ese paso en su biblioteca de primalidad.
Después, el programa dinámico tiene sólo 512 estados memoizados. La lista almacenada contiene 43089 bloques primos, y cada estado recorre esa lista con pruebas de compatibilidad de tiempo constante sobre máscaras. Por eso, en el problema completo, la fase de conteo realiza \(O(512\cdot 43089)\) comprobaciones simples, con memoria \(O(512+43089)\).
Más en general, si el conjunto de dígitos fuera \(\{1,\dots,n\}\), el mismo método usaría \(2^n\) estados memoizados y enumeraría \(\sum_{k=1}^{n} P(n,k)\) prefijos candidatos. Para \(n=9\), ese tamaño fijo de búsqueda hace que el enfoque de exact cover sea perfectamente práctico.
题目要求把数字 \(1,2,\dots,9\) 全部用掉且每个数字恰好使用一次，把它们拆成若干个十进制整数，并要求得到的每个整数都是素数。我们要统计这样的素数集合一共有多少个。因此 \(\{23,461,5879\}\) 与 \(\{5879,23,461\}\) 是同一个解，因为题目计数的是集合而不是出现顺序。
如果直接暴力搜索，规模会很大。任意一个由互不重复数字组成的有序串都可能成为一个分块，而最终这些分块必须无重叠地覆盖整个数字集合 \(\{1,\dots,9\}\)。三个实现都把问题拆成两个层次：先生成所有由 \(1\) 到 \(9\) 中互不重复数字构成的素数块，再用一个带记忆化的递推去统计这些块对数字集合的精确覆盖。
真正关键的数学对象有两个：一是所有可用素数块组成的候选族，二是定义在“剩余数字集合”上的递推关系。一旦把问题改写成这个形式，整个任务就变成了一个只有 \(2^9\) 个状态的小型 exact cover 动态规划。
记 \(\mathcal{P}\) 为所有满足以下条件的素数集合：它们的十进制表示只使用 \(\{1,\dots,9\}\) 中的数字，而且每个数字在该素数内部最多出现一次。对任意 \(p\in\mathcal{P}\)，记 \(D(p)\subseteq\{1,\dots,9\}\) 为 \(p\) 所使用的数字集合。
那么，一个合法的 pandigital prime set 就等价于一组素数 \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\)，满足
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}.$$
也就是说，原题本质上是在问：用 \(\mathcal{P}\) 中数字互不重叠的成员，对 \(\{1,\dots,9\}\) 做精确覆盖，一共有多少种方式。
实现中的递归生成器正是直接构造这个 \(\mathcal{P}\)。它从空串开始，每一步把一个尚未使用过的数字接到右边；只要当前前缀是素数，就把它存成一个可用块。由于每一种“互不重复数字的有序串”都会在搜索树中恰好出现一次，所以每一个可能的素数块也恰好被生成一次。
对于任意子集 \(S\subseteq\{1,\dots,9\}\)，定义 \(F(S)\) 为“恰好使用 \(S\) 中这些数字”的 pandigital prime set 数量。题目要求的就是 \(F(\{1,\dots,9\})\)。空集的边界值自然是
$$F(\varnothing)=1,$$
因为当没有数字剩下时，覆盖方法只有一种：什么都不再选。
现在令 \(m(S)=\min S\)，即当前尚未覆盖数字中的最小者。对于任意一个对 \(S\) 的合法分解，必然存在且只存在一个素数块包含这个最小数字。因此得到递推式
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
这就是代码真正依赖的不变量。它不是通过“把素数按数值升序加入”来去重，而是通过“每一步必须选择包含当前最小剩余数字的那一个块”来保证每个集合只被计数一次。在位掩码实现中，这个约束正好对应于最低位的那个 1。
设某个有效解是集合 \(\{p_1,\dots,p_r\}\)。如果在搜索中允许任意挑选下一个块，那么同一个集合会以 \(r!\) 种不同顺序被重复生成。锚点规则完全消除了这种重复。第一步必须选择包含数字 \(1\) 的块；删去这个块后，下一步必须选择包含当前最小未使用数字的块；之后同理。
因此，每一个合法集合都会对应到唯一的一条递推路径；反过来，每一条递推路径也都会唯一地重构出一个由数字互不相交素数组成的合法集合。这就建立了“解集”与“递推路径”之间的一一对应。
生成器会遍历所有由 \(1\) 到 \(9\) 中互不重复数字构成的非空有序前缀。这样的前缀总数精确为
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
其中只有很小一部分能够通过素性检验；对于完整的题目，最终保留下来的候选素数块有 43089 个。另外，9 位候选数不可能是素数，因为 \(1,\dots,9\) 任意排列的数位和都是 \(45\)，必然能被 \(9\) 整除。候选列表确定之后，计数阶段就只剩下 \(2^9=512\) 个“剩余数字”状态了。
用 \(\{1,2,3,4\}\) 这个较小的实例可以把同样的递推过程看得很清楚。顶层时，锚点数字是 \(1\)，所以只需要考虑那些包含 \(1\) 的素数块：
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
前两个块会留下 \(\{2,4\}\)，而 \(\{2,4\}\) 没有任何素数覆盖，所以这两条分支贡献 \(0\)。其余分支给出
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
这里 \(F(\{3\})=1\)，\(F(\{2\})=1\)，并且
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
因为 \(\{2,3\}\) 既可以拆成两个一位素数，也可以用单个素数 \(\{23\}\) 覆盖。于是
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
对应的九个集合是 \(\{2,3,41\}\)、\(\{23,41\}\)、\(\{3,241\}\)、\(\{3,421\}\)、\(\{2,431\}\)、\(\{1423\}\)、\(\{2143\}\)、\(\{2341\}\) 和 \(\{4231\}\)。这正是带参数实现先验证的小规模检查点。
C++、Python 和 Java 实现都先递归枚举数字串。起点是数值 \(0\) 和空的“已用数字掩码”。每一步把一个尚未使用的数字接到当前数值右侧，形成新的十进制前缀；只要这个前缀是素数，就把“素数值”和“它所使用的数字掩码”这一对信息保存下来。随后递归继续，因为一个已经是素数的前缀仍然可能继续扩展成更长的素数。
生成完成后，代码会把候选列表规范化为互不重复的条目。抽象地看，这个列表就是有限集合 \(\mathcal{P}\) 以及每个元素对应的数字集 \(D(p)\)。
第二阶段把数字子集表示成 9 位掩码。一个掩码表示“还有哪些数字没有被覆盖”。空掩码返回 \(1\)。对于任意非空掩码，实现会先取出最低位的 1，也就是当前最小的剩余数字，然后扫描所有已经存储的素数块。
只有当某个块满足两个条件时，它才会贡献到答案中：它的数字掩码必须是当前剩余掩码的子集，并且它还必须包含那个锚点位。一旦满足条件，就把这组数字从剩余掩码中删掉，并递归统计剩余部分的方案数。每个掩码状态都会被记忆化，因此每个状态只求解一次。这就是上面 \(F(S)\) 递推式的位运算版本。
C++ 和 Java 使用的是到 \(\sqrt{n}\) 为止的试除法。这里完全够用，因为所有候选数都小于 \(10^9\)，所以 \(\sqrt{n}\lt 31623\)。Python 则调用库中的素性判断，但候选生成与掩码递推的组合结构在三种语言中完全一致。
候选生成阶段会访问恰好 986409 个非空数字前缀。若记一次数量级为 \(x\) 的素性测试代价为 \(T_{\mathrm{prime}}(x)\)，那么生成阶段的复杂度为
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
对 C++ 和 Java 而言，试除法给出 \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\)；Python 把这一步交给其素性库完成。
之后的动态规划只有 512 个记忆化状态。保存下来的候选素数块共有 43089 个，而每个状态只需要用常数时间的位运算去检查这些块是否兼容。因此完整题目的计数阶段相当于 \(O(512\cdot 43089)\) 次简单兼容性检查，空间复杂度是 \(O(512+43089)\)。
更一般地，如果数字集合是 \(\{1,\dots,n\}\)，同样的方法会有 \(2^n\) 个记忆化状态，并枚举 \(\sum_{k=1}^{n} P(n,k)\) 个候选前缀。对 \(n=9\) 来说，这个固定规模完全足以让 exact cover 思路高效运行。
Нужно использовать цифры \(1,2,\dots,9\) ровно по одному разу, разбить их на несколько десятичных чисел и потребовать, чтобы каждое получившееся число было простым. Требуется посчитать количество таких множеств простых чисел. Поэтому \(\{23,461,5879\}\) и \(\{5879,23,461\}\) считаются одним и тем же решением: важен набор чисел, а не порядок их появления.
В лоб это выглядит как очень большой перебор. Любая упорядоченная строка из неповторяющихся цифр может стать одним блоком разбиения, а в конце такие блоки должны без пересечений покрыть всё множество \(\{1,\dots,9\}\). Реализации разбивают задачу на два слоя: сначала генерируют все простые числа, состоящие из различных цифр от \(1\) до \(9\), а затем считают точные покрытия множества цифр с помощью рекуррентной формулы с мемоизацией.
Главные математические объекты здесь - семейство допустимых простых блоков и рекурсия по множеству ещё не использованных цифр. После такой переформулировки задача превращается в небольшой exact-cover DP всего на \(2^9\) состояниях.
Обозначим через \(\mathcal{P}\) множество всех простых чисел, чья десятичная запись использует различные цифры из \(\{1,\dots,9\}\). Для каждого \(p\in\mathcal{P}\) обозначим через \(D(p)\subseteq\{1,\dots,9\}\) множество цифр, входящих в запись числа \(p\).
Тогда любое допустимое pandigital prime set есть набор \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\), для которого выполняется
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}.$$
Иными словами, исходная задача эквивалентна подсчёту всех точных покрытий множества цифр элементами \(\mathcal{P}\), чьи наборы цифр попарно не пересекаются.
Рекурсивный генератор в реализациях строит \(\mathcal{P}\) напрямую: он стартует с пустой строки, на каждом шаге дописывает справа ещё не использованную цифру и сохраняет текущий префикс как допустимый блок, если тот прост. Поскольку каждая упорядоченная последовательность различных цифр возникает в дереве поиска ровно один раз, каждый возможный простой блок тоже появляется ровно один раз.
Для любого подмножества \(S\subseteq\{1,\dots,9\}\) определим \(F(S)\) как число pandigital prime set, использующих ровно цифры из \(S\). Нас интересует \(F(\{1,\dots,9\})\). Для пустого множества естественно положить
$$F(\varnothing)=1,$$
потому что покрыть пустое множество можно ровно одним способом: больше ничего не выбирать.
Теперь пусть \(m(S)=\min S\), то есть наименьшая ещё не покрытая цифра. В любом корректном разбиении множества \(S\) существует ровно один простой блок, содержащий эту цифру. Отсюда следует рекурсия
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
Именно это инвариантное правило лежит в основе кода. Устранение повторного счёта достигается не сортировкой простых по величине, а выбором единственного блока, содержащего минимальную ещё свободную цифру. В битовой реализации этому соответствует младший установленный бит.
Пусть корректное решение равно \(\{p_1,\dots,p_r\}\). Если бы следующий блок можно было выбирать в произвольном порядке, то один и тот же набор появился бы в \(r!\) разных порядках. Правило якоря полностью устраняет эту проблему. На верхнем уровне выбранный блок обязан содержать цифру \(1\). После его удаления следующий блок обязан содержать наименьшую из ещё не использованных цифр, и так далее.
Поэтому каждому допустимому множеству соответствует ровно один путь в рекурсии, а каждый путь однозначно восстанавливает допустимое множество попарно непересекающихся по цифрам простых чисел. Это и даёт биекцию между решениями и рекурсивными путями.
Генератор посещает каждую непустую упорядоченную строку из различных цифр от \(1\) до \(9\). Точное количество таких префиксов равно
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
Лишь малая часть из них проходит проверку на простоту; для полного случая остаётся 43089 допустимых простых блоков. Кроме того, ни один 9-значный кандидат не может быть простым, потому что сумма цифр любой перестановки \(1,\dots,9\) равна \(45\), а значит число делится на \(9\). После построения списка кандидатов фаза подсчёта имеет всего \(2^9=512\) состояний множества оставшихся цифр.
Малый пример на \(\{1,2,3,4\}\) уже показывает весь механизм. На верхнем уровне якорной цифрой служит \(1\), поэтому нужно рассматривать только те простые блоки, которые её содержат:
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
Первые два варианта оставляют множество \(\{2,4\}\), а у него нет простого покрытия, так что их вклад равен \(0\). Для остальных ветвей получаем
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
Здесь \(F(\{3\})=1\), \(F(\{2\})=1\), а
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
поскольку множество \(\{2,3\}\) можно покрыть либо двумя однозначными простыми, либо одним числом \(\{23\}\). Следовательно,
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
Эти девять множеств таковы: \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\) и \(\{4231\}\). Именно это значение \(9\) параметризованная реализация использует как контрольную проверку перед запуском полного случая для цифр от \(1\) до \(9\).
Реализации на C++, Python и Java сначала рекурсивно перебирают строки цифр. Стартовое состояние состоит из значения \(0\) и пустой маски использованных цифр. На каждом шаге справа дописывается ещё не использованная цифра, образуя новый десятичный префикс. Если этот префикс прост, реализация сохраняет пару из самого простого числа и маски цифр, использованных в нём. Поиск продолжается, потому что простой префикс всё ещё может быть расширен до более длинного простого числа за счёт оставшихся цифр.
После генерации список кандидатов нормализуется до уникальных пар. С математической точки зрения это просто конечное множество \(\mathcal{P}\) вместе с прикреплённым к каждому элементу множеством цифр \(D(p)\).
На втором этапе подмножества цифр заменяются 9-битными масками. Маска обозначает цифры, которые ещё нужно покрыть. Пустая маска возвращает \(1\). Для любой непустой маски код извлекает её младший установленный бит; это и есть наименьшая оставшаяся цифра. Затем перебираются все сохранённые простые блоки.
Блок учитывается только тогда, когда его маска цифр является подмножеством текущей маски и одновременно содержит якорный бит. Если оба условия выполнены, цифры этого блока удаляются из текущей маски, а число способов для остатка вычисляется рекурсивно. Значение мемоизируется по маске, так что каждое состояние решается один раз. Это прямое битовое воплощение рекурсии для \(F(S)\).
Версии на C++ и Java используют обычное пробное деление до \(\sqrt{n}\). Здесь этого достаточно, потому что любой кандидат меньше \(10^9\), то есть \(\sqrt{n}\lt 31623\). Версия на Python использует библиотечную проверку простоты, но окружающая комбинаторика и рекурсия по маскам во всех трёх языках одинаковы.
Фаза генерации кандидатов посещает ровно 986409 непустых цифровых префиксов. Если обозначить стоимость одной проверки простоты для чисел порядка \(x\) через \(T_{\mathrm{prime}}(x)\), то сложность генерации равна
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
При пробном делении в C++ и Java получаем \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\); в Python этот шаг передаётся библиотеке.
После этого у динамики всего 512 мемоизированных состояний. Список кандидатов содержит 43089 простых блоков, и каждое состояние линейно просматривает этот список, выполняя только постоянные по времени проверки совместимости масок. Значит, для полной задачи фаза подсчёта имеет вид \(O(512\cdot 43089)\) простых проверок, а память равна \(O(512+43089)\).
В более общем случае для множества цифр \(\{1,\dots,n\}\) тот же метод использует \(2^n\) состояний и перечисляет \(\sum_{k=1}^{n} P(n,k)\) кандидатных префиксов. При \(n=9\) такой фиксированный объём поиска делает подход exact cover вполне практичным.
المطلوب هو استعمال الأرقام \(1,2,\dots,9\) كلها مرة واحدة بالضبط، ثم تقسيمها إلى عدة أعداد عشرية مع اشتراط أن يكون كل عدد ناتج عددًا أوليًا. الهدف هو عد جميع المجموعات الممكنة من الأعداد الأولية. لذلك فإن \(\{23,461,5879\}\) و\(\{5879,23,461\}\) يمثلان الحل نفسه، لأننا نعد مجموعات لا ترتيبات.
إذا نظرنا إلى المسألة مباشرةً ففضاء البحث كبير جدًا. فكل سلسلة مرتبة من أرقام مختلفة قد تصلح كتلةً في هذا التقسيم، وفي النهاية يجب أن تغطي هذه الكتل مجموعة الأرقام \(\{1,\dots,9\}\) من دون أي تداخل. لهذا تفصل التطبيقات الحل إلى مرحلتين: أولًا توليد جميع الأعداد الأولية التي تتكون من أرقام مختلفة مأخوذة من \(1\) إلى \(9\)، ثم عد جميع التغطيات التامة لمجموعة الأرقام باستعمال علاقة عودية مع حفظ النتائج.
العنصران الحاسمان هنا هما: عائلة الكتل الأولية المسموح بها، والعلاقة العودية المعرفة على مجموعة الأرقام المتبقية. بعد هذه الصياغة تتحول المسألة كلها إلى برنامج ديناميكي صغير من نوع exact cover على \(2^9\) حالات فقط.
لنرمز بـ \(\mathcal{P}\) إلى مجموعة جميع الأعداد الأولية التي يكتب تمثيلها العشري بأرقام مختلفة مأخوذة من \(\{1,\dots,9\}\). ولكل \(p\in\mathcal{P}\)، نرمز بـ \(D(p)\subseteq\{1,\dots,9\}\) إلى مجموعة الأرقام التي تظهر في \(p\).
إذًا كل مجموعة أولية pandigital صالحة هي مجموعة \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) تحقق
$$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\}.$$
أي إن المسألة الأصلية تكافئ عد جميع التغطيات التامة لمجموعة الأرقام باستعمال عناصر من \(\mathcal{P}\) تكون مجموعات أرقامها متباينة فيما بينها.
المولد العودي الموجود في التطبيقات يبني \(\mathcal{P}\) مباشرةً: يبدأ من السلسلة الفارغة، ويضيف في كل خطوة رقمًا غير مستخدم إلى اليمين، وكلما كان البادئ الحالي عددًا أوليًا يُخزن على أنه كتلة صالحة. وبما أن كل تسلسل مرتب من أرقام مختلفة يظهر مرة واحدة فقط في شجرة البحث، فإن كل كتلة أولية ممكنة تظهر مرة واحدة أيضًا.
لكل مجموعة جزئية \(S\subseteq\{1,\dots,9\}\)، عرّف \(F(S)\) بأنه عدد مجموعات الأعداد الأولية التي تستعمل بالضبط الأرقام الموجودة في \(S\). المطلوب هو \(F(\{1,\dots,9\})\). أما الحالة الأساسية فهي
$$F(\varnothing)=1,$$
لأن هناك طريقة واحدة فقط لتغطية لا شيء: ألّا نختار أي عدد إضافي.
الآن ليكن \(m(S)=\min S\)، أي أصغر رقم لم يُغطَّ بعد. في أي تقسيم صالح للمجموعة \(S\)، توجد كتلة أولية واحدة بالضبط تحتوي هذا الرقم. ومن هنا نحصل على العلاقة
$$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$$
هذه هي الثابتة الأساسية التي يعتمد عليها الكود. إزالة العد المكرر لا تتم بفرض ترتيب عددي على الأعداد الأولية، بل بفرض اختيار الكتلة التي تحتوي أصغر رقم متبق في كل خطوة. وفي تمثيل الأقنعة الثنائية يقابل ذلك أقل بت مرفوع.
لنفرض أن الحل الصحيح هو المجموعة \(\{p_1,\dots,p_r\}\). لو سمحنا باختيار الكتلة التالية بحرية، لظهر نفس الحل في \(r!\) ترتيبات مختلفة. قاعدة المرساة تمنع هذا تمامًا. في المستوى الأول يجب أن تكون الكتلة المختارة هي الكتلة الوحيدة التي تحتوي الرقم \(1\). وبعد حذفها، يجب أن تكون الكتلة التالية هي الكتلة التي تحتوي أصغر رقم لم يُستخدم بعد، وهكذا.
وبذلك تحدد كل مجموعة صالحة مسارًا عوديًا وحيدًا، كما أن كل مسار يعيد بناء مجموعة صالحة واحدة من أعداد أولية متباينة في الأرقام. وهذا يثبت وجود تقابل واحد لواحد بين الحلول ومسارات البحث.
المولد يزور كل بادئة غير فارغة مكوّنة من أرقام مختلفة من \(1\) إلى \(9\). والعدد الدقيق لهذه البوادئ هو
$$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$$
جزء صغير فقط من هذه البوادئ ينجح في اختبار الأولية؛ وفي الحالة الكاملة تبقى 43089 كتلة أولية مرشحة. كذلك لا يمكن لأي مرشح من 9 خانات أن يكون أوليًا، لأن مجموع أرقام أي ترتيب للأرقام \(1,\dots,9\) يساوي \(45\)، وبالتالي فالعدد يقبل القسمة على \(9\). وبعد تثبيت قائمة المرشحين تصبح مرحلة العد محصورة في \(2^9=512\) حالة فقط للأرقام المتبقية.
المثال الأصغر على المجموعة \(\{1,2,3,4\}\) يوضح الآلية كاملة. في المستوى الأعلى يكون رقم المرساة هو \(1\)، لذا لا نحتاج إلا إلى الكتل الأولية التي تحتوي \(1\):
$$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$$
الخياران الأولان يتركان المجموعة \(\{2,4\}\)، وهذه لا تملك أي تغطية أولية، لذا إسهامهما يساوي \(0\). أما بقية الفروع فتعطي
$$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$$
وهنا \(F(\{3\})=1\)، و\(F(\{2\})=1\)، بينما
$$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$$
لأن \(\{2,3\}\) يمكن تغطيتها إما بالعددين الأحاديين \(\{2,3\}\) أو بالعدد الوحيد \(\{23\}\). إذن
$$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$$
والمجموعات التسع الناتجة هي \(\{2,3,41\}\)، و\(\{23,41\}\)، و\(\{3,241\}\)، و\(\{3,421\}\)، و\(\{2,431\}\)، و\(\{1423\}\)، و\(\{2143\}\)، و\(\{2341\}\)، و\(\{4231\}\). وهذه هي بالضبط قيمة التحقق الصغيرة التي تستعملها النسخة القابلة للضبط قبل الانتقال إلى الحالة الكاملة للأرقام من \(1\) إلى \(9\).
تبدأ تطبيقات C++ وPython وJava بتعداد سلاسل الأرقام بصورة عودية. تنطلق من القيمة \(0\) ومن قناع فارغ للأرقام المستخدمة. وفي كل خطوة تضيف رقمًا غير مستعمل إلى يمين القيمة الحالية لتكوين بادئة عشرية جديدة. فإذا كانت هذه البادئة عددًا أوليًا، تُخزن الشيفرة الزوج المكوَّن من قيمة العدد الأولي وقناع الأرقام التي يستعملها. ثم تستمر العودية، لأن البادئة الأولية قد تُمدد لاحقًا إلى عدد أولي أطول باستعمال أرقام أخرى غير مستخدمة.
بعد اكتمال التوليد، تُطبَّع قائمة المرشحين إلى أزواج فريدة قبل بدء العد. ومن الناحية الرياضية ليست هذه القائمة إلا المجموعة المنتهية \(\mathcal{P}\) مع مجموعة الأرقام \(D(p)\) الملحقة بكل عنصر فيها.
في المرحلة الثانية تُمثل المجموعات الجزئية للأرقام بأقنعة من 9 بتات. كل قناع يمثل الأرقام التي لا تزال بحاجة إلى تغطية. القناع الفارغ يعيد \(1\). ولأي قناع غير فارغ تستخرج الشيفرة أقل بت مرفوع فيه، وهو ما يقابل أصغر رقم متبق، ثم تمر على جميع الكتل الأولية المخزنة.
لا تسهم كتلة ما في الناتج إلا إذا كان قناع أرقامها مجموعة جزئية من القناع المتبقي، وإذا كانت تحتوي أيضًا بت المرساة. عند تحقق الشرطين تُزال أرقام هذه الكتلة من القناع المتبقي، ثم يُحسب عدد الطرق للباقي عوديًا. وتُحفظ النتيجة لكل قناع، لذلك لا تُحل أي حالة إلا مرة واحدة. وهذا هو التطبيق الثنائي المباشر للعلاقة الخاصة بـ \(F(S)\).
تعتمد نسختا C++ وJava على القسمة التجريبية حتى \(\sqrt{n}\). وهذا كاف تمامًا هنا لأن كل مرشح أصغر من \(10^9\)، وبالتالي \(\sqrt{n}\lt 31623\). أما نسخة Python فتستعمل روتينًا مكتبيًا لاختبار الأولية، لكن البنية التوافقية والعلاقة العودية على الأقنعة متماثلتان في اللغات الثلاث.
تمر مرحلة توليد المرشحين على 986409 بادئة رقمية غير فارغة بالضبط. وإذا رمزنا بكلفة اختبار أولية واحد لعدد من رتبة \(x\) إلى \(T_{\mathrm{prime}}(x)\)، فإن كلفة هذه المرحلة هي
$$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$$
ومع القسمة التجريبية نحصل في C++ وJava على \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\)، بينما تفوض Python هذه الخطوة إلى مكتبتها الخاصة.
بعد ذلك لا يبقى في البرنامج الديناميكي إلا 512 حالة محفوظة. تحتوي قائمة المرشحين على 43089 كتلة أولية، وكل حالة تفحص هذه القائمة باختبارات توافق ثابتة الزمن على الأقنعة. لذا فإن مرحلة العد في الحالة الكاملة تساوي \(O(512\cdot 43089)\) من الفحوص البسيطة، مع ذاكرة \(O(512+43089)\).
وبصورة أعم، لو كانت مجموعة الأرقام هي \(\{1,\dots,n\}\)، فإن الطريقة نفسها ستستخدم \(2^n\) حالات محفوظة وتولد \(\sum_{k=1}^{n} P(n,k)\) بادئة مرشحة. وعند \(n=9\) يكون هذا الحجم الثابت صغيرًا بما يكفي لجعل منهج exact cover عمليًا جدًا.