For a positive integer \(b\), form the concatenated product $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ We want \(C(b,m)\) to be a 9-digit number whose digits are exactly \(1,2,\dots,9\) in some order, and we must find the largest such value.
The standard example is $$C(192,3)=192384576,$$ which is already 1-to-9 pandigital. The full problem is to determine which base \(b\) and which final multiplier \(m\) produce the maximum pandigital concatenation.
The implementations solve the problem by turning it into a tiny exhaustive search, but that search is only convincing after we understand the exact digit-length and digit-usage constraints.
Let \(\ell(x)\) be the number of decimal digits of \(x\), and define $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ A base \(b\) can be valid only if there is some \(m \ge 2\) with \(L_b(m)=9\). This quantity is the real state variable of the search: after appending the first \(t\) products, the current string has length \(L_b(t)\).
Because every appended block contributes at least one digit, \(L_b(t)\) is strictly increasing in \(t\). So for any fixed base there is at most one relevant stopping point: the first \(t\) for which \(L_b(t)\ge 9\). If \(L_b(t)=9\), we have the only possible candidate for that base. If \(L_b(t) \gt 9\), then no larger multiplier can ever repair the overshoot.
Since \(m \ge 2\), any valid concatenation must include both \(b\) and \(2b\). Therefore $$\ell(b)+\ell(2b)\le 9.$$ If \(\ell(b)\ge 5\), then already \(\ell(b)+\ell(2b)\ge 10\), which is impossible. Hence every solution satisfies $$1 \le b \le 9999.$$ This is exactly why the C++, Python, and Java implementations enumerate bases only in that range.
There is also a useful structural consequence. A 4-digit base can only work with \(m=2\), because three 4-digit blocks would already contribute at least 12 digits. A 3-digit base can only survive a few multipliers, and a 1-digit base needs many of them. The code does not hard-code those cases; it lets the length sum \(L_b(t)\) discover them automatically.
For each decimal digit \(j\in\{0,1,\dots,9\}\), let \(c_j\) be the number of times \(j\) appears in \(C(b,m)\). The 1-to-9 pandigital condition is $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ Because the candidate length is already fixed at 9, this condition becomes very cheap to verify: reject 0 immediately, reject any repeated nonzero digit immediately, and if no rejection occurs then the nine used digits must be exactly \(\{1,2,\dots,9\}\).
This is why the implementations only need a small boolean table indexed by digit. There is no deeper combinatorial machinery here; once the length is right, the entire problem reduces to a constant-size occupancy check.
The given example $$C(192,3)=192384576$$ has length \(3+3+3=9\) and uses each nonzero digit exactly once. A stronger benchmark comes from $$C(9,5)=918273645,$$ which starts with 9 and is also pandigital.
The winning case found by the exhaustive scan is $$C(9327,2)=932718654,$$ because \(9327\) contributes 4 digits, \(18654\) contributes 5 digits, and together they use the digits \(1\) through \(9\) exactly once. Since every admissible base \(1\le b\le 9999\) is checked and each base contributes at most one 9-digit candidate, this value is the true maximum.
The C++, Python, and Java implementations all follow the same algorithm. They iterate through every base \(b\) from 1 to 9999, start with an empty decimal string, and append \(b,2b,3b,\dots\) one block at a time. The loop stops for that base as soon as the concatenation length reaches 9 or exceeds 9, which is exactly the monotonicity argument from \(L_b(t)\).
If the length lands on 9 and at least two products have been appended, the implementation performs the pandigital check with a 10-slot digit table. Encountering 0 or a repeated digit rejects the candidate immediately; otherwise the 9-digit value is compared with the current maximum. Because all valid candidates have the same length, a plain integer comparison is enough.
Each implementation also includes two tiny checkpoint tests before solving the full problem. One verifies that multiplying 192 by \(1,2,3\) produces the known concatenation \(192384576\), and the other verifies that the digit validator accepts \(123456789\). Those checkpoints guard both the concatenation logic and the pandigital test.
The outer loop tries exactly 9999 bases. For any one base, the inner loop appends products only until the running length reaches 9, so it performs at most 9 iterations and usually far fewer. The pandigital test scans exactly 9 characters and uses a fixed-size digit table.
So the running time is effectively constant for this Project Euler instance, and if the upper base bound is written as \(B\) then the search is \(O(B)\) time with \(O(1)\) extra space. In practical terms the entire workload is only a few tens of thousands of primitive digit operations.
Zu einer positiven ganzen Zahl \(b\) bilden wir das verkettete Produkt $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ Gesucht ist der groesste 9-stellige Wert dieser Form, dessen Ziffern genau \(1,2,\dots,9\) in irgendeiner Reihenfolge sind.
Das klassische Beispiel lautet $$C(192,3)=192384576,$$ also bereits eine 1-bis-9-pandigitale Zahl. Die eigentliche Aufgabe ist herauszufinden, welche Basis \(b\) und welcher Endmultiplikator \(m\) das Maximum liefern.
Die Programme loesen das Problem durch eine sehr kleine vollstaendige Suche. Damit diese Suche wirklich mathematisch korrekt ist, muessen zuerst die Ziffernlaengen und die Ziffernbelegung sauber eingegrenzt werden.
Sei \(\ell(x)\) die Anzahl der Dezimalziffern von \(x\), und setze $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ Eine Basis \(b\) kann nur dann erfolgreich sein, wenn es ein \(m \ge 2\) mit \(L_b(m)=9\) gibt. Genau diese Groesse beschreibt den Zustand der Suche: Nach dem Anhaengen der ersten \(t\) Produkte hat die aktuelle Zeichenkette die Laenge \(L_b(t)\).
Da jeder neue Block mindestens eine Ziffer beisteuert, waechst \(L_b(t)\) streng mit \(t\). Fuer eine feste Basis gibt es also hoechstens einen relevanten Pruefpunkt: das erste \(t\) mit \(L_b(t)\ge 9\). Falls \(L_b(t)=9\), ist das der einzige moegliche Kandidat dieser Basis. Falls \(L_b(t)\gt 9\), kann keine spaetere Verlaengerung die Ueberschreitung mehr rueckgaengig machen.
Weil \(m \ge 2\) gilt, muss jede gueltige Verkettung sowohl \(b\) als auch \(2b\) enthalten. Also gilt notwendig $$\ell(b)+\ell(2b)\le 9.$$ Waere \(\ell(b)\ge 5\), dann haetten schon diese beiden ersten Bloecke zusammen mindestens 10 Ziffern. Das ist unmoeglich. Daher folgt $$1 \le b \le 9999.$$ Genau deswegen durchlaufen die Implementierungen auch nur diese aeussere Schleife.
Daraus ergibt sich zugleich eine grobe Formklassifikation. Eine 4-stellige Basis kann nur mit \(m=2\) funktionieren, denn drei 4-stellige Bloecke haetten bereits mindestens 12 Ziffern. Bei 3-stelligen oder 1-stelligen Basen sind andere Multiplikatorlaengen moeglich, aber auch diese Faelle werden automatisch durch die Laengensumme \(L_b(t)\) entdeckt.
Fuer jede Dezimalziffer \(j\in\{0,1,\dots,9\}\) sei \(c_j\) ihre Auftretenshaeufigkeit in \(C(b,m)\). Die Bedingung "1 bis 9 pandigital" lautet dann $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ Weil die Kandidatenlaenge ohnehin schon 9 ist, wird diese Bedingung extrem billig: Eine 0 fuehrt sofort zur Ablehnung, eine wiederholte von 1 bis 9 ebenfalls, und wenn beides nicht passiert, muessen automatisch alle Ziffern \(1,\dots,9\) genau einmal vorkommen.
Darum brauchen die Implementierungen nur ein kleines Wahrheitsfeld fuer die Ziffern. Es gibt hier keine tiefere Rekurrenz oder Theorie, sondern nur eine feste Belegungspruefung auf neun Zeichen.
Das Beispiel aus der Aufgabenstellung $$C(192,3)=192384576$$ hat die Laenge \(3+3+3=9\) und verwendet jede Nichtnullziffer genau einmal. Ein staerkerer Vergleichswert ist $$C(9,5)=918273645,$$ das ebenfalls pandigital ist und bereits mit 9 beginnt.
Der Gewinner der vollstaendigen Suche ist $$C(9327,2)=932718654,$$ denn \(9327\) liefert 4 Ziffern, \(18654\) liefert 5 Ziffern, und zusammen erscheinen die Ziffern \(1\) bis \(9\) genau einmal. Weil jede zulaessige Basis \(1\le b\le 9999\) geprueft wird und jede Basis hoechstens einen 9-stelligen Kandidaten beisteuert, ist dieser Wert tatsaechlich das globale Maximum.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Schleifenstruktur. Sie gehen alle Basen \(b\) von 1 bis 9999 durch, starten mit einer leeren Dezimalkette und haengen dann \(b,2b,3b,\dots\) Block fuer Block an. Fuer diese Basis stoppt die innere Schleife, sobald die Gesamtkette Laenge 9 erreicht oder ueberschreitet. Genau das entspricht der Monotonie von \(L_b(t)\).
Falls die Laenge exakt 9 ist und mindestens zwei Produkte angehaengt wurden, wird die Pandigitalpruefung mit einer 10-stelligen Zifferntabelle ausgefuehrt. Eine 0 oder eine Wiederholung fuehrt sofort zur Verwerfung, sonst wird der 9-stellige Wert mit dem aktuellen Maximum verglichen. Weil alle gueltigen Kandidaten dieselbe Laenge haben, reicht ein einfacher numerischer Vergleich.
Vor dem eigentlichen Loesen enthalten alle drei Versionen noch zwei kleine Kontrolltests: Die Verkettung von 192 mit den Multiplikatoren \(1,2,3\) muss \(192384576\) ergeben, und der Ziffernpruefer muss \(123456789\) akzeptieren. Damit werden sowohl das Verketten als auch die Pandigitalitaetspruefung abgesichert.
Die aeussere Schleife prueft genau 9999 Basen. Fuer eine feste Basis werden Produkte nur so lange angehaengt, bis die Laenge 9 erreicht ist, also hoechstens 9 Iterationen und in der Praxis meist deutlich weniger. Die Pandigitalpruefung betrachtet genau 9 Zeichen und benutzt eine Tabelle fester Groesse.
Damit ist die Laufzeit fuer diese konkrete Euler-Aufgabe praktisch konstant, und bei einem allgemeinen oberen Basislimit \(B\) erhaelt man \(O(B)\) Zeit und \(O(1)\) Zusatzspeicher. Tatsaechlich sind es nur wenige Zehntausend primitive Ziffernoperationen.
Pozitif bir \(b\) tamsayisi icin su birlestirilmis carpimi tanimlayalim: $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ Amac, bu bicimde elde edilen ve rakamlari tam olarak \(1,2,\dots,9\) olan en buyuk 9 basamakli sayiyi bulmaktir.
Standart ornek $$C(192,3)=192384576$$ seklindedir ve bu sayi zaten 1'den 9'a pandigitaldir. Asil soru, en buyuk boyle degeri hangi taban \(b\) ile hangi son carpani \(m\) olusturur sorusudur.
Programlar problemi cok kucuk bir tam tarama ile cozer. Bu taramanin neden eksiksiz oldugunu gormek icin once basamak uzunlugu ve rakam kullanimina ait kisitlari netlestirmek gerekir.
\(\ell(x)\) ifadesi \(x\)'in onluk yazimindaki basamak sayisi olsun ve $$L_b(t)=\sum_{r=1}^{t}\ell(rb)$$ tanimini yapalim. Bir tabanin basarili olabilmesi icin, en az bir \(m \ge 2\) degeri icin \(L_b(m)=9\) olmalidir. Aramanin asil durumu budur: ilk \(t\) carpan eklendiginde olusan dizgenin uzunlugu tam olarak \(L_b(t)\) olur.
Her yeni blok en az bir basamak getirdigi icin \(L_b(t)\) degeri \(t\) arttikca siki bicimde buyur. Dolayisiyla sabit bir taban icin en fazla bir anlamli durak vardir: \(L_b(t)\ge 9\) yapan ilk \(t\). Eger \(L_b(t)=9\) ise bu, o taban icin tek olasi adaydir. Eger \(L_b(t)\gt 9\) ise daha sonraki hicbir carpan bu fazla uzunlugu geri alamaz.
\(m \ge 2\) oldugu icin her gecerli birlestirme hem \(b\)'yi hem de \(2b\)'yi icermek zorundadir. Bu nedenle zorunlu olarak $$\ell(b)+\ell(2b)\le 9$$ olmalidir. Eger \(\ell(b)\ge 5\) olsaydi daha ilk iki blok bile en az 10 basamak ederdi. Bu imkansizdir. O halde $$1 \le b \le 9999$$ sonucu cikar. C++, Python ve Java uygulamalarinin dis donguyu yalnizca bu aralikta kurmasinin nedeni tam olarak budur.
Bundan sekil bilgisi de gelir. 4 basamakli bir taban ancak \(m=2\) ile calisabilir; cunku uc tane 4 basamakli blok en az 12 basamak yapar. 3 basamakli ve 1 basamakli tabanlarda farkli olasiliklar vardir, fakat kod bunlari tek tek ayirmak yerine \(L_b(t)\) toplaminin dogal davranisina birakir.
Her \(j\in\{0,1,\dots,9\}\) rakami icin, \(c_j\) degeri \(C(b,m)\) icinde \(j\)'nin kac kez gectigini gostersin. 1'den 9'a pandigital olma kosulu $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9)$$ bicimindedir. Adayin uzunlugu zaten 9 oldugu icin bu test cok ucuzdur: 0 gorulurse hemen reddedilir, sifir disi bir rakam tekrar ederse hemen reddedilir, hicbiri olmazsa kullanilan dokuz rakam mecburen \(\{1,2,\dots,9\}\) olur.
Bu yuzden uygulamalar yalnizca rakama gore indekslenen kucuk bir dogruluk tablosu kullanir. Daha derin bir cebirsel yapi yoktur; dogru uzunluga ulasildiktan sonra mesele sabit boyutlu bir doluluk kontrolune iner.
Soruda verilen $$C(192,3)=192384576$$ orneginin uzunlugu \(3+3+3=9\)'dur ve her sifir disi rakam bir kez kullanilir. Daha guclu bir esitlik ise $$C(9,5)=918273645$$ olup yine pandigitaldir ve 9 ile baslar.
Tam taramanin buldugu kazanan durum $$C(9327,2)=932718654$$ ifadesidir. Burada \(9327\) 4 basamak, \(18654\) ise 5 basamak getirir ve birlikte \(1\) ile \(9\) arasindaki tum rakamlar tam bir kez kullanilir. Her uygun taban \(1\le b\le 9999\) tarandigi ve her taban en fazla bir 9 basamakli aday uretebildigi icin bu deger gercek maksimumdur.
C++, Python ve Java uygulamalarinin is akisi aynidir. Hepsi \(b=1\)'den \(b=9999\)'a kadar gider, bos bir onluk dizge ile baslar ve sirasiyla \(b,2b,3b,\dots\) bloklarini ekler. Dize uzunlugu 9'a ulastiginda ya da 9'u gectiginde o taban icin ic dongu durur. Bu tam olarak \(L_b(t)\)'nin monoton buyumesiyle ayni mantiktir.
Eger uzunluk tam 9 ise ve en az iki carpim eklenmisse, uygulama 10 hucreli bir rakam tablosu ile pandigital kontrolu yapar. 0 gorulmesi veya bir rakamin tekrar etmesi adayi aninda eler; aksi halde ortaya cikan 9 basamakli sayi mevcut en iyi degerle karsilastirilir. Tum gecerli adaylarin uzunlugu ayni oldugu icin siradan bir sayisal karsilastirma yeterlidir.
Uc uygulamanin hepsinde iki kucuk kontrol de vardir: 192 sayisinin \(1,2,3\) ile carpimlarinin birlestirilince \(192384576\) vermesi gerekir ve rakam denetleyicisi \(123456789\) dizisini kabul etmelidir. Bu kontroller hem birlestirme mantigini hem de rakam dogrulamasini guvenceye alir.
Dis dongu tam 9999 taban dener. Sabit bir taban icin ic dongu, birlesen uzunluk 9'a varana kadar calisir; dolayisiyla en fazla 9 adim surer ve pratikte genellikle cok daha kisadir. Pandigital kontrolu ise tam 9 karakter tarar ve sabit boyutlu bir tablo kullanir.
Bu nedenle bu Euler problemi icin calisma suresi fiilen sabittir. Ust taban siniri \(B\) ile yazilmak istenirse zaman karmasikligi \(O(B)\), ek bellek ise \(O(1)\) olur. Gercek is yuku yalnizca birkaç on bin basit rakam islemi duzeyindedir.
Para un entero positivo \(b\), formamos el producto concatenado $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ Buscamos el mayor numero de 9 cifras de esta forma cuyos digitos sean exactamente \(1,2,\dots,9\) en algun orden.
El ejemplo clasico es $$C(192,3)=192384576,$$ que ya es pandigital del 1 al 9. La tarea real consiste en determinar que base \(b\) y que multiplicador final \(m\) producen el maximo.
Los programas resuelven el problema con una enumeracion exhaustiva muy pequena. Para ver por que esa enumeracion es completa, primero hay que fijar con precision las restricciones de longitud y de uso de digitos.
Sea \(\ell(x)\) el numero de cifras decimales de \(x\), y definamos $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ Una base \(b\) solo puede servir si existe algun \(m \ge 2\) tal que \(L_b(m)=9\). Esa es la verdadera variable de estado del proceso: despues de concatenar los primeros \(t\) productos, la cadena actual tiene longitud \(L_b(t)\).
Como cada bloque nuevo aporta al menos una cifra, \(L_b(t)\) crece estrictamente con \(t\). Por tanto, para una base fija hay como mucho un punto relevante: el primer \(t\) para el que \(L_b(t)\ge 9\). Si \(L_b(t)=9\), obtenemos el unico candidato posible de esa base. Si \(L_b(t)\gt 9\), ningun multiplicador posterior podra corregir el exceso.
Dado que \(m \ge 2\), toda concatenacion valida contiene tanto \(b\) como \(2b\). Asi que necesariamente $$\ell(b)+\ell(2b)\le 9.$$ Si \(\ell(b)\ge 5\), entonces esos dos primeros bloques ya sumarian al menos 10 cifras, lo cual es imposible. En consecuencia, $$1 \le b \le 9999.$$ Esa es exactamente la razon por la que las implementaciones de C++, Python y Java solo recorren esa banda de bases.
De aqui tambien sale una intuicion util. Una base de 4 cifras solo puede funcionar con \(m=2\), porque tres bloques de 4 cifras ya darian como minimo 12 cifras. En bases de 3, 2 o 1 cifra hay otros patrones posibles, pero el codigo no necesita separarlos a mano: la propia suma \(L_b(t)\) los detecta.
Para cada digito \(j\in\{0,1,\dots,9\}\), sea \(c_j\) el numero de veces que \(j\) aparece en \(C(b,m)\). Ser pandigital del 1 al 9 equivale a exigir $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ Como la longitud del candidato ya esta fijada en 9, esta comprobacion se vuelve muy barata: si aparece un 0, se rechaza; si aparece un digito no nulo repetido, se rechaza; y si ninguna de esas dos cosas ocurre, entonces los nueve digitos usados solo pueden ser \(1,2,\dots,9\).
Por eso las implementaciones solo necesitan una pequena tabla booleana indexada por digito. No hay aqui una recurrencia sofisticada; una vez correcta la longitud, el problema queda reducido a una comprobacion de ocupacion de tamano constante.
El ejemplo del enunciado $$C(192,3)=192384576$$ tiene longitud \(3+3+3=9\) y usa cada digito no nulo exactamente una vez. Un punto de referencia mas fuerte es $$C(9,5)=918273645,$$ que tambien es pandigital y empieza por 9.
El caso ganador encontrado por la exploracion completa es $$C(9327,2)=932718654,$$ porque \(9327\) aporta 4 cifras, \(18654\) aporta 5 cifras, y entre ambos aparecen una sola vez los digitos \(1\) a \(9\). Como se revisa toda base admisible \(1\le b\le 9999\) y cada base aporta a lo sumo un candidato de 9 cifras, este valor es de verdad el maximo global.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Recorren todas las bases \(b\) desde 1 hasta 9999, comienzan con una cadena decimal vacia y van anadiendo los bloques \(b,2b,3b,\dots\) uno a uno. Para esa base concreta, el bucle interno termina cuando la longitud total alcanza 9 o la sobrepasa. Eso coincide con el argumento de monotonia de \(L_b(t)\).
Si la longitud queda exactamente en 9 y ya se han usado al menos dos productos, se ejecuta la validacion pandigital con una tabla de 10 posiciones. Encontrar un 0 o una repeticion descarta el candidato al instante; en caso contrario, el valor de 9 cifras se compara con el mejor visto hasta ese momento. Como todos los candidatos validos tienen la misma longitud, basta comparar enteros.
Ademas, las tres versiones incluyen dos pequenas pruebas internas antes de resolver el problema completo. Una verifica que 192 concatenado con sus multiplicaciones por \(1,2,3\) produce \(192384576\), y la otra verifica que el validador acepta \(123456789\). Esas comprobaciones protegen tanto la logica de concatenacion como la prueba de pandigitalidad.
El bucle exterior prueba exactamente 9999 bases. Para una base fija, el bucle interior solo continua hasta llegar a longitud 9, de modo que realiza como mucho 9 iteraciones y normalmente muchas menos. La comprobacion pandigital inspecciona exactamente 9 caracteres y usa una tabla de tamano fijo.
Por eso el tiempo total es, en la practica, constante para esta instancia concreta de Project Euler. Si se escribe \(B\) para el limite superior de la base, la complejidad temporal es \(O(B)\) y el espacio extra es \(O(1)\). El trabajo real se reduce a unas pocas decenas de miles de operaciones elementales con digitos.
对一个正整数 \(b\)，构造它与连续倍数的十进制拼接： $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ 我们要找的是这种形式中最大的 9 位数，并且这 9 位恰好是 \(1,2,\dots,9\) 各出现一次。
题目里的经典例子是 $$C(192,3)=192384576,$$ 它已经是一个 1 到 9 的全数字数。真正的问题是：哪一个底数 \(b\) 和哪一个最终乘数 \(m\) 能产生最大的合法拼接结果。
三个实现本质上都在做一次很小的穷举，但这次穷举之所以足够，需要先把长度约束和数字约束说清楚。这里没有复杂递推，关键是两个不变量：拼接长度的单调增长，以及数字占用情况。
记 \(\ell(x)\) 为整数 \(x\) 的十进制位数，并定义 $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ 这表示把 \(b,2b,\dots,tb\) 全部拼接以后得到的总位数。一个底数 \(b\) 想要成功，必须存在某个 \(m \ge 2\) 使得 \(L_b(m)=9\)。因此 \(L_b(t)\) 才是搜索中的真实状态量。
由于每次新追加的 \(rb\) 至少带来 1 位，所以 \(L_b(t)\) 随 \(t\) 严格递增。于是对固定的 \(b\)，真正值得检查的时刻最多只有一次：第一次满足 \(L_b(t)\ge 9\) 的那个 \(t\)。如果这时恰好 \(L_b(t)=9\)，那么它就是这个底数唯一可能的候选；如果已经超过 9 位，那么再乘更大的倍数只会更长，不可能重新回到 9 位。
因为题目要求 \(m \ge 2\)，所以任何合法答案都至少包含 \(b\) 和 \(2b\) 这两个块。于是必然有 $$\ell(b)+\ell(2b)\le 9.$$ 如果 \(\ell(b)\ge 5\)，那么仅仅前两个块就至少有 10 位，立刻矛盾。因此一定有 $$1 \le b \le 9999.$$ 这正是三份实现把外层循环限制在 1 到 9999 的数学原因。
这个结论还说明了候选形状为什么很有限。4 位底数只能配 \(m=2\)，因为三个 4 位块至少已经有 12 位。3 位、2 位、1 位底数也各自只有很少的可能情况。不过代码并没有人为写死这些分类，而是直接依靠 \(L_b(t)\) 的自然增长来自动发现什么时候该停。
对每个十进制数字 \(j\in\{0,1,\dots,9\}\)，设 \(c_j\) 为它在 \(C(b,m)\) 中出现的次数。所谓 "1 到 9 pandigital"，等价于 $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ 由于候选长度已经固定为 9，这个条件检查起来非常便宜：一旦看到 0，立即失败；一旦看到非零数字重复，立即失败；如果这两种失败都没有发生，那么这 9 个位置只能正好由 \(1,2,\dots,9\) 填满。
因此实现里只需要一个按数字索引的小型布尔表。这里不需要容斥、不需要生成函数，也不需要任何复杂组合结构；长度正确之后，问题就退化成一个常数规模的占位检查。
题目给出的例子 $$C(192,3)=192384576$$ 的位数为 \(3+3+3=9\)，并且每个非零数字恰好出现一次。另一个更强的基准是 $$C(9,5)=918273645,$$ 它同样是 1 到 9 全数字，而且首位已经是 9。
完整搜索找到的最优情况是 $$C(9327,2)=932718654.$$ 这里 \(9327\) 提供 4 位，\(18654\) 提供 5 位，合起来刚好 9 位，而且数字 \(1\) 到 \(9\) 各出现一次。由于所有可能的底数 \(1\le b\le 9999\) 都被检查过，并且每个底数至多只能产生一个 9 位候选，所以这个值就是全局最大值。
C++、Python 和 Java 三个实现的流程完全一致。它们都从 \(b=1\) 枚举到 \(b=9999\)，先准备一个空的十进制字符串，然后依次追加 \(b,2b,3b,\dots\)。当当前字符串长度达到 9 或超过 9 时，这个底数的内层循环就终止。这正好对应前面证明过的 \(L_b(t)\) 单调增长性质。
如果某一步长度恰好等于 9，并且已经至少追加了两个乘积，就执行一次全数字检查。检查方法是使用一个长度为 10 的数字占用表：遇到 0 立即拒绝，遇到重复的非零数字也立即拒绝；否则把得到的 9 位数与当前最优值比较并更新。因为所有合法候选长度都相同，所以直接按整数比较就够了。
三个实现还都带有两条很小的自检。第一条验证 \(192\) 与 \(1,2,3\) 的拼接确实是 \(192384576\)；第二条验证数字检查器会接受 \(123456789\)。这两条自检分别覆盖了拼接逻辑和数字判定逻辑。
外层循环固定检查 9999 个底数。对任意一个底数，内层循环只会持续到总长度达到 9，因此最多做 9 次追加，而且通常远少于 9 次。每次真正进入全数字判定时，也只需要扫描 9 个字符并维护一个固定大小的布尔表。
所以对这道固定规模的 Project Euler 题来说，运行时间实际上就是常数量级。若把底数上界写成参数 \(B\)，则时间复杂度是 \(O(B)\)，额外空间复杂度是 \(O(1)\)。从实际工作量看，不过是几万次非常简单的数字操作。
Для положительного целого \(b\) рассмотрим конкатенированное произведение $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ Нужно найти наибольшее девятизначное число такого вида, в котором цифры \(1,2,\dots,9\) встречаются ровно по одному разу.
Классический пример из условия: $$C(192,3)=192384576.$$ Это уже панцифровое число от 1 до 9. Задача состоит в том, чтобы определить, какие именно \(b\) и \(m\) дают максимальный допустимый результат.
Все три реализации сводят задачу к очень маленькому полному перебору. Чтобы такой перебор был обоснован, надо сначала аккуратно разобрать ограничения на длину записи и на набор цифр.
Пусть \(\ell(x)\) обозначает число десятичных цифр в \(x\), и положим $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ Это общая длина строки после конкатенации \(b,2b,\dots,tb\). Основание \(b\) может дать решение только тогда, когда существует \(m \ge 2\) со свойством \(L_b(m)=9\). Именно \(L_b(t)\) и является реальным состоянием поиска.
Каждый новый блок добавляет как минимум одну цифру, поэтому \(L_b(t)\) строго возрастает по \(t\). Значит, для фиксированного \(b\) есть не более одного важного момента: первое \(t\), при котором \(L_b(t)\ge 9\). Если в этот момент длина равна 9, то это единственный возможный кандидат для данной базы. Если длина уже превысила 9, никакое последующее домножение не сможет вернуть ее обратно к 9.
Так как по условию \(m \ge 2\), любая допустимая конкатенация обязана содержать и \(b\), и \(2b\). Следовательно, $$\ell(b)+\ell(2b)\le 9.$$ Если бы \(\ell(b)\ge 5\), то уже первые два блока дали бы не меньше 10 цифр, что невозможно. Поэтому обязательно $$1 \le b \le 9999.$$ Именно этим объясняется, почему реализации на C++, Python и Java перебирают базы только в таком диапазоне.
Отсюда видна и форма возможных кандидатов. Четырехзначная база может работать только при \(m=2\), потому что три четырехзначных блока уже дали бы не меньше 12 цифр. Для трехзначных, двухзначных и однозначных баз возможны другие короткие схемы, но код не зашивает их вручную: он просто следует росту \(L_b(t)\) и останавливается в нужный момент.
Для каждой цифры \(j\in\{0,1,\dots,9\}\) обозначим через \(c_j\) число ее вхождений в \(C(b,m)\). Тогда условие "панцифровое от 1 до 9" записывается так: $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ Поскольку длина кандидата уже равна 9, проверка становится очень дешевой: увидели 0 - сразу отказ, увидели повтор цифры от 1 до 9 - тоже отказ. Если ни одного отказа не произошло, то использованы ровно цифры \(1,2,\dots,9\).
Поэтому реализациям достаточно маленькой булевой таблицы по цифрам. Никаких нетривиальных рекуррентных соотношений здесь не требуется; после правильного ограничения длины остается лишь константная проверка занятости цифр.
Пример из условия $$C(192,3)=192384576$$ имеет длину \(3+3+3=9\) и использует каждую ненулевую цифру ровно один раз. Более сильный ориентир дает $$C(9,5)=918273645,$$ которое тоже панцифрово и уже начинается с 9.
Максимальный случай, найденный полным перебором, таков: $$C(9327,2)=932718654.$$ Здесь \(9327\) дает 4 цифры, \(18654\) дает 5 цифр, и вместе они содержат каждую цифру от 1 до 9 ровно один раз. Так как проверяются все допустимые базы \(1\le b\le 9999\), а каждая база может породить не более одного девятизначного кандидата, это и есть глобальный максимум.
Реализации на C++, Python и Java устроены одинаково. Они перебирают все базы \(b\) от 1 до 9999, начинают с пустой десятичной строки и по одному добавляют блоки \(b,2b,3b,\dots\). Для текущей базы внутренний цикл прекращается сразу, как только суммарная длина достигает 9 или превосходит 9. Это в точности соответствует доказанной выше монотонности \(L_b(t)\).
Если длина оказалась ровно 9 и уже использовано как минимум два произведения, запускается проверка пандигитальности через таблицу из 10 ячеек. Появление 0 или повторной цифры мгновенно отбрасывает кандидата; в противном случае полученное девятизначное число сравнивается с текущим максимумом. Поскольку длина всех допустимых кандидатов одинакова, достаточно обычного числового сравнения.
Перед основным поиском во всех трех версиях есть две маленькие контрольные проверки. Первая подтверждает, что для 192 и множителей \(1,2,3\) действительно получается \(192384576\). Вторая подтверждает, что проверка цифр принимает \(123456789\). Эти тесты страхуют и логику конкатенации, и сам валидатор.
Внешний цикл проверяет ровно 9999 баз. Для одной базы внутренний цикл работает только до тех пор, пока длина не достигнет 9, то есть не более 9 итераций и обычно заметно меньше. Проверка пандигитальности сканирует ровно 9 символов и использует таблицу фиксированного размера.
Поэтому для этой конкретной задачи Project Euler время работы фактически постоянно. Если обозначить верхнюю границу базы через \(B\), то получаем \(O(B)\) по времени и \(O(1)\) по дополнительной памяти. Реальный объем вычислений - всего несколько десятков тысяч элементарных операций над цифрами.
لعدد صحيح موجب \(b\) نعرّف الجداء المتسلسل على الصورة $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ والمطلوب هو ايجاد اكبر عدد مكوّن من 9 خانات من هذا الشكل بحيث تكون خاناته هي \(1,2,\dots,9\) مرة واحدة لكل رقم.
المثال الكلاسيكي في نص المسألة هو $$C(192,3)=192384576,$$ وهو بالفعل عدد شامل من 1 إلى 9. اما السؤال الحقيقي فهو: ما قيمة \(b\) وما قيمة \(m\) اللتان تعطيان اكبر ناتج صالح؟
الحلول الثلاثة تحوّل المسألة إلى تعداد كامل صغير جدا. ولكي يكون هذا التعداد مبررا، يجب اولا فهم قيدي طول السلسلة وتوزيع الارقام فهما دقيقا. لا توجد هنا علاقة عودية عميقة؛ العنصران الحاسمان هما ازدياد الطول بشكل رتيب، وفحص ظهور الارقام.
لنرمز بـ \(\ell(x)\) إلى عدد الخانات العشرية في \(x\)، ولنعرّف $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ هذا هو طول السلسلة بعد دمج \(b,2b,\dots,tb\). ولا يمكن لقاعدة \(b\) ان تنتج حلا الا اذا وجد \(m \ge 2\) بحيث \(L_b(m)=9\). لذلك فهذه الكمية هي متغير الحالة الحقيقي في البحث.
بما ان كل كتلة جديدة تضيف خانة واحدة على الاقل، فان \(L_b(t)\) يزداد زيادة صارمة مع \(t\). ولهذا فلكل قاعدة ثابتة يوجد في اقصى الاحوال موضع واحد يستحق الفحص: اول \(t\) يحقق \(L_b(t)\ge 9\). اذا كان \(L_b(t)=9\) حصلنا على المرشح الوحيد الممكن لهذه القاعدة. واذا كان \(L_b(t)\gt 9\) فلا توجد اي قيمة اكبر لـ \(t\) تستطيع اصلاح هذا التجاوز.
بما ان الشرط يفرض \(m \ge 2\)، فلا بد ان يحتوي اي حل صالح على كل من \(b\) و \(2b\). لذلك يلزم $$\ell(b)+\ell(2b)\le 9.$$ ولو كانت \(\ell(b)\ge 5\) لكان مجموع اول كتلتين لا يقل عن 10 خانات، وهذا مستحيل. ومن ثم نحصل على $$1 \le b \le 9999.$$ وهذا هو السبب الرياضي المباشر الذي يجعل تطبيقات C++ وPython وJava تكتفي بفحص هذا المجال فقط.
ومن هنا يظهر ايضا شكل المرشحين المحتملين. فالقاعدة ذات الاربع خانات لا يمكن ان تعمل الا مع \(m=2\)، لان ثلاث كتل من اربع خانات تعطي على الاقل 12 خانة. اما القواعد ذات ثلاث خانات او خانتين او خانة واحدة فلها حالات قصيرة اخرى، لكن الشيفرة لا تبرمج هذه الحالات يدويا؛ بل تترك لسلوك \(L_b(t)\) ان يحدد نقطة التوقف تلقائيا.
لكل رقم عشري \(j\in\{0,1,\dots,9\}\) لنكتب \(c_j\) لعدد مرات ظهور \(j\) داخل \(C(b,m)\). عندئذ يصبح شرط "شامل من 1 إلى 9" هو $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ وبما ان طول المرشح محدد سلفا بــ 9، فالفحص يصبح بسيطا جدا: ظهور الصفر يعني رفضا فوريا، وظهور رقم غير صفري للمرة الثانية يعني رفضا فوريا ايضا، واذا لم يقع اي من هذين الامرين فلا يبقى الا ان تكون الارقام المستخدمة هي \(1,2,\dots,9\) كلها مرة واحدة.
لهذا السبب لا تحتاج التطبيقات إلا إلى جدول منطقي صغير مفهرس بالارقام. فبعد تثبيت الطول الصحيح، تتحول المسألة كلها إلى اختبار اشغال ثابت الحجم.
مثال المسألة $$C(192,3)=192384576$$ طوله \(3+3+3=9\) ويستخدم كل رقم غير صفري مرة واحدة. وهناك مرجع اقوى هو $$C(9,5)=918273645,$$ وهو ايضا شامل من 1 إلى 9 ويبدأ بالرقم 9.
الحالة الفائزة التي يجدها التعداد الكامل هي $$C(9327,2)=932718654.$$ فالعدد \(9327\) يضيف 4 خانات، و\(18654\) يضيف 5 خانات، ومعا يعطون الارقام \(1\) إلى \(9\) مرة واحدة لكل رقم. وبما ان كل قاعدة ممكنة ضمن المجال \(1\le b\le 9999\) يتم فحصها، وبما ان كل قاعدة لا تنتج اكثر من مرشح واحد بطول 9 خانات، فان هذه القيمة هي بالفعل القيمة العظمى الحقيقية.
تتبع تطبيقات C++ وPython وJava البنية نفسها تماما. فهي تمر على كل قاعدة \(b\) من 1 إلى 9999، وتبدأ بسلسلة عشرية فارغة، ثم تضيف بالتتابع الكتل \(b,2b,3b,\dots\). ويتوقف الدور الداخلي لهذه القاعدة حالما يصل طول السلسلة إلى 9 او يتجاوزها. وهذا يطابق تماما برهان الرتابة الخاص بـ \(L_b(t)\).
اذا كان الطول يساوي 9 تماما، وكان قد استُخدم على الاقل حاصلان، تُجرى عندئذ عملية فحص الشمول الرقمي باستعمال جدول من 10 خانات. ظهور الصفر او تكرار اي رقم يؤدي إلى رفض المرشح فورا، وإلا تُقارن القيمة الناتجة ذات الخانات التسع مع اكبر قيمة معروفة حتى تلك اللحظة. ولأن جميع المرشحين الصالحين لهم الطول نفسه، فالمقارنة العددية المباشرة كافية.
وتحتوي كل نسخة ايضا على اختبارين صغيرين قبل الحل الكامل. الاختبار الاول يتحقق من ان دمج \(192\) مع مضاعفاته \(1,2,3\) يعطي \(192384576\)، والاختبار الثاني يتحقق من ان فاحص الارقام يقبل \(123456789\). هذان الاختباران يثبتان سلامة منطق الدمج وسلامة فحص الارقام معا.
الحلقة الخارجية تختبر 9999 قاعدة بالضبط. اما الحلقة الداخلية، فلكل قاعدة تستمر فقط حتى يصل الطول إلى 9، ولذلك لا تتجاوز 9 خطوات في اسوأ الاحوال وغالبا اقل من ذلك بكثير. وفحص الشمول الرقمي يمر على 9 محارف فقط ويستخدم جدولا ثابتا صغيرا.
لذلك يكون زمن التنفيذ عمليا ثابتا لهذه المسألة المحددة من Project Euler. واذا رمزنا لحد القواعد الاعلى بالرمز \(B\)، نحصل على زمن \(O(B)\) ومساحة اضافية \(O(1)\). اما الحمل الفعلي فلا يتجاوز بضعة عشرات الالاف من العمليات البسيطة على الخانات.