Project Euler 178 asks for the number of step numbers below \(10^{40}\) that are pandigital, meaning that every digit \(0,1,\dots,9\) appears at least once. A step number is a positive decimal integer whose adjacent digits differ by exactly 1, so every valid number traces a walk such as \(45654\) or \(1234567890\) along the digit line.
Because the bound is \(10^{40}\), we must count all valid lengths from 1 through 40, not only 40-digit numbers. Leading zero is forbidden, and any number with fewer than 10 digits is automatically too short to be pandigital, but the dynamic program can treat all lengths uniformly.
The natural model is to view the digits as the vertices of the path graph
$$0-1-2-3-4-5-6-7-8-9.$$
A step number of length \(\ell\) is exactly a walk of \(\ell-1\) edges on this graph, starting from one of the vertices \(1,\dots,9\). The step condition itself is easy; the real issue is remembering which digits have already appeared so that we know when the walk has become pandigital.
Let \(M\subseteq\{0,1,\dots,9\}\) be the set of digits seen so far, and let \(d\) be the last digit. Define
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
The invariant is exact: every legal prefix belongs to one and only one state, determined by its length, its final digit, and the set of distinct digits already visited. In the implementations, the set \(M\) is encoded by a 10-bit mask, so adding a new digit is just setting one more bit.
At length 1, the only allowed starting digits are \(1,2,\dots,9\). Therefore
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
and all other states with \(\ell=1\) are zero. In particular, there is no initial state ending in \(0\), because that would represent a leading zero.
The path-graph viewpoint also explains the edge cases immediately. Digit \(0\) can only move to \(1\), digit \(9\) can only move to \(8\), and each interior digit \(1,\dots,8\) has exactly two possible continuations.
Suppose a prefix is in state \((\ell,M,d)\). The next digit must be a neighbor of \(d\), so each valid extension goes to one of the states
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
This recurrence is exact rather than heuristic. Every step number of length \(\ell+1\) has a unique prefix of length \(\ell\), so the transition neither misses any object nor counts any object twice.
Let
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
A number contributes to the answer precisely when its visited set is \(M_{\mathrm{all}}\). Since the problem asks for all step numbers below \(10^{40}\), the required total is
$$\text{Answer}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
Lengths below 10 contribute zero automatically, because no 9-digit number can contain all ten decimal digits. Keeping those lengths in the summation makes the formulation cleaner and matches the implementations exactly.
Consider the prefix \(45654\). It is a step number because all adjacent differences are 1. Its state is
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
From there the next digit can only be \(3\) or \(5\). Appending \(3\) produces \(456543\), which moves to \((6,\{3,4,5,6\},3)\); appending \(5\) produces \(456545\), which moves to \((6,\{4,5,6\},5)\). This is exactly why both pieces of information are necessary: the last digit determines the legal next move, while the visited set determines whether the number is already pandigital.
At the other extreme, numbers such as \(1234567890\) and \(9876543210\) already have \(M_{\mathrm{all}}\) at length 10, so they are immediate contributors to the final total.
The C++, Python, and Java implementations all realize this same three-dimensional dynamic program. They allocate a table indexed by length, visited-digit mask, and final digit, and they seed the nine legal one-digit starting states.
The table is filled in increasing order of length. Whenever a state count is zero, the implementation skips it. Otherwise it forwards that count to the next layer, once to \(d-1\) if \(d>0\) and once to \(d+1\) if \(d<9\), while updating the visited-digit mask.
Because the digit graph is just a line, each state has at most two outgoing transitions, and the endpoints have only one. That is why the full computation up to 40 digits is completely practical once the digit set is compressed into a bitmask.
After all layers have been filled, the implementation scans every length from 1 through 40 and adds the counts whose mask has all ten bits set. Summing over all end digits is necessary because the problem does not prescribe the final digit.
The implementations use ordinary integer arithmetic rather than modular arithmetic: the goal is the exact count, and the 40-digit limit keeps the total within 64-bit range.
The C++ implementation includes an additional checkpoint for a small digit bound: it brute-forces all step-number walks by depth-first search and confirms that the total agrees with the dynamic program. The Python and Java implementations keep the same DP core but omit that explicit cross-check layer.
There are \(40\) possible lengths, \(2^{10}=1024\) possible visited-digit sets, and \(10\) possible final digits, so the total number of DP states is
$$40\cdot 2^{10}\cdot 10=409{,}600.$$
Each state generates at most two transitions. Therefore the running time is \(O(N\cdot 2^{10}\cdot 10)\) for a general upper bound \(N\), and with \(N=40\) the computation is very small.
The current implementations store every length layer, so the memory usage is also \(O(N\cdot 2^{10}\cdot 10)\). A rolling-array variant could reduce that to \(O(2^{10}\cdot 10)\), but the larger table is still tiny and keeps the code straightforward.
Project Euler 178 fragt nach der Anzahl der Step Numbers kleiner als \(10^{40}\), die pandigital sind, also jede Ziffer \(0,1,\dots,9\) mindestens einmal enthalten. Eine Step Number ist eine positive Dezimalzahl, bei der sich benachbarte Ziffern immer um genau 1 unterscheiden.
Wegen der Schranke \(10^{40}\) müssen alle Längen von 1 bis 40 berücksichtigt werden, nicht nur Zahlen mit genau 40 Stellen. Führende Nullen sind verboten, und jede Zahl mit weniger als 10 Stellen ist automatisch zu kurz, um alle zehn Ziffern zu enthalten. Trotzdem lässt sich alles in einer einheitlichen dynamischen Programmierung erfassen.
Am klarsten wird das Problem, wenn man die Ziffern als Knoten des Pfadgraphen
$$0-1-2-3-4-5-6-7-8-9$$
auffasst. Eine Step Number der Länge \(\ell\) ist dann genau ein Weg mit \(\ell-1\) Kanten auf diesem Graphen, beginnend bei einem der Startknoten \(1,\dots,9\). Die Schrittbedingung selbst ist einfach; schwierig ist nur, mitzuschreiben, welche Ziffern bereits gesehen wurden.
Sei \(M\subseteq\{0,1,\dots,9\}\) die bisher besuchte Ziffernmenge und \(d\) die Endziffer. Definiere
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
Das ist eine exakte Zustandsbeschreibung: Jedes gültige Präfix gehört zu genau einem Zustand, bestimmt durch Länge, letzte Ziffer und die Menge der bisher vorkommenden Ziffern. In den Implementierungen wird \(M\) als 10-Bit-Maske kodiert; eine neue Ziffer hinzuzunehmen bedeutet also nur, ein weiteres Bit zu setzen.
Für Länge 1 sind nur die Startziffern \(1,2,\dots,9\) erlaubt. Also gilt
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
während alle anderen Zustände mit \(\ell=1\) gleich null sind. Insbesondere existiert kein Startzustand mit Endziffer \(0\), weil das einer führenden Null entspräche.
Der Pfadgraph zeigt auch sofort die Randfälle: Von \(0\) kann man nur nach \(1\) gehen, von \(9\) nur nach \(8\), und jede innere Ziffer \(1,\dots,8\) besitzt genau zwei mögliche Fortsetzungen.
Befindet sich ein Präfix im Zustand \((\ell,M,d)\), dann muss die nächste Ziffer ein Nachbar von \(d\) sein. Jede erlaubte Verlängerung landet also in einem der Zustände
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
Diese Rekurrenz ist exakt. Jede Step Number der Länge \(\ell+1\) hat genau ein Präfix der Länge \(\ell\), daher wird nichts vergessen und nichts doppelt gezählt.
Setze
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
Zur gesuchten Summe tragen genau die Zustände bei, deren besuchte Menge \(M_{\mathrm{all}}\) ist. Weil alle Zahlen unter \(10^{40}\) gemeint sind, lautet die Gesamtzahl
$$\text{Antwort}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
Längen unter 10 liefern automatisch keinen Beitrag, da keine 9-stellige Zahl alle zehn Dezimalziffern enthalten kann. Die Summenformel bleibt trotzdem sauber und stimmt genau mit dem Programm überein.
Betrachte das Präfix \(45654\). Es ist eine Step Number, weil jede benachbarte Differenz gleich 1 ist. Der zugehörige Zustand lautet
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
Als nächste Ziffer sind nur \(3\) oder \(5\) möglich. Durch Anhängen von \(3\) entsteht \(456543\), also der Zustand \((6,\{3,4,5,6\},3)\); durch Anhängen von \(5\) entsteht \(456545\), also \((6,\{4,5,6\},5)\). Genau daran sieht man, warum sowohl die letzte Ziffer als auch die besuchte Ziffernmenge gespeichert werden müssen.
Am anderen Ende stehen Zahlen wie \(1234567890\) und \(9876543210\): Sie erreichen bereits bei Länge 10 die volle Menge \(M_{\mathrm{all}}\) und zählen deshalb sofort zum Ergebnis.
Die C++-, Python- und Java-Implementierungen setzen genau diese dreidimensionale dynamische Programmierung um. Sie legen eine Tabelle mit Indizes für Länge, Bitmaske der besuchten Ziffern und Endziffer an und initialisieren die neun gültigen Startzustände der Länge 1.
Die Tabelle wird in aufsteigender Länge gefüllt. Zustände mit Wert null werden übersprungen. Andernfalls wird die aktuelle Anzahl in die nächste Längenschicht weitergereicht: einmal nach \(d-1\), falls \(d>0\), und einmal nach \(d+1\), falls \(d<9\). Gleichzeitig wird die Bitmaske um die neue Ziffer erweitert.
Weil der Zifferngraph nur ein Pfad ist, hat jeder Zustand höchstens zwei ausgehende Übergänge, an den Rändern sogar nur einen. Genau deshalb ist die vollständige Rechnung bis 40 Stellen nach der Bitmaskenkompression sehr klein.
Nach dem Füllen aller Schichten durchsucht die Implementierung jede Länge von 1 bis 40 und addiert die Zustände, deren Maske alle zehn Bits gesetzt hat. Über alle Endziffern muss summiert werden, weil das Problem die letzte Ziffer nicht festlegt.
Die Implementierungen arbeiten mit gewöhnlicher Ganzzahlarithmetik statt mit modularer Arithmetik: Gesucht ist die exakte Anzahl, und für die Grenze 40 genügt ein 64-Bit-Typ.
Die C++-Implementierung enthält zusätzlich einen Kontrollpunkt für eine kleine Stellenzahl: Dort werden alle Step-Number-Wege per Tiefensuche explizit erzeugt, und das Ergebnis wird mit der DP verglichen. Die Python- und Java-Implementierungen verwenden denselben DP-Kern, verzichten aber auf diese separate Gegenprüfung.
Es gibt \(40\) mögliche Längen, \(2^{10}=1024\) mögliche Ziffernmengen und \(10\) mögliche Endziffern. Damit umfasst der Zustandsraum insgesamt
$$40\cdot 2^{10}\cdot 10=409{,}600$$
Zustände. Jeder Zustand erzeugt höchstens zwei Übergänge, also beträgt die Laufzeit für eine allgemeine Obergrenze \(N\) gleich \(O(N\cdot 2^{10}\cdot 10)\). Für \(N=40\) ist das sehr klein.
Die vorhandenen Implementierungen speichern alle Längenschichten gleichzeitig, daher ist auch der Speicherbedarf \(O(N\cdot 2^{10}\cdot 10)\). Mit Rolling Arrays könnte man auf \(O(2^{10}\cdot 10)\) reduzieren, aber die größere Tabelle bleibt klein und vereinfacht den Code.
Project Euler 178, \(10^{40}\)'tan küçük pandigital step number sayılarını ister. Burada step number, ardışık iki basamağı arasındaki fark tam olarak 1 olan pozitif bir onluk sayıdır; pandigital ise \(0,1,\dots,9\) rakamlarının hepsinin en az bir kez görülmesi anlamına gelir.
Üst sınır \(10^{40}\) olduğu için yalnızca 40 basamaklı sayıları değil, 1 ile 40 arasındaki bütün uzunlukları saymak gerekir. Baştaki rakam \(0\) olamaz. Ayrıca 10 basamaktan kısa hiçbir sayı bütün rakamları içeremez, ancak dinamik program bu durumu ayrı bir özel duruma dönüştürmeden doğal biçimde ele alır.
Problemi en temiz biçimde görmek için rakamları şu yol grafiğinin düğümleri gibi düşünelim:
$$0-1-2-3-4-5-6-7-8-9.$$
Uzunluğu \(\ell\) olan bir step number, bu graf üzerinde \(\ell-1\) kenarlı bir yürüyüştür ve başlangıç düğümü \(1,\dots,9\) arasından seçilir. Asıl zorluk adım kuralı değil, bu yürüyüş boyunca hangi rakamların görüldüğünü unutmamaktır.
\(M\subseteq\{0,1,\dots,9\}\) şimdiye kadar görülmüş rakamlar kümesi, \(d\) ise son rakam olsun. Şu sayıyı tanımlayalım:
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
Bu tanım tam bir durum değişmezidir: Geçerli her ön ek, uzunluğu, son rakamı ve gördüğü farklı rakamlar kümesi tarafından tek bir duruma yerleşir. Uygulamalarda \(M\) kümesi 10 bitlik bir maske ile tutulur; yeni bir rakam eklemek yalnızca ilgili biti 1 yapmak demektir.
Uzunluk 1 için izin verilen başlangıç rakamları yalnızca \(1,2,\dots,9\)'dur. Dolayısıyla
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
ve \(\ell=1\) için diğer bütün durumlar sıfırdır. Özellikle \(0\) ile başlayan bir durum yoktur; çünkü bu, başta sıfır bulunan geçersiz bir onluk gösterim olur.
Yol grafiği sınır durumlarını da hemen açıklar. \(0\) yalnızca \(1\)'e gidebilir, \(9\) yalnızca \(8\)'e gidebilir; içteki her rakam \(1,\dots,8\) ise iki farklı devam seçeneğine sahiptir.
Bir ön ek \((\ell,M,d)\) durumundaysa, sıradaki rakam ancak \(d\)'nin komşularından biri olabilir. Bu yüzden her geçerli uzatma aşağıdaki durumlardan birine gider:
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
Bu bağıntı yaklaşık değil, birebirdir. Uzunluğu \(\ell+1\) olan her step number'ın tek bir uzunluk-\(\ell\) ön eki vardır; dolayısıyla ne eksik sayım ne de çift sayım oluşur.
Şimdi
$$M_{\mathrm{all}}=\{0,1,\dots,9\}$$
olsun. Bir sayı ancak gördüğü rakamlar kümesi \(M_{\mathrm{all}}\) olduğunda cevaba katkı yapar. Problem \(10^{40}\)'tan küçük bütün sayıları istediği için toplam
$$\text{Cevap}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d)$$
şeklindedir. 10'dan kısa uzunluklar otomatik olarak sıfır katkı verir; çünkü 9 basamaklı bir sayı on farklı rakamın tamamını içeremez. Buna rağmen formülü tüm uzunluklarda aynı bırakmak hem temizdir hem de kodun yaptığı şeyle aynıdır.
\(45654\) ön ekini düşünelim. Bu bir step number'dır; çünkü yan yana her iki basamak arasındaki fark 1'dir. İlgili durum
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}$$
olur. Buradan sonra yalnızca \(3\) veya \(5\) gelebilir. \(3\) eklenirse \(456543\) elde edilir ve durum \((6,\{3,4,5,6\},3)\) olur; \(5\) eklenirse \(456545\) elde edilir ve durum \((6,\{4,5,6\},5)\) olur. Bu küçük örnek, neden hem son rakamın hem de ziyaret edilmiş rakamlar kümesinin saklanması gerektiğini açık biçimde gösterir.
Diğer uçta \(1234567890\) ve \(9876543210\) gibi sayılar daha uzunluğun 10. adımında \(M_{\mathrm{all}}\)'e ulaşır; bu yüzden nihai toplama doğrudan katkı yaparlar.
C++, Python ve Java uygulamaları tam olarak bu üç boyutlu dinamik programı gerçekleştirir. Uzunluk, ziyaret-maskesi ve son rakama göre indekslenen bir tablo oluştururlar ve tek basamaklı dokuz geçerli başlangıç durumunu yerleştirirler.
Tablo uzunluk arttıkça doldurulur. Bir durumun sayısı sıfırsa o durum geçilir. Aksi halde bu sayı bir sonraki katmana aktarılır: \(d>0\) ise \(d-1\)'e, \(d<9\) ise \(d+1\)'e. Aynı anda ziyaret-maskesine yeni rakam da eklenir.
Rakam grafiği yalnızca bir doğru olduğundan her durumun en fazla iki çıkışı vardır; uç rakamlarda ise bu sayı bire düşer. Bitmask sıkıştırmasıyla birleşince bu yapı, 40 basamağa kadar tam sayımı son derece hafif hale getirir.
Bütün katmanlar doldurulduktan sonra uygulama 1'den 40'a kadar her uzunluğu dolaşır ve maskesi on bitin tamamını içeren durumları toplar. Son rakam sabit olmadığı için \(d=0,\dots,9\) üzerindeki toplam zorunludur.
Burada modüler aritmetik kullanılmaz; amaç tam sayıyı hesaplamaktır ve 40 basamak sınırında sonuç 64 bitlik tamsayı aralığında kalır.
C++ uygulaması küçük bir basamak sınırı için ek bir kontrol daha yapar: derinlik öncelikli arama ile bütün step-number yürüyüşlerini kaba kuvvetle üretir ve bu toplamı dinamik programın verdiği sonuçla karşılaştırır. Python ve Java uygulamaları ise aynı DP çekirdeğini koruyup bu ek doğrulama katmanını içermez.
\(40\) farklı uzunluk, \(2^{10}=1024\) farklı rakam kümesi ve \(10\) farklı son rakam vardır. Yani toplam durum sayısı
$$40\cdot 2^{10}\cdot 10=409{,}600$$
olur. Her durum en fazla iki geçiş üretir. Bu nedenle genel bir üst sınır \(N\) için zaman karmaşıklığı \(O(N\cdot 2^{10}\cdot 10)\) düzeyindedir; \(N=40\) için bu maliyet çok küçüktür.
Mevcut uygulamalar bütün uzunluk katmanlarını sakladığından bellek karmaşıklığı da \(O(N\cdot 2^{10}\cdot 10)\)'dur. İstenirse dönen iki katmanla \(O(2^{10}\cdot 10)\)'a inmek mümkündür; ancak mevcut tablo zaten küçüktür ve kodu daha okunur tutar.
Project Euler 178 pide contar los step numbers menores que \(10^{40}\) que además sean pandigitales, es decir, que contengan todos los dígitos \(0,1,\dots,9\) al menos una vez. Un step number es un entero decimal positivo en el que la diferencia entre dos dígitos consecutivos es exactamente 1.
Como la cota es \(10^{40}\), hay que considerar todas las longitudes entre 1 y 40, no solo las de 40 cifras. El primer dígito no puede ser \(0\), y cualquier número con menos de 10 cifras es demasiado corto para contener los diez dígitos, pero la programación dinámica puede manejar todas las longitudes con la misma fórmula.
La forma más clara de ver el problema es interpretar los dígitos como los vértices del grafo camino
$$0-1-2-3-4-5-6-7-8-9.$$
Entonces un step number de longitud \(\ell\) es exactamente un recorrido de \(\ell-1\) aristas sobre ese grafo, comenzando en uno de los vértices \(1,\dots,9\). La restricción de diferencia 1 es local y sencilla; lo difícil es recordar qué dígitos ya aparecieron.
Sea \(M\subseteq\{0,1,\dots,9\}\) el conjunto de dígitos ya vistos y sea \(d\) el último dígito. Definimos
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
El invariante es exacto: cada prefijo válido cae en un único estado, determinado por su longitud, su dígito final y el conjunto de dígitos distintos que ya aparecieron. En la implementación, el conjunto \(M\) se codifica como una máscara de 10 bits, así que añadir un dígito nuevo equivale a activar un bit.
Para longitud 1, los únicos comienzos permitidos son \(1,2,\dots,9\). Por tanto,
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
mientras que todos los demás estados con \(\ell=1\) valen cero. En particular, no existe un estado inicial con último dígito \(0\), porque eso representaría un cero a la izquierda.
El modelo del grafo camino también aclara los extremos. El dígito \(0\) solo puede pasar a \(1\), el dígito \(9\) solo puede pasar a \(8\), y cualquier dígito interior \(1,\dots,8\) tiene exactamente dos continuaciones posibles.
Si un prefijo está en el estado \((\ell,M,d)\), el siguiente dígito debe ser un vecino de \(d\). Por eso, cada extensión válida conduce a uno de los estados
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
La recurrencia es exacta. Todo step number de longitud \(\ell+1\) tiene un prefijo único de longitud \(\ell\), así que no hay pérdidas ni doble conteo.
Sea
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
Un número aporta al resultado exactamente cuando su conjunto visitado es \(M_{\mathrm{all}}\). Como el problema pide todos los números menores que \(10^{40}\), la cantidad buscada es
$$\text{Respuesta}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
Las longitudes menores que 10 aportan cero de forma automática, porque ningún número de 9 cifras puede contener los diez dígitos decimales. Mantenerlas dentro de la suma hace la formulación más limpia y coincide exactamente con las implementaciones.
Tomemos el prefijo \(45654\). Es un step number porque todas las diferencias entre cifras consecutivas son 1. Su estado es
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
Desde ahí, el siguiente dígito solo puede ser \(3\) o \(5\). Si añadimos \(3\), obtenemos \(456543\), que pasa al estado \((6,\{3,4,5,6\},3)\); si añadimos \(5\), obtenemos \(456545\), que pasa a \((6,\{4,5,6\},5)\). Este ejemplo muestra por qué hace falta guardar tanto el último dígito como el conjunto visitado.
En el otro extremo, números como \(1234567890\) y \(9876543210\) ya alcanzan \(M_{\mathrm{all}}\) en longitud 10, así que contribuyen inmediatamente a la suma final.
Las implementaciones en C++, Python y Java materializan exactamente esta programación dinámica tridimensional. Reservan una tabla indexada por longitud, máscara de dígitos visitados y dígito final, e inicializan los nueve estados legales de una sola cifra.
La tabla se rellena por longitudes crecientes. Cuando un estado tiene valor cero, se omite. En caso contrario, su conteo se propaga a la capa siguiente: una vez hacia \(d-1\) si \(d>0\) y una vez hacia \(d+1\) si \(d<9\), actualizando al mismo tiempo la máscara visitada.
Como el grafo de dígitos es simplemente una línea, cada estado tiene a lo sumo dos transiciones salientes, y los extremos solo una. Esa es la razón de que el cálculo completo hasta 40 cifras sea perfectamente factible.
Una vez llenas todas las capas, la implementación recorre cada longitud entre 1 y 40 y suma los estados cuya máscara tiene los diez bits activados. Hay que sumar sobre todos los dígitos finales porque el problema no fija la última cifra.
Las implementaciones usan aritmética entera ordinaria, no aritmética modular: aquí se necesita la cuenta exacta y el límite de 40 cifras mantiene el resultado dentro del rango de 64 bits.
La implementación en C++ añade una comprobación extra para una cota pequeña de dígitos: enumera por fuerza bruta todos los recorridos válidos mediante búsqueda en profundidad y confirma que el total coincide con la programación dinámica. Las versiones en Python y Java conservan el mismo núcleo DP, pero sin esa capa explícita de contraste.
Hay \(40\) longitudes posibles, \(2^{10}=1024\) conjuntos posibles de dígitos visitados y \(10\) posibles dígitos finales. Por tanto, el espacio total de estados es
$$40\cdot 2^{10}\cdot 10=409{,}600.$$
Cada estado genera como máximo dos transiciones. En consecuencia, el tiempo de ejecución es \(O(N\cdot 2^{10}\cdot 10)\) para una cota general \(N\), y con \(N=40\) el coste es muy pequeño.
Las implementaciones actuales almacenan todas las capas de longitud, así que la memoria también es \(O(N\cdot 2^{10}\cdot 10)\). Se podría comprimir a \(O(2^{10}\cdot 10)\) con un arreglo rodante, pero la tabla completa sigue siendo pequeña y simplifica el código.
Project Euler 178 要求统计所有小于 \(10^{40}\) 的 pandigital step number。这里的 step number 指相邻两位数字之差恰好为 1 的正十进制整数；pandigital 则表示十个数字 \(0,1,\dots,9\) 都至少出现过一次。
由于上界是 \(10^{40}\)，我们必须统计 1 位数到 40 位数之间的全部合法长度，而不是只看 40 位。首位不能是 \(0\)。另外，位数小于 10 的数字不可能覆盖全部十个数字，不过动态规划可以把这些长度自然地包含在统一公式里，它们会自动贡献 0。
最自然的建模方式，是把数字看成下面这条路径图上的顶点：
$$0-1-2-3-4-5-6-7-8-9.$$
于是，一个长度为 \(\ell\) 的 step number，就等价于在这张图上走了 \(\ell-1\) 条边的一个步行序列，起点必须在 \(1,\dots,9\) 之中。相邻差为 1 的条件本身并不复杂，真正需要额外记录的是：到目前为止哪些数字已经出现过。
设 \(M\subseteq\{0,1,\dots,9\}\) 是已经出现过的数字集合，\(d\) 是当前最后一位数字。定义
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
这个定义给出了精确的不变量：每一个合法前缀，都恰好落在一个状态里，而这个状态完全由三个信息决定，分别是长度、末位数字，以及目前为止出现过的不同数字集合。实现中把集合 \(M\) 编码成 10 位二进制掩码，因此“把一个新数字加入集合”就只是把对应的那一位设为 1。
当长度为 1 时，唯一允许的起始数字是 \(1,2,\dots,9\)。因此
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
而其他所有 \(\ell=1\) 的状态都为 0。尤其不能有以 \(0\) 结尾的初始状态，因为那意味着前导零。
路径图模型还把边界情况说得很清楚。数字 \(0\) 只有一个相邻点 \(1\)，数字 \(9\) 只有一个相邻点 \(8\)，而中间的数字 \(1,\dots,8\) 都有两个可能的后继。
如果某个前缀处在状态 \((\ell,M,d)\)，那么下一位只能是 \(d\) 的邻居。所以，每一种合法延伸都落到下面两个状态之一：
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
这个递推不是经验性的，而是严格正确的。任意一个长度为 \(\ell+1\) 的 step number，删去最后一位之后都会得到唯一的长度为 \(\ell\) 的前缀，所以不会漏计，也不会重计。
记
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
只有当访问到的数字集合正好是 \(M_{\mathrm{all}}\) 时，这个数才对答案有贡献。由于题目要求的是所有小于 \(10^{40}\) 的 step number，总数就是
$$\text{Answer}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
长度小于 10 的部分会自动给出 0，因为 9 位数不可能包含全部十个十进制数字。把这些长度也保留在求和式中，可以让表达式更整洁，而且与实现完全一致。
考虑前缀 \(45654\)。它是一个 step number，因为每一对相邻数字之差都等于 1。它对应的状态是
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
接下来只能补上 \(3\) 或 \(5\)。如果补 \(3\)，得到 \(456543\)，新状态是 \((6,\{3,4,5,6\},3)\)；如果补 \(5\)，得到 \(456545\)，新状态是 \((6,\{4,5,6\},5)\)。这个小例子清楚说明了为什么必须同时记录“最后一位是什么”和“已经出现过哪些数字”这两部分信息。
而像 \(1234567890\) 和 \(9876543210\) 这样的数，在长度 10 时就已经达到了完整集合 \(M_{\mathrm{all}}\)，因此会立刻计入最终答案。
C++、Python 和 Java 的实现都严格对应这个三维动态规划。它们分配一个按长度、访问掩码和末位数字索引的表，并先放入 9 个合法的一位起始状态。
表按长度递增的顺序填充。某个状态的计数如果为 0，就直接跳过。否则，就把这个计数向下一层传播：若 \(d>0\)，传播到 \(d-1\)；若 \(d<9\)，传播到 \(d+1\)。同时更新访问掩码，把新数字对应的位设置为 1。
因为数字图只是一条长度为 10 的路径，所以每个状态最多只有两个出边，两个端点甚至只有一个。这也是为什么在加入位掩码压缩之后，把所有长度做到 40 仍然非常轻量。
所有层都填完后，实现会遍历从 1 到 40 的每个长度，把掩码中十位全部为 1 的状态累加起来。还需要对所有末位数字 \(0,\dots,9\) 求和，因为题目并没有限制最后一位必须是什么。
这里使用的是普通整数运算，而不是模运算；题目要的是精确计数，而且在 40 位的范围内，总结果仍然落在 64 位整数可承受的范围里。
C++ 实现额外加入了一个小规模校验：在较小的位数上，用深度优先搜索枚举所有 step-number 路径，再把暴力得到的总数和动态规划的结果进行比较。Python 与 Java 版本保留了同样的 DP 主体，但没有写出这一层显式交叉验证。
长度一共有 \(40\) 种可能，访问集合一共有 \(2^{10}=1024\) 种可能，末位数字一共有 \(10\) 种可能，因此总状态数为
$$40\cdot 2^{10}\cdot 10=409{,}600.$$
每个状态最多产生两次转移，所以一般上界 \(N\) 下的时间复杂度是 \(O(N\cdot 2^{10}\cdot 10)\)。对本题的 \(N=40\) 来说，这个规模非常小。
当前实现把所有长度层都保存下来，因此空间复杂度同样是 \(O(N\cdot 2^{10}\cdot 10)\)。如果愿意，也可以只保留相邻两层，把空间压缩到 \(O(2^{10}\cdot 10)\)，不过现有表已经足够小，而且代码更直观。
Project Euler 178 требует посчитать все pandigital step numbers, меньшие \(10^{40}\). Step number в этой задаче - это положительное десятичное число, у которого разность любых двух соседних цифр равна ровно 1. Слово pandigital означает, что каждая цифра \(0,1,\dots,9\) встречается хотя бы один раз.
Поскольку верхняя граница равна \(10^{40}\), нужно учитывать все длины от 1 до 40, а не только числа ровно из 40 цифр. Ведущий ноль запрещен. Кроме того, число короче 10 цифр заведомо не может содержать все десять цифр, но динамика может рассматривать и эти длины без специальных исключений.
Удобнее всего смотреть на цифры как на вершины графа-пути
$$0-1-2-3-4-5-6-7-8-9.$$
Тогда step number длины \(\ell\) - это просто маршрут длины \(\ell-1\) по этому графу, начинающийся в одной из вершин \(1,\dots,9\). Условие шага локально и очень простое; основная трудность в том, чтобы помнить, какие цифры уже были посещены.
Пусть \(M\subseteq\{0,1,\dots,9\}\) - множество уже встреченных цифр, а \(d\) - последняя цифра. Определим
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
Это точный инвариант состояния: каждый допустимый префикс попадает ровно в одно состояние, которое определяется его длиной, последней цифрой и множеством различных цифр, уже встретившихся в записи. В реализации множество \(M\) кодируется 10-битной маской, поэтому добавление новой цифры сводится к установке одного бита.
При длине 1 допустимы только стартовые цифры \(1,2,\dots,9\). Поэтому
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
а все остальные состояния с \(\ell=1\) равны нулю. В частности, не существует начального состояния с цифрой \(0\), поскольку это означало бы ведущий ноль.
Модель графа-пути сразу показывает и крайние случаи. Из \(0\) можно перейти только в \(1\), из \(9\) только в \(8\), а каждая внутренняя цифра \(1,\dots,8\) имеет ровно два возможных продолжения.
Если префикс находится в состоянии \((\ell,M,d)\), следующая цифра обязана быть соседом \(d\). Значит, каждое допустимое продолжение попадает в одно из состояний
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
Этот переход точен. У любого step number длины \(\ell+1\) есть единственный префикс длины \(\ell\), поэтому здесь нет ни пропусков, ни двойного счета.
Обозначим
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
Число дает вклад в ответ тогда и только тогда, когда посещенное множество равно \(M_{\mathrm{all}}\). Поскольку нужны все числа меньше \(10^{40}\), итоговая формула имеет вид
$$\text{Ответ}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
Длины меньше 10 автоматически дают нулевой вклад, потому что 9-значное число не может содержать все десять цифр. Тем не менее включать эти длины в общую сумму удобно и полностью соответствует программе.
Рассмотрим префикс \(45654\). Это step number, потому что разности соседних цифр равны 1. Его состояние равно
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
Следующей цифрой может быть только \(3\) или \(5\). Если дописать \(3\), получится \(456543\), то есть новое состояние \((6,\{3,4,5,6\},3)\); если дописать \(5\), получится \(456545\), то есть состояние \((6,\{4,5,6\},5)\). Этот пример показывает, почему нужно хранить и последнюю цифру, и множество уже увиденных цифр.
С другой стороны, числа вроде \(1234567890\) и \(9876543210\) достигают полного множества \(M_{\mathrm{all}}\) уже при длине 10 и сразу попадают в итоговую сумму.
Реализации на C++, Python и Java строят именно эту трехмерную динамику. Они выделяют таблицу, индексируемую длиной, маской посещенных цифр и последней цифрой, а затем инициализируют девять допустимых одноразрядных стартовых состояний.
Таблица заполняется по возрастанию длины. Если значение состояния равно нулю, оно пропускается. Иначе это количество переносится на следующий слой: один раз в \(d-1\), если \(d>0\), и один раз в \(d+1\), если \(d<9\), с одновременным обновлением маски.
Поскольку граф цифр - это просто путь, у каждого состояния не более двух исходящих переходов, а у крайних цифр только один. Именно поэтому полный перебор всех длин до 40 после сжатия множества цифр в битовую маску оказывается очень дешевым.
После заполнения всех слоев реализация просматривает каждую длину от 1 до 40 и суммирует состояния, у которых в маске установлены все десять битов. Сумма по всем возможным последним цифрам обязательна, потому что задача не фиксирует последнюю цифру.
Используется обычная целочисленная арифметика, а не арифметика по модулю: здесь нужен точный ответ, и при ограничении в 40 цифр итог остается в пределах 64-битного типа.
Версия на C++ содержит дополнительную проверку на малой границе длины: она явно перечисляет все step-number-маршруты с помощью поиска в глубину и сверяет полученное значение с динамикой. Реализации на Python и Java сохраняют тот же DP-алгоритм, но без этого отдельного слоя проверки.
Всего имеется \(40\) возможных длин, \(2^{10}=1024\) возможных множеств цифр и \(10\) возможных последних цифр. Значит, общее число состояний равно
$$40\cdot 2^{10}\cdot 10=409{,}600.$$
Каждое состояние порождает не более двух переходов. Поэтому время работы при общем ограничении \(N\) равно \(O(N\cdot 2^{10}\cdot 10)\), а при \(N=40\) это очень небольшой объем вычислений.
Текущие реализации хранят все слои по длине, так что расход памяти также равен \(O(N\cdot 2^{10}\cdot 10)\). При желании можно было бы перейти к двум чередующимся слоям и получить \(O(2^{10}\cdot 10)\), но полная таблица все равно очень мала и делает код проще.
تطلب مسألة Project Euler 178 عدّ جميع أعداد step number الأصغر من \(10^{40}\) والتي تكون أيضاً pandigital، أي إن كل الأرقام \(0,1,\dots,9\) تظهر فيها مرة واحدة على الأقل. والـ step number هو عدد عشري موجب يكون الفرق بين كل رقمين متجاورين فيه مساوياً تماماً لـ 1.
وبما أن الحد الأعلى هو \(10^{40}\)، فلا يكفي النظر إلى الأعداد ذات 40 خانة فقط، بل يجب جمع كل الأطوال من 1 إلى 40. كما أن الصفر في البداية غير مسموح، وأي عدد أقصر من 10 خانات يستحيل أن يحتوي على الأرقام العشرة كلها، لكن البرمجة الديناميكية تتعامل مع هذه الأطوال كلها بصيغة واحدة.
أوضح طريقة لبناء الحل هي أن ننظر إلى الأرقام بوصفها رؤوس المخطط المساري التالي:
$$0-1-2-3-4-5-6-7-8-9.$$
وعندئذ يصبح أي step number بطول \(\ell\) عبارة عن مسار طوله \(\ell-1\) على هذا المخطط، ويبدأ من أحد الرؤوس \(1,\dots,9\). شرط الفرق بمقدار 1 شرط محلي بسيط، لكن الصعوبة الحقيقية هي تتبع مجموعة الأرقام التي زارتها السلسلة حتى الآن.
لتكن \(M\subseteq\{0,1,\dots,9\}\) مجموعة الأرقام التي ظهرت حتى الآن، وليكن \(d\) هو الرقم الأخير. نعرّف
$$F(\ell,M,d)=\#\{(a_1,\dots,a_\ell): a_\ell=d,\ |a_i-a_{i+1}|=1,\ \{a_1,\dots,a_\ell\}=M\}.$$
هذا التعريف يعبّر عن ثابت دقيق للحالة: كل بادئة صحيحة تنتمي إلى حالة واحدة فقط، وهذه الحالة يحددها طول البادئة وآخر رقم فيها ومجموعة الأرقام المختلفة التي ظهرت داخلها. وفي التنفيذ تُشفَّر المجموعة \(M\) على هيئة قناع من 10 بتات، لذا فإن إضافة رقم جديد تعني فقط تفعيل بت واحد إضافي.
عندما يكون الطول 1، فالأرقام الابتدائية المسموح بها هي \(1,2,\dots,9\) فقط. لذلك
$$F(1,\{d\},d)=1\qquad(1\le d\le 9),$$
وجميع الحالات الأخرى عند \(\ell=1\) تساوي الصفر. وبخاصة لا توجد حالة ابتدائية تنتهي بالرقم \(0\)، لأن ذلك يعني وجود صفر بادئ.
كما أن تمثيل المسألة بمخطط مساري يوضح الحالات الطرفية مباشرةً: فالرقم \(0\) لا يستطيع الانتقال إلا إلى \(1\)، والرقم \(9\) لا يستطيع الانتقال إلا إلى \(8\)، أما الأرقام الداخلية \(1,\dots,8\) فلها انتقالان ممكنان بالضبط.
إذا كانت بادئة ما في الحالة \((\ell,M,d)\)، فإن الرقم التالي لا بد أن يكون جاراً للرقم \(d\). ومن ثم فإن كل امتداد صحيح يذهب إلى إحدى الحالتين
$$F(\ell+1,M\cup\{d-1\},d-1)\mathrel{+}=F(\ell,M,d)\qquad(d>0),$$
$$F(\ell+1,M\cup\{d+1\},d+1)\mathrel{+}=F(\ell,M,d)\qquad(d<9).$$
وهذه العلاقة دقيقة تماماً وليست تقريبية. فكل step number بطول \(\ell+1\) يملك بادئة وحيدة بطول \(\ell\)، ولهذا لا يوجد فقدان للحالات ولا عدّ مزدوج لها.
لنكتب
$$M_{\mathrm{all}}=\{0,1,\dots,9\}.$$
يساهم العدد في الجواب إذا وفقط إذا كانت مجموعة الأرقام التي زارها مساوية لـ \(M_{\mathrm{all}}\). وبما أن المطلوب هو جميع الأعداد الأصغر من \(10^{40}\)، فإن المجموع النهائي يساوي
$$\text{Answer}=\sum_{\ell=1}^{40}\sum_{d=0}^{9}F(\ell,M_{\mathrm{all}},d).$$
الأطوال الأصغر من 10 تعطي صفراً تلقائياً، لأنه لا يمكن لعدد مكوّن من 9 خانات أن يحتوي على الأرقام العشرة كلها. ومع ذلك فإن إبقاءها داخل الصيغة يعطي عرضاً أنظف ويتطابق تماماً مع ما تفعله التطبيقات.
لنأخذ البادئة \(45654\). هذه بالفعل step number لأن الفروق بين كل رقمين متجاورين تساوي 1. حالتها هي
$$\ell=5,\qquad d=4,\qquad M=\{4,5,6\}.$$
بعد ذلك لا يمكن إلا إضافة \(3\) أو \(5\). إذا أضفنا \(3\) نحصل على \(456543\)، وتصبح الحالة \((6,\{3,4,5,6\},3)\). وإذا أضفنا \(5\) نحصل على \(456545\)، وتصبح الحالة \((6,\{4,5,6\},5)\). يوضح هذا المثال لماذا نحتاج إلى تخزين آخر رقم، وكذلك مجموعة الأرقام التي ظهرت حتى الآن.
وفي الجهة الأخرى، فإن أعداداً مثل \(1234567890\) و\(9876543210\) تصل إلى المجموعة الكاملة \(M_{\mathrm{all}}\) بالفعل عند الطول 10، ولذلك تسهم مباشرةً في الجواب النهائي.
تطبّق نسخ C++ وPython وJava هذه البرمجة الديناميكية الثلاثية الأبعاد حرفياً. فهي تنشئ جدولاً مفهرساً بالطول وقناع الأرقام المزارة والرقم الأخير، ثم تهيئ الحالات التسع الصحيحة ذات الخانة الواحدة.
يُملأ الجدول بترتيب تصاعدي في الطول. إذا كانت قيمة حالة ما صفراً فإن التنفيذ يتجاوزها. وإلا فإنه يدفع هذا العدد إلى الطبقة التالية: مرة إلى \(d-1\) إذا كان \(d>0\)، ومرة إلى \(d+1\) إذا كان \(d<9\)، مع تحديث قناع الأرقام في اللحظة نفسها.
وبما أن مخطط الأرقام ليس إلا مساراً مستقيماً، فإن لكل حالة في أقصى الأحوال انتقالين فقط، بينما تمتلك العقد الطرفية انتقالاً واحداً. ولهذا تصبح عملية العد الكامل حتى 40 خانة عملية خفيفة جداً بعد ضغط مجموعة الأرقام داخل bitmask.
بعد اكتمال جميع الطبقات، يمر التنفيذ على كل طول من 1 إلى 40 ويجمع الحالات التي يكون فيها القناع مشتملاً على البتات العشرة كلها. ولا بد من الجمع على جميع الأرقام النهائية الممكنة، لأن المسألة لا تفرض رقماً أخيراً بعينه.
التنفيذات تستعمل حساباً صحيحاً عادياً، لا حساباً معيارياً. فالهدف هنا هو العدد الدقيق، وحدّ 40 خانة يجعل الناتج ما زال ضمن المدى الذي تتحمله أعداد 64-بت.
تتضمن نسخة C++ فحصاً إضافياً عند حد صغير لعدد الخانات: فهي تعدّ جميع مسارات step number صراحةً بواسطة بحث عمق أول، ثم تقارن هذه الحصيلة بنتيجة البرمجة الديناميكية. أما نسختا Python وJava فتحتفظان بالنواة نفسها، ولكن من دون هذه الطبقة الصريحة من التحقق المتقاطع.
لدينا \(40\) طولاً ممكناً، و\(2^{10}=1024\) مجموعة ممكنة من الأرقام المزارة، و\(10\) أرقام ممكنة في النهاية. ولذلك فإن عدد الحالات الكلي يساوي
$$40\cdot 2^{10}\cdot 10=409{,}600.$$
كل حالة تولّد في أقصى الأحوال انتقالين. ومن ثم فإن التعقيد الزمني لحد عام \(N\) هو \(O(N\cdot 2^{10}\cdot 10)\)، ومع \(N=40\) يكون الحمل الحسابي صغيراً جداً.
وبما أن التنفيذات الحالية تخزّن جميع طبقات الطول، فإن التعقيد المكاني هو أيضاً \(O(N\cdot 2^{10}\cdot 10)\). ويمكن نظرياً ضغطه إلى \(O(2^{10}\cdot 10)\) باستخدام طبقتين متبادلتين، لكن الجدول الكامل صغير أصلاً ويجعل الشيفرة أوضح.