A multiplicand \(a\), a multiplier \(b\), and a product \(p=ab\) form a valid identity when the decimal digits of \(a\), \(b\), and \(p\) together use each of \(1,2,\dots,9\) exactly once. The task is to find every such identity and sum the distinct product values, counting the same product only once even if it has more than one factorization.
The standard example is \(39\times 186=7254\), because the concatenation \(391867254\) is a permutation of \(123456789\).
The solution is a finite search, but it is not an arbitrary brute-force search. A short digit-length argument collapses the problem to two search families, and a simple invariant decides whether a candidate identity is truly 1-to-9 pandigital.
Let \(x=d(a)\), \(y=d(b)\), and \(z=d(p)\), where \(d(n)\) is the number of decimal digits of \(n\). A valid pandigital identity uses exactly nine digits overall, so
$$x+y+z=9.$$
For the product of an \(x\)-digit number and a \(y\)-digit number, the result has either \(x+y-1\) digits or \(x+y\) digits. Therefore
$$z\in\{x+y-1,\ x+y\}.$$
If \(z=x+y\), then \(9=2(x+y)\), which is impossible because the left-hand side is odd. So the only remaining case is \(z=x+y-1\), giving
$$9=x+y+(x+y-1)=2(x+y)-1,$$
hence \(x+y=5\) and \(z=4\). After ordering the two factors by size of digit-length, the only admissible triples are
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
That exact deduction explains why the implementations search only the cases \(1\)-digit \(\times\) \(4\)-digit and \(2\)-digit \(\times\) \(3\)-digit. No other digit pattern can succeed.
For any candidate \((a,b,p)\), scan the decimal digits of \(a\), then \(b\), then \(p\). The triple is valid if and only if three conditions all hold: no digit is \(0\), no digit is repeated, and exactly nine digits are seen in total. Once those three conditions are satisfied, the digit set must be exactly \(\{1,2,\dots,9\}\).
The implementations encode this with a ten-entry boolean table indexed by the digit. Encountering a zero or a repeated digit causes immediate rejection, so most bad candidates fail before the full scan is finished.
The problem asks for the sum of distinct products, not the sum over successful factorizations. This matters because one product can arise from more than one pandigital identity. A well-known example is
$$12\times 483=5796,\qquad 42\times 138=5796.$$
Both identities are valid, but the product \(5796\) must contribute only once. That is why the implementations store successful products in a set before taking the final sum.
The positive checkpoint
$$39\times 186=7254$$
belongs to the \((2,3,4)\) case. Its digits are \(3,9,1,8,6,7,2,5,4\): there is no zero, no repetition, and the total count is nine, so it is valid.
The negative checkpoint
$$12\times 34=408$$
fails immediately because the product contains the digit \(0\). It also has only \(2+2+3=7\) digits altogether, so it cannot possibly be a 1-to-9 pandigital identity.
The C++, Python, and Java implementations run two nested-loop searches matching the two digit patterns above. The first search tests every \(a\in\{1,\dots,9\}\) against every four-digit \(b\in\{1234,\dots,9876\}\). The second tests every two-digit \(a\in\{12,\dots,98\}\) against every three-digit \(b\in\{123,\dots,987\}\). This removes impossible factor-length shapes such as \(3\)-digit \(\times\) \(3\)-digit before the digit checker is ever called.
For each pair, the implementation computes \(p=ab\) and feeds \(a\), \(b\), and \(p\) into the same digit-usage test. The loops deliberately keep simple rectangular ranges instead of pre-filtering zeros or repeated digits inside the factors; the shared validator rejects those cases in constant time. A wrong product length is also handled naturally: if the combined digit count is not exactly nine, the candidate fails at the end of the scan.
Whenever a candidate passes the digit test, its product is inserted into a set. After both searches finish, the program sums the set elements to obtain the required answer. Before the main computation, each implementation also performs two small checkpoints: one known valid pandigital identity and one known invalid identity.
The first search examines \(9\times 8643=77{,}787\) pairs, and the second examines \(87\times 865=75{,}255\) pairs, so the total number of tested products is \(153{,}042\). Each test performs one multiplication and a scan of at most ten decimal digits, so the work per candidate is \(O(1)\). For this fixed problem instance, the running time is therefore tiny.
The digit validator itself uses constant working memory. The only growing structure is the set of successful products, and for Problem 32 that set remains very small. In practice the computation completes essentially instantly.
Gesucht sind alle Identitäten \(a\times b=p\), bei denen die Dezimalziffern von \(a\), \(b\) und \(p\) zusammen jede Ziffer \(1,2,\dots,9\) genau einmal enthalten. Am Ende wird nicht über die Identitäten selbst summiert, sondern über die verschiedenen Produktwerte \(p\); derselbe Produktwert darf also nur einmal gezählt werden, auch wenn er aus mehreren gültigen Faktorisierungen entsteht.
Das klassische Beispiel ist \(39\times 186=7254\), denn die Verkettung \(391867254\) ist eine Permutation von \(123456789\).
Die Lösung ist eine endliche Suche, aber nicht blind. Zuerst wird die Zahl möglicher Stellenmuster exakt bestimmt. Danach genügt ein Zifferninvariante-Test, um jede Kandidatenidentität korrekt zu akzeptieren oder zu verwerfen.
Seien \(x=d(a)\), \(y=d(b)\) und \(z=d(p)\), wobei \(d(n)\) die Anzahl der Dezimalstellen von \(n\) bezeichnet. Da eine gültige pandigitale Identität insgesamt genau neun Ziffern benutzt, gilt
$$x+y+z=9.$$
Das Produkt einer \(x\)-stelligen und einer \(y\)-stelligen Zahl besitzt entweder \(x+y-1\) oder \(x+y\) Stellen. Also
$$z\in\{x+y-1,\ x+y\}.$$
Der Fall \(z=x+y\) würde \(9=2(x+y)\) liefern und ist unmöglich. Somit bleibt nur \(z=x+y-1\), also
$$9=x+y+(x+y-1)=2(x+y)-1,$$
und daraus folgt \(x+y=5\) sowie \(z=4\). Ordnet man die Faktoren nach ihrer Stellenzahl, bleiben genau die beiden Möglichkeiten
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
Genau deshalb durchsuchen die Implementierungen nur die Fälle \(1\)-stellig \(\times\) \(4\)-stellig und \(2\)-stellig \(\times\) \(3\)-stellig. Andere Stellenmuster können prinzipiell nicht funktionieren.
Für jedes Kandidatentripel \((a,b,p)\) werden die Dezimalziffern von \(a\), dann von \(b\) und dann von \(p\) gelesen. Gültig ist das Tripel genau dann, wenn drei Bedingungen zugleich erfüllt sind: Keine Ziffer ist \(0\), keine Ziffer kommt doppelt vor, und insgesamt werden genau neun Ziffern gesehen. Dann ist die Ziffernmenge automatisch exakt \(\{1,2,\dots,9\}\).
In den Implementierungen wird dies durch ein Bool-Array mit zehn Einträgen realisiert. Sobald eine Null oder eine bereits benutzte Ziffer auftaucht, wird der Kandidat sofort verworfen.
Gefordert ist die Summe der verschiedenen Produkte, nicht die Summe aller erfolgreichen Faktorisierungen. Das ist wichtig, weil derselbe Produktwert mehrfach entstehen kann. Ein Standardbeispiel lautet
$$12\times 483=5796,\qquad 42\times 138=5796.$$
Beide Identitäten sind gültig, aber \(5796\) darf nur einmal in die Endsumme eingehen. Deshalb werden erfolgreiche Produkte zunächst in einer Menge gespeichert.
Das positive Prüfbeispiel
$$39\times 186=7254$$
gehört zum Fall \((2,3,4)\). Seine Ziffern sind \(3,9,1,8,6,7,2,5,4\): keine Null, keine Wiederholung, insgesamt neun Ziffern. Also ist die Identität gültig.
Das negative Prüfbeispiel
$$12\times 34=408$$
scheitert sofort, weil das Produkt die Ziffer \(0\) enthält. Außerdem gibt es insgesamt nur \(2+2+3=7\) Ziffern, also kann die Identität gar nicht 1-bis-9-pandigital sein.
Die C++-, Python- und Java-Implementierungen verwenden zwei Doppelschleifen, die genau die beiden zulässigen Stellenmuster abdecken. Im ersten Teil wird jedes \(a\in\{1,\dots,9\}\) mit jedem vierstelligen \(b\in\{1234,\dots,9876\}\) kombiniert. Im zweiten Teil wird jedes zweistellige \(a\in\{12,\dots,98\}\) mit jedem dreistelligen \(b\in\{123,\dots,987\}\) kombiniert. Unmögliche Formen wie \(3\)-stellig \(\times\) \(3\)-stellig werden dadurch von vornherein ausgeschlossen.
Für jedes Paar wird \(p=ab\) berechnet und anschließend dieselbe Ziffernprüfung auf \(a\), \(b\) und \(p\) angewendet. Die Schleifen bleiben bewusst einfach rechteckig; Ziffern wie \(0\) oder Wiederholungen werden nicht vorher herausgefiltert, weil der gemeinsame Prüfer solche Fälle in konstanter Zeit aussortiert. Auch eine falsche Produktlänge wird so automatisch erkannt: Wenn am Ende nicht genau neun Ziffern gesehen wurden, ist der Kandidat ungültig.
Jedes erfolgreiche Produkt wird in eine Menge eingefügt. Nach Abschluss beider Suchphasen werden die Elemente dieser Menge aufsummiert. Vor der eigentlichen Rechnung führen die Programme außerdem zwei kleine Plausibilitätsprüfungen aus: eine bekannte gültige Identität und eine bekannte ungültige Identität.
Die erste Suchphase betrachtet \(9\times 8643=77{,}787\) Paare, die zweite \(87\times 865=75{,}255\) Paare. Insgesamt werden also \(153{,}042\) Produkte geprüft. Pro Kandidat fallen nur eine Multiplikation und das Lesen von höchstens zehn Dezimalziffern an; der Aufwand pro Kandidat ist somit \(O(1)\).
Der Zifferntest selbst benötigt nur konstanten Arbeitsspeicher. Wachsen kann lediglich die Menge der erfolgreichen Produkte, doch bei Problem 32 bleibt sie sehr klein. Praktisch ist die Laufzeit daher sofortig.
Aranan şey, \(a\times b=p\) özdeşlikleri içinde \(a\), \(b\) ve \(p\) sayılarının ondalık basamaklarının birlikte \(1,2,\dots,9\) rakamlarını tam olarak birer kez kullandığı durumları bulmaktır. Sonuç, başarılı özdeşliklerin değil, farklı ürün değerlerinin toplamıdır; aynı ürün birden fazla geçerli çarpan ayrışımından gelse bile yalnızca bir kez sayılır.
Standart örnek \(39\times 186=7254\) ifadesidir; çünkü \(391867254\) dizisi \(123456789\) dizisinin bir permütasyonudur.
Çözüm sonlu bir arama yapar, fakat arama alanı önce matematiksel olarak daraltılır. Basamak sayıları üzerine kısa bir ispat, yalnızca iki olası çarpan biçimi bırakarak problemi küçültür. Ardından basit bir rakam-kullanım değişmezi her adayı test eder.
\(x=d(a)\), \(y=d(b)\) ve \(z=d(p)\) olsun; burada \(d(n)\), \(n\) sayısının ondalık basamak sayısıdır. Geçerli bir pandijital özdeşlik toplam dokuz basamak kullandığı için
$$x+y+z=9.$$
\(x\) basamaklı bir sayı ile \(y\) basamaklı bir sayının çarpımı ya \(x+y-1\) ya da \(x+y\) basamaklı olur. Dolayısıyla
$$z\in\{x+y-1,\ x+y\}.$$
\(z=x+y\) olsaydı \(9=2(x+y)\) çıkardı ve bu imkansızdır. O halde tek seçenek \(z=x+y-1\) olur; buradan
$$9=x+y+(x+y-1)=2(x+y)-1$$
ve sonuç olarak \(x+y=5\), \(z=4\) elde edilir. Çarpanları basamak sayısına göre sıralayınca geriye tam olarak
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
durumları kalır. Uygulamaların yalnızca \(1\)-basamaklı \(\times\) \(4\)-basamaklı ve \(2\)-basamaklı \(\times\) \(3\)-basamaklı arama yapmasının nedeni budur.
Her aday \((a,b,p)\) için önce \(a\)'nın, sonra \(b\)'nin, sonra da \(p\)'nin basamakları okunur. Adayın geçerli olması için üç koşulun birlikte sağlanması gerekir: hiçbir basamak \(0\) olmamalıdır, hiçbir basamak tekrar etmemelidir ve toplam görülen basamak sayısı tam olarak dokuz olmalıdır. Bu üç koşul gerçekleştiğinde basamak kümesi otomatik olarak \(\{1,2,\dots,9\}\) olur.
Uygulamalar bunu rakamlara göre indekslenen on elemanlı bir doğruluk tablosu ile yapar. Bir \(0\) ya da daha önce görülmüş bir rakam geldiği anda aday hemen reddedilir.
Sorulan toplam, başarılı çarpan ayrışımlarının toplamı değil, farklı ürünlerin toplamıdır. Çünkü aynı ürün birden fazla pandijital özdeşlikten gelebilir. Tipik örnek
$$12\times 483=5796,\qquad 42\times 138=5796$$
eşitliğidir. Her iki özdeşlik de geçerlidir; ancak \(5796\) son toplama yalnızca bir kez eklenmelidir. Bu yüzden başarılı ürünler önce bir kümede tutulur.
Pozitif kontrol örneği
$$39\times 186=7254$$
\((2,3,4)\) durumuna aittir. Basamakları \(3,9,1,8,6,7,2,5,4\) olduğundan ne sıfır vardır ne tekrar, toplam basamak sayısı da dokuzdur; dolayısıyla özdeşlik geçerlidir.
Negatif kontrol örneği
$$12\times 34=408$$
üründe \(0\) bulunduğu için hemen başarısız olur. Ayrıca toplam basamak sayısı yalnızca \(2+2+3=7\) olduğundan zaten 1'den 9'a pandijital olamaz.
C++, Python ve Java uygulamaları yukarıdaki iki basamak desenine karşılık gelen iki iç içe döngü kullanır. İlk bölümde her \(a\in\{1,\dots,9\}\), her dört basamaklı \(b\in\{1234,\dots,9876\}\) ile çarpılır. İkinci bölümde her iki basamaklı \(a\in\{12,\dots,98\}\), her üç basamaklı \(b\in\{123,\dots,987\}\) ile çarpılır. Böylece \(3\)-basamaklı \(\times\) \(3\)-basamaklı gibi imkansız biçimler en baştan elenir.
Her çift için \(p=ab\) hesaplanır ve aynı rakam-kullanım testi \(a\), \(b\) ve \(p\) üzerinde uygulanır. Döngüler bilerek basit dikdörtgen aralıklar halinde tutulur; çarpanların içinde sıfır ya da tekrar olup olmadığı önceden filtrelenmez, çünkü ortak doğrulayıcı bunları sabit zamanda eler. Ürünün yanlış basamak sayısına sahip olması da doğal biçimde yakalanır: toplam görülen basamak sayısı dokuz değilse aday reddedilir.
Bir aday testi geçerse ürün değeri kümeye eklenir. İki arama da tamamlandıktan sonra kümedeki elemanlar toplanır. Ana hesap başlamadan önce her uygulama iki küçük sağlamlık kontrolü de yapar: biri bilinen geçerli bir pandijital özdeşlik, diğeri bilinen geçersiz bir örnek içindir.
İlk arama \(9\times 8643=77{,}787\) çift, ikinci arama \(87\times 865=75{,}255\) çift inceler. Böylece toplam aday sayısı \(153{,}042\) olur. Her aday için bir çarpma ve en fazla on ondalık basamağın taranması gerekir; yani aday başına iş yükü \(O(1)\)'dir.
Rakam doğrulayıcısının çalışma belleği sabittir. Büyüyebilen tek yapı başarılı ürünlerin kümesidir ve Problem 32'de o da çok küçük kalır. Pratikte hesaplama anlıktır.
Se buscan todas las identidades \(a\times b=p\) para las que los dígitos decimales de \(a\), \(b\) y \(p\), tomados en conjunto, usan cada uno de los dígitos \(1,2,\dots,9\) exactamente una vez. La respuesta final no suma identidades, sino productos distintos; por eso un mismo valor de \(p\) debe contarse una sola vez aunque aparezca en varias factorizaciones válidas.
El ejemplo clásico es \(39\times 186=7254\), porque la concatenación \(391867254\) es una permutación de \(123456789\).
La solución sí hace una búsqueda exhaustiva, pero sobre un espacio ya reducido por la aritmética decimal. Primero se demuestra que sólo existen dos repartos posibles de longitudes. Después, un invariante de uso de dígitos decide si cada candidato es realmente pandigital de 1 a 9.
Sea \(x=d(a)\), \(y=d(b)\) y \(z=d(p)\), donde \(d(n)\) es el número de dígitos decimales de \(n\). Como una identidad válida usa en total nueve dígitos, se cumple
$$x+y+z=9.$$
El producto de un número de \(x\) dígitos por otro de \(y\) dígitos tiene \(x+y-1\) o \(x+y\) dígitos. Por tanto
$$z\in\{x+y-1,\ x+y\}.$$
Si ocurriera \(z=x+y\), tendríamos \(9=2(x+y)\), lo cual es imposible. Así que necesariamente \(z=x+y-1\), y entonces
$$9=x+y+(x+y-1)=2(x+y)-1.$$
De aquí se obtiene \(x+y=5\) y \(z=4\). Ordenando los factores por número de dígitos, las únicas posibilidades son
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
Ésa es la razón exacta por la que las implementaciones sólo recorren los casos \(1\)-dígito \(\times\) \(4\)-dígitos y \(2\)-dígitos \(\times\) \(3\)-dígitos.
Para cada triple \((a,b,p)\), se recorren los dígitos de \(a\), luego los de \(b\) y finalmente los de \(p\). El triple es válido si y sólo si se cumplen tres condiciones: ningún dígito es \(0\), ningún dígito se repite y el número total de dígitos vistos es exactamente nueve. En ese momento, el conjunto de dígitos ya tiene que ser \(\{1,2,\dots,9\}\).
Las implementaciones representan esta idea con una tabla booleana de diez posiciones indexada por el dígito. Encontrar un cero o una repetición provoca rechazo inmediato.
El problema pide la suma de productos distintos, no la suma de todas las factorizaciones exitosas. Eso importa porque un mismo producto puede aparecer más de una vez. El ejemplo más conocido es
$$12\times 483=5796,\qquad 42\times 138=5796.$$
Ambas identidades son válidas, pero \(5796\) debe añadirse una sola vez. Por eso los productos aceptados se guardan primero en un conjunto.
El control positivo
$$39\times 186=7254$$
pertenece al caso \((2,3,4)\). Sus dígitos son \(3,9,1,8,6,7,2,5,4\): no hay ceros, no hay repeticiones y el total es nueve, así que la identidad es válida.
El control negativo
$$12\times 34=408$$
falla de inmediato porque el producto contiene el dígito \(0\). Además sólo hay \(2+2+3=7\) dígitos en total, de modo que jamás podría ser pandigital de 1 a 9.
Las implementaciones en C++, Python y Java ejecutan dos búsquedas con bucles anidados que corresponden exactamente a los dos patrones de longitudes. En la primera, cada \(a\in\{1,\dots,9\}\) se combina con cada \(b\in\{1234,\dots,9876\}\). En la segunda, cada \(a\in\{12,\dots,98\}\) se combina con cada \(b\in\{123,\dots,987\}\). Así se descartan desde el principio formas imposibles como \(3\)-dígitos \(\times\) \(3\)-dígitos.
Para cada par, la implementación calcula \(p=ab\) y aplica la misma prueba de uso de dígitos a \(a\), \(b\) y \(p\). Los intervalos se mantienen rectangulares a propósito; no se filtran por adelantado ceros ni repeticiones dentro de los factores, porque el mismo verificador los elimina en tiempo constante. Si la longitud total no es nueve, el candidato queda rechazado automáticamente al final del recorrido de dígitos.
Cada producto que supera la prueba se inserta en un conjunto. Cuando terminan las dos búsquedas, se suman los elementos del conjunto para obtener el resultado pedido. Antes del cálculo principal, los programas también ejecutan dos comprobaciones sencillas: una identidad válida conocida y una identidad inválida conocida.
La primera búsqueda revisa \(9\times 8643=77{,}787\) pares y la segunda \(87\times 865=75{,}255\), para un total de \(153{,}042\) productos candidatos. Cada prueba requiere una multiplicación y el examen de como mucho diez dígitos decimales, así que el coste por candidato es \(O(1)\).
El validador de dígitos usa memoria de trabajo constante. La única estructura que crece es el conjunto de productos correctos, y en este problema su tamaño es muy pequeño. En la práctica el tiempo total es instantáneo.
我们要找出所有满足 \(a\times b=p\) 的等式，使得把 \(a\)、\(b\) 和 \(p\) 的十进制数字连在一起以后，恰好把 \(1,2,\dots,9\) 每个数字各用一次。最终要求的不是这些等式的个数，而是所有不同乘积 \(p\) 的总和；如果同一个乘积可以由多组合法得到，它只能计入一次。
最经典的例子是 \(39\times 186=7254\)，因为串接结果 \(391867254\) 正好是 \(123456789\) 的一个排列。
这道题确实需要枚举，但并不是毫无结构地暴力搜索。先用一个位数方程把可能的情形压缩到两类，再用一个非常直接的数字使用不变量判断候选等式是否真正满足 1 到 9 的 pandigital 条件。
记 \(x=d(a)\)、\(y=d(b)\)、\(z=d(p)\)，其中 \(d(n)\) 表示 \(n\) 的十进制位数。有效等式总共正好使用九个数字，因此有
$$x+y+z=9.$$
一个 \(x\) 位数和一个 \(y\) 位数相乘，乘积的位数只可能是 \(x+y-1\) 或 \(x+y\)。也就是说
$$z\in\{x+y-1,\ x+y\}.$$
如果出现 \(z=x+y\)，那么就会得到 \(9=2(x+y)\)，这是不可能的，因为右边必为偶数。于是只能有 \(z=x+y-1\)，从而
$$9=x+y+(x+y-1)=2(x+y)-1.$$
所以 \(x+y=5\)，并且 \(z=4\)。如果再按位数令前一个因子不长于后一个因子，那么唯一可能的三元组就是
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
这正是实现只搜索两种模式的原因：一位数乘四位数，或者两位数乘三位数。除此以外的位数组合从数学上就不可能成功。
对于每个候选三元组 \((a,b,p)\)，依次读取 \(a\)、\(b\)、\(p\) 的十进制数字。一个候选成立，当且仅当三个条件同时满足：没有数字 \(0\)，没有任何数字重复出现，而且总共恰好读到九个数字。只要这三点都满足，数字集合就必然正好是 \(\{1,2,\dots,9\}\)。
实现里用一个长度为 10 的布尔表记录每个数字是否已经出现。扫描过程中一旦遇到 \(0\) 或者重复数字，就可以立即判定失败，因此大量无效候选会很早被淘汰。
题目要求的是不同乘积之和，而不是所有成功分解式之和。同一个乘积可能对应多组合法，例如
$$12\times 483=5796,\qquad 42\times 138=5796.$$
这两个等式都有效，但 \(5796\) 在最终答案里只能出现一次。因此实现会先把通过检测的乘积放入集合，再对集合求和。
正例
$$39\times 186=7254$$
属于 \((2,3,4)\) 这一类。它的数字依次为 \(3,9,1,8,6,7,2,5,4\)：没有 \(0\)，没有重复，总数恰好是九个，所以它是有效的。
反例
$$12\times 34=408$$
会立刻失败，因为乘积里出现了数字 \(0\)。另外它一共只有 \(2+2+3=7\) 个数字，因此无论如何都不可能构成 1 到 9 的 pandigital 恒等式。
C++、Python 和 Java 实现都采用两层嵌套循环，并且这两轮循环恰好对应上面的两种位数组合。第一轮让每个 \(a\in\{1,\dots,9\}\) 与每个四位数 \(b\in\{1234,\dots,9876\}\) 相乘。第二轮让每个两位数 \(a\in\{12,\dots,98\}\) 与每个三位数 \(b\in\{123,\dots,987\}\) 相乘。这样像三位数乘三位数这种不可能的形状，在进入数字检查之前就已经被排除。
对于每个候选对，先计算 \(p=ab\)，然后把 \(a\)、\(b\)、\(p\) 送入同一个数字使用检测器。循环区间故意保持为简单的矩形范围，而不是提前筛掉含 \(0\) 或内部重复数字的因子，因为统一的检测器已经能以常数时间处理这些情况。若乘积位数不对，也不需要单独写分支；只要最终统计到的数字总数不是九个，候选就会自动失败。
凡是通过检测的候选，其乘积都会加入集合。两轮搜索结束后，再把集合中的元素相加得到最终结果。正式计算之前，程序还会做两个小型自检：一个是已知正确的 pandigital 恒等式，另一个是已知错误的例子。
第一轮搜索检查 \(9\times 8643=77{,}787\) 对，第二轮检查 \(87\times 865=75{,}255\) 对，总计 \(153{,}042\) 个候选乘积。每个候选只需要一次乘法和最多十个十进制数字的扫描，因此单个候选的代价是 \(O(1)\)。对本题固定规模而言，运行时间极小。
数字验证器本身只使用常数级工作内存。唯一会增长的数据结构是存放成功乘积的集合，而在这道题里它非常小。所以整体计算在实践中几乎是瞬间完成的。
Нужно найти все тождества вида \(a\times b=p\), для которых десятичные цифры чисел \(a\), \(b\) и \(p\), взятые вместе, используют каждую из цифр \(1,2,\dots,9\) ровно по одному разу. В ответ входит не сумма всех найденных разложений, а сумма различных произведений \(p\); если одно и то же произведение получается несколькими способами, учитывать его надо только один раз.
Классический пример: \(39\times 186=7254\), потому что конкатенация \(391867254\) является перестановкой \(123456789\).
Решение действительно перебирает кандидатов, но сначала жёстко сокращает область поиска. Небольшое рассуждение о количестве цифр оставляет только два возможных формата разложения, а затем простой инвариант по использованным цифрам проверяет каждый кандидат.
Обозначим \(x=d(a)\), \(y=d(b)\) и \(z=d(p)\), где \(d(n)\) — число десятичных цифр числа \(n\). Поскольку корректное тождество использует всего девять цифр, имеем
$$x+y+z=9.$$
Произведение \(x\)-значного и \(y\)-значного числа имеет либо \(x+y-1\), либо \(x+y\) цифр. Значит,
$$z\in\{x+y-1,\ x+y\}.$$
Случай \(z=x+y\) дал бы равенство \(9=2(x+y)\), что невозможно. Поэтому остаётся только \(z=x+y-1\), и тогда
$$9=x+y+(x+y-1)=2(x+y)-1.$$
Отсюда следует \(x+y=5\) и \(z=4\). Если упорядочить множители по числу цифр, получаем единственные возможные тройки
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
Именно поэтому реализации рассматривают только случаи \(1\)-значное \(\times\) \(4\)-значное и \(2\)-значное \(\times\) \(3\)-значное. Других допустимых шаблонов просто нет.
Для каждого кандидата \((a,b,p)\) последовательно читаются цифры числа \(a\), затем \(b\), затем \(p\). Кандидат корректен тогда и только тогда, когда одновременно выполняются три условия: нигде не встречается цифра \(0\), ни одна цифра не повторяется, и всего просмотрено ровно девять цифр. После этого множество цифр автоматически равно \(\{1,2,\dots,9\}\).
В реализациях это выражено через булев массив из десяти ячеек. Как только появляется ноль или уже встречавшаяся цифра, кандидат немедленно отвергается.
Требуется сумма различных произведений, а не сумма всех успешных разложений. Это важно, потому что одно и то же произведение может возникать в нескольких корректных тождествах. Стандартный пример:
$$12\times 483=5796,\qquad 42\times 138=5796.$$
Обе записи корректны, но \(5796\) должно попасть в итог только один раз. Поэтому успешные произведения сначала складываются в множество.
Положительный контроль
$$39\times 186=7254$$
относится к случаю \((2,3,4)\). Его цифры: \(3,9,1,8,6,7,2,5,4\). Нуля нет, повторов нет, всего девять цифр, значит тождество корректно.
Отрицательный контроль
$$12\times 34=408$$
сразу проваливается, потому что в произведении есть цифра \(0\). Кроме того, суммарно здесь лишь \(2+2+3=7\) цифр, так что такое равенство в принципе не может быть пандигитальным от 1 до 9.
Реализации на C++, Python и Java используют два двойных цикла, точно соответствующих двум разрешённым шаблонам длины. В первой части перебирается каждое \(a\in\{1,\dots,9\}\) вместе с каждым четырёхзначным \(b\in\{1234,\dots,9876\}\). Во второй части перебирается каждое двузначное \(a\in\{12,\dots,98\}\) вместе с каждым трёхзначным \(b\in\{123,\dots,987\}\). Поэтому невозможные формы вроде \(3\)-значное \(\times\) \(3\)-значное заранее исключены.
Для каждой пары вычисляется \(p=ab\), после чего к числам \(a\), \(b\) и \(p\) применяется одна и та же проверка использованных цифр. Диапазоны перебора намеренно оставлены простыми прямоугольными; нули и повторяющиеся цифры внутри множителей заранее не отсекаются, потому что общий валидатор и так отбрасывает такие случаи за постоянное время. Неправильная длина произведения тоже обрабатывается автоматически: если суммарно просмотрено не девять цифр, кандидат отклоняется.
Каждое произведение, прошедшее проверку, добавляется во множество. Когда обе фазы перебора завершены, элементы множества суммируются. Перед основным вычислением программы также выполняют две маленькие проверки: одно заведомо правильное тождество и один заведомо неправильный пример.
Первая фаза просматривает \(9\times 8643=77{,}787\) пар, вторая — \(87\times 865=75{,}255\) пар. Итого проверяется \(153{,}042\) кандидата. На каждый кандидат приходится одна операция умножения и просмотр не более десяти десятичных цифр, то есть стоимость одного теста равна \(O(1)\).
Сам проверяющий механизм использует постоянную рабочую память. Расти может только множество успешных произведений, но для этой задачи оно очень мало. На практике решение работает мгновенно.
نبحث عن جميع المتطابقات \(a\times b=p\) التي تكون فيها الأرقام العشرية لكل من \(a\) و\(b\) و\(p\)، عند جمعها معًا، مستخدمةً للأرقام \(1,2,\dots,9\) مرة واحدة بالضبط لكل رقم. المطلوب في النهاية ليس جمع كل المتطابقات الناجحة، بل جمع قيم المنتجات المختلفة فقط؛ فإذا ظهر نفس المنتج من أكثر من تحليل صحيح فلا بد من احتسابه مرة واحدة.
المثال الأشهر هو \(39\times 186=7254\)، لأن السلسلة \(391867254\) هي مجرد ترتيب مختلف للأرقام \(123456789\).
الحل يعتمد على تعداد منتهٍ، لكنه ليس تعدادًا أعمى. أولًا نقيد أطوال الأعداد بقانون دقيق لعدد الخانات، ثم نستخدم ثابتًا بسيطًا يتعلق باستعمال الأرقام للحكم على كل مرشح.
لنكتب \(x=d(a)\) و\(y=d(b)\) و\(z=d(p)\)، حيث \(d(n)\) هو عدد الخانات العشرية في \(n\). بما أن الهوية الصحيحة تستعمل تسع خانات بالمجموع، فإن
$$x+y+z=9.$$
وحاصل ضرب عدد ذي \(x\) خانات في عدد ذي \(y\) خانات يملك إما \(x+y-1\) خانة أو \(x+y\) خانة. لذلك
$$z\in\{x+y-1,\ x+y\}.$$
ولو كان \(z=x+y\) لحصلنا على \(9=2(x+y)\)، وهذا مستحيل. إذن لا يبقى إلا \(z=x+y-1\)، ومن ثم
$$9=x+y+(x+y-1)=2(x+y)-1.$$
وبالتالي نحصل على \(x+y=5\) و\(z=4\). وإذا رتبنا العاملين حسب عدد الخانات، فالحالتان الوحيدتان الممكنتان هما
$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$
وهذا هو السبب المباشر الذي يجعل التنفيذ يحصر البحث في حالتي عدد من خانة واحدة مع عدد من أربع خانات، أو عدد من خانتين مع عدد من ثلاث خانات.
لكل ثلاثي مرشح \((a,b,p)\)، تُفحص خانات \(a\) ثم \(b\) ثم \(p\). ويكون الثلاثي صالحًا إذا وفقط إذا تحققت ثلاثة شروط معًا: ألا يظهر الرقم \(0\)، وألا يتكرر أي رقم، وأن يكون مجموع الخانات المقروءة مساويًا لتسع خانات تمامًا. وعند تحقق هذه الشروط الثلاثة يكون من الضروري أن تكون مجموعة الأرقام هي بالضبط \(\{1,2,\dots,9\}\).
التنفيذ يمثل هذه الفكرة بمصفوفة منطقية طولها عشرة مفهرسةً بالأرقام. وبمجرد ظهور صفر أو رقم مكرر يُرفض المرشح فورًا.
المطلوب هو مجموع المنتجات المختلفة، لا مجموع طرق التحليل الناجحة. وهذه نقطة مهمة لأن المنتج نفسه قد يظهر في أكثر من هوية pandigital صحيحة. المثال القياسي هو
$$12\times 483=5796,\qquad 42\times 138=5796.$$
كلتا الهويتين صحيحتان، لكن \(5796\) يجب أن يدخل في المجموع النهائي مرة واحدة فقط. لذلك تحتفظ البرامج بالمنتجات الناجحة داخل مجموعة قبل إجراء الجمع.
مثال التحقق الإيجابي
$$39\times 186=7254$$
ينتمي إلى الحالة \((2,3,4)\). أرقامه هي \(3,9,1,8,6,7,2,5,4\): لا يوجد صفر، ولا يوجد تكرار، والمجموع تسع خانات، لذا فهو صحيح.
أما مثال التحقق السلبي
$$12\times 34=408$$
فيفشل مباشرة لأن الناتج يحتوي على الرقم \(0\). كما أن مجموع الخانات فيه هو فقط \(2+2+3=7\)، ولذلك لا يمكن أصلًا أن يكون pandigital من 1 إلى 9.
تستخدم تطبيقات C++ وPython وJava حلقتين متداخلتين تطابقان بالضبط نمطي الخانات المسموحين. في الجزء الأول يُجرب كل \(a\in\{1,\dots,9\}\) مع كل \(b\in\{1234,\dots,9876\}\). وفي الجزء الثاني يُجرب كل \(a\in\{12,\dots,98\}\) مع كل \(b\in\{123,\dots,987\}\). وهكذا تُستبعد من البداية الأشكال المستحيلة مثل \(3\)-خانات \(\times\) \(3\)-خانات.
لكل زوج مرشح يُحسب \(p=ab\)، ثم تُمرر الأعداد \(a\) و\(b\) و\(p\) جميعًا إلى اختبار استعمال الأرقام نفسه. النطاقات تُترك عمدًا في صورة مستطيلات بسيطة، من دون تصفية مسبقة للأصفار أو التكرارات داخل العوامل، لأن أداة التحقق الموحدة ترفض هذه الحالات بزمن ثابت. وحتى إذا كان طول الناتج غير مناسب، فذلك يُكتشف تلقائيًا عندما لا يكون مجموع الخانات المقروءة مساويًا لتسعة.
كل منتج ينجح في الاختبار يُضاف إلى مجموعة. وبعد انتهاء مرحلتي التعداد، تُجمع عناصر المجموعة لإنتاج النتيجة المطلوبة. وقبل الحساب الرئيسي تنفذ البرامج أيضًا فحصين صغيرين: هوية صحيحة معروفة، وهوية غير صحيحة معروفة.
المرحلة الأولى تفحص \(9\times 8643=77{,}787\) زوجًا، والمرحلة الثانية تفحص \(87\times 865=75{,}255\) زوجًا، أي ما مجموعه \(153{,}042\) منتجًا مرشحًا. وكل اختبار يحتاج إلى عملية ضرب واحدة ومسح لما لا يزيد على عشر خانات عشرية، لذا فالكلفة لكل مرشح هي \(O(1)\).
أداة التحقق من الأرقام تستهلك ذاكرة عمل ثابتة فقط. والبنية الوحيدة التي يمكن أن تنمو هي مجموعة المنتجات الصحيحة، لكنها تبقى صغيرة جدًا في هذه المسألة. عمليًا يكون التنفيذ فوريًا.