For each positive integer \(n\), define \(d(n)\) as the smallest positive multiple of \(n\) whose decimal expansion uses at most two distinct digits; such a number is called a duodigit. The task is to evaluate
$$D(k)=\sum_{n=1}^{k} d(n).$$
A direct search through multiples of \(n\) is far too slow, because the first valid multiple can be much larger than \(n\) and can have many digits. The implementation instead rewrites the digit pattern as a modular subset-sum problem and searches by increasing decimal length.
The key idea is to describe every candidate duodigit of a fixed length in a uniform algebraic way. That turns the divisibility test into a congruence and lets us search over residue classes instead of enumerating all decimal strings.
Fix a decimal length \(t\ge 1\) and a leading digit \(f\in\{1,\ldots,9\}\). Let the second digit be \(f+g\), where
$$-f \le g \le 9-f,\qquad g\ne 0.$$
The repeated-digit backbone is the repunit-scaled number
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
If \(S\subseteq \{0,1,\ldots,t-2\}\) is the set of non-leading positions where we replace \(f\) by \(f+g\), then the candidate number is
$$N=fR_t+g\sum_{j\in S}10^j.$$
The leading position is excluded from \(S\), so the first digit stays equal to \(f\). The special one-digit-value case is simply the empty choice \(S=\varnothing\), which gives \(N=fR_t\).
Let
$$s(S)=\sum_{j\in S}10^j.$$
Then \(n\mid N\) is equivalent to
$$g\,s(S)\equiv -fR_t \pmod n.$$
Write
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
This congruence has a solution only if \(d\mid r\). When that happens we divide by \(d\) and obtain
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
Now \(\gcd(g/d,n/d)=1\), so \((g/d)^{-1}\) exists modulo \(n/d\). Therefore all valid residues are described by
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
Viewed modulo \(n\), that means the acceptable residues are
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
So the arithmetic test for a digit pair \(\{f,f+g\}\) reduces to a short list of target residue classes.
For length \(t\), the adjustable place values are \(1,10,\ldots,10^{t-2}\). The implementation assigns these powers of ten to two groups, say \(X\) and \(Y\), and treats the chosen set as a union \(S=A\cup B\) with \(A\subseteq X\) and \(B\subseteq Y\).
For each half we care about two quantities:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
and similarly for \(B\). Then
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
This is a meet-in-the-middle decomposition: if a target residue \(w\) is required, we only need residues \(x\) from the first half and \(y\) from the second half such that
$$x+y\equiv w\pmod n.$$
For fixed \(t\), \(f\), and \(g\), the base term \(fR_t\) is constant, so minimizing \(N\) is the same as optimizing \(s(S)\) in
$$N=fR_t+g\,s(S).$$
If \(g\gt 0\), a smaller subset sum gives a smaller number, so we only need the minimum value of \(\sigma\) for each residue. If \(g\lt 0\), a larger subset sum gives a smaller number, so we only need the maximum value of \(\sigma\) for each residue.
That is why each residue class stores just two extremal values: the smallest attainable subset sum and the largest attainable subset sum. Full lists of subsets are unnecessary.
The search proceeds through lengths \(t=1,2,3,\ldots\). At each new length, the repeated-digit backbone \(fR_t\) is updated, and one more lower place value \(10^{t-1}\) becomes available for future subset choices.
When a new weight \(10^j\) is added to one residue collection, every existing subset either keeps that weight out or includes it. So each stored residue \(u\) generates a shifted residue
$$u+10^j \pmod n,$$
and the corresponding subset sum increases by \(10^j\). The implementation inserts the new place value into whichever side is cheaper to expand, which keeps the two tables practical while preserving exactly the same set of possible totals.
There is also a useful special case: if \(10\mid n\), then every multiple of \(n\) must end in \(0\), so the second digit must be \(0\). In the formula above that means \(g=-f\), and all other offsets can be skipped.
For \(n=12\), take length \(t=2\), leading digit \(f=1\), and offset \(g=1\). Then \(R_2=11\), and choosing \(S=\{0\}\) gives
$$N=1\cdot 11+1\cdot 1=12.$$
In congruence form,
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
so \(s(S)=1\) works immediately.
For \(n=103\), a negative offset is needed. Take \(t=3\), \(f=5\), and \(g=-4\). With \(S=\{1\}\),
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
and indeed \(515=5\cdot 103\). This illustrates why the search must support both \(g\gt 0\) and \(g\lt 0\).
The C++ implementation performs the actual number-theoretic search. For each admissible digit offset \(g\in\{-9,\ldots,-1,1,\ldots,9\}\), it precomputes the gcd reduction data and the modular inverse needed to solve the congruence modulo \(n/d\). That lets it reject impossible digit pairs quickly and turn every possible pair into a small list of target residues.
Two residue tables are maintained. Each table starts with the empty subset, and whenever a new lower place value \(10^j\) is introduced, the chosen table updates all of its reachable residues by considering both possibilities: exclude \(10^j\) or include \(10^j\). For every residue class modulo \(n\), the table keeps only the smallest and largest actual subset sums that realize that residue.
For the current length \(t\) and leading digit \(f\), the implementation first tests the repeated-digit number \(fR_t\). If that does not work, it tries every valid second digit. For each admissible target residue \(w\), it joins the two tables by checking which residue \(x\) from the first table can be paired with residue \(w-x\) from the second. The stored extremal subset sums then reconstruct the smallest numeric candidate for that sign of \(g\).
After \(d(n)\) has been found, the C++ implementation adds it to the running total. For large \(k\), the range \(1,\ldots,k\) is split into chunks and processed in parallel by worker threads, then the partial sums are added exactly. The Python and Java implementations do not rederive the mathematics; they invoke the same compiled core and parse its printed result.
For a fixed \(n\), each residue table has at most \(n\) residue classes. Adding one new power of ten to a table therefore costs \(O(n)\) time in the worst case, because every currently reachable residue may create one shifted state. The join step also works over residue classes rather than over all subsets.
If the smallest duodigit multiple of \(n\) has length \(t_n\), the search for that \(n\) uses \(O(t_n n)\) memory-time scale up to small constant factors coming from the finite set of digit offsets. This is dramatically smaller than a naive exploration of all \(2^{t_n-1}\) subsets of lower positions.
For the outer sum, the total work is
$$\sum_{n=1}^{k} O(t_n n),$$
and the implementation parallelizes this sum across CPU cores because the values \(d(1),d(2),\ldots,d(k)\) are independent.
Für jede positive ganze Zahl \(n\) sei \(d(n)\) das kleinste positive Vielfache von \(n\), dessen Dezimalschreibweise höchstens zwei verschiedene Ziffern enthält; eine solche Zahl heißt Duodigit. Gesucht ist
$$D(k)=\sum_{n=1}^{k} d(n).$$
Eine direkte Suche über die Vielfachen von \(n\) ist viel zu langsam, weil das erste gültige Vielfache sehr groß werden und viele Stellen besitzen kann. Die Implementierung formt die Ziffernbedingung daher in ein modulares Teilmengen-Summenproblem um und durchsucht die Kandidaten nach wachsender Dezimallänge.
Die Grundidee besteht darin, jedes Duodigit fester Länge algebraisch einheitlich zu beschreiben. Dadurch wird die Teilbarkeitsbedingung zu einer Kongruenz, und statt aller Dezimalstrings müssen nur Restklassen untersucht werden.
Fixiere eine Dezimallänge \(t\ge 1\) und eine führende Ziffer \(f\in\{1,\ldots,9\}\). Die zweite Ziffer sei \(f+g\), wobei
$$-f \le g \le 9-f,\qquad g\ne 0.$$
Das Rückgrat aus gleichen Ziffern ist
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
Ist \(S\subseteq \{0,1,\ldots,t-2\}\) die Menge der nichtführenden Positionen, an denen \(f\) durch \(f+g\) ersetzt wird, dann hat der Kandidat die Form
$$N=fR_t+g\sum_{j\in S}10^j.$$
Die führende Stelle gehört nicht zu \(S\), also bleibt die erste Ziffer gleich \(f\). Der Spezialfall mit nur einer Ziffernart entspricht \(S=\varnothing\) und liefert \(N=fR_t\).
Setze
$$s(S)=\sum_{j\in S}10^j.$$
Dann ist \(n\mid N\) äquivalent zu
$$g\,s(S)\equiv -fR_t \pmod n.$$
Schreibe
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
Eine Lösung existiert nur dann, wenn \(d\mid r\). Ist das erfüllt, so teilen wir durch \(d\) und erhalten
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
Nun gilt \(\gcd(g/d,n/d)=1\), also existiert \((g/d)^{-1}\) modulo \(n/d\). Damit sind alle zulässigen Reste beschrieben durch
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
Modulo \(n\) sind die möglichen Reste also
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
Der arithmetische Test für ein Ziffernpaar \(\{f,f+g\}\) schrumpft damit auf eine kurze Liste von Zielrestklassen.
Für Länge \(t\) sind die veränderbaren Stellenwerte \(1,10,\ldots,10^{t-2}\). Die Implementierung verteilt diese Zehnerpotenzen auf zwei Gruppen \(X\) und \(Y\) und schreibt die ausgewählte Menge als Vereinigung \(S=A\cup B\) mit \(A\subseteq X\) und \(B\subseteq Y\).
Für jede Hälfte sind zwei Größen wichtig:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
und entsprechend für \(B\). Dann gilt
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
Das ist eine Meet-in-the-Middle-Zerlegung: Wenn ein Zielrest \(w\) vorgegeben ist, genügen Reste \(x\) aus der ersten Hälfte und \(y\) aus der zweiten Hälfte mit
$$x+y\equiv w\pmod n.$$
Für feste Werte \(t\), \(f\) und \(g\) ist der Basisterm \(fR_t\) konstant. \(N\) wird also durch
$$N=fR_t+g\,s(S)$$
bestimmt. Bei \(g\gt 0\) liefert eine kleinere Teilmengensumme eine kleinere Zahl, also braucht man pro Restklasse nur das Minimum von \(\sigma\). Bei \(g\lt 0\) liefert eine größere Teilmengensumme die kleinere Zahl, also reicht das Maximum von \(\sigma\).
Darum speichert jede Restklasse genau zwei Extremwerte: die kleinste und die größte erreichbare Teilmengensumme. Vollständige Listen aller Teilmengen sind unnötig.
Die Durchmusterung läuft über die Längen \(t=1,2,3,\ldots\). Für jede neue Länge wird das Rückgrat \(fR_t\) aktualisiert, und ein weiterer niedriger Stellenwert \(10^{t-1}\) steht künftig für Teilmengen zur Verfügung.
Wird ein neues Gewicht \(10^j\) zu einer Restmenge hinzugefügt, dann kann jede bisherige Teilmenge dieses Gewicht entweder ignorieren oder aufnehmen. Aus jedem gespeicherten Rest \(u\) entsteht also ein verschobener Rest
$$u+10^j \pmod n,$$
während die zugehörige Teilmengensumme um \(10^j\) wächst. Die Implementierung fügt den neuen Stellenwert jeweils auf der billigeren Seite ein, damit beide Tabellen handhabbar bleiben, ohne dass mögliche Gesamtsummen verloren gehen.
Es gibt außerdem einen wichtigen Spezialfall: Ist \(10\mid n\), dann muss jedes Vielfache von \(n\) auf \(0\) enden. Also muss die zweite Ziffer \(0\) sein, was in der Formel \(g=-f\) bedeutet; alle anderen Offsets können übersprungen werden.
Für \(n=12\) nehmen wir \(t=2\), \(f=1\) und \(g=1\). Dann ist \(R_2=11\), und mit \(S=\{0\}\) erhalten wir
$$N=1\cdot 11+1\cdot 1=12.$$
In Kongruenzschreibweise gilt
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
also funktioniert \(s(S)=1\) sofort.
Für \(n=103\) braucht man einen negativen Offset. Mit \(t=3\), \(f=5\), \(g=-4\) und \(S=\{1\}\) folgt
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
und tatsächlich ist \(515=5\cdot 103\). Das zeigt, warum die Suche sowohl \(g\gt 0\) als auch \(g\lt 0\) unterstützen muss.
Die eigentliche zahlentheoretische Suche steckt in der C++-Implementierung. Für jedes zulässige Ziffernoffset \(g\in\{-9,\ldots,-1,1,\ldots,9\}\) berechnet sie vorab die ggT-Reduktion und das modulare Inverse, das zur Lösung der Kongruenz modulo \(n/d\) benötigt wird. So lassen sich unmögliche Ziffernpaare sofort verwerfen, und jedes verbleibende Paar wird auf wenige Zielreste reduziert.
Es werden zwei Resttabellen geführt. Beide starten mit der leeren Teilmenge. Sobald ein neuer niedriger Stellenwert \(10^j\) hinzukommt, aktualisiert die gewählte Tabelle alle erreichbaren Reste durch die beiden Möglichkeiten: \(10^j\) nicht verwenden oder \(10^j\) verwenden. Für jede Restklasse modulo \(n\) werden nur die kleinste und die größte reale Teilmengensumme gespeichert, die diesen Rest erzeugen.
Für die aktuelle Länge \(t\) und die führende Ziffer \(f\) prüft die Implementierung zuerst die Zahl \(fR_t\) mit nur einer Ziffernart. Falls das nicht genügt, werden alle gültigen zweiten Ziffern getestet. Für jeden zulässigen Zielrest \(w\) verbindet sie die beiden Tabellen, indem geprüft wird, welcher Rest \(x\) aus der ersten Tabelle mit dem Rest \(w-x\) aus der zweiten Tabelle zusammenpasst. Aus den gespeicherten Extremwerten wird dann der kleinste numerische Kandidat für dieses Vorzeichen von \(g\) rekonstruiert.
Sobald \(d(n)\) feststeht, addiert die C++-Implementierung den Wert zur Gesamtsumme. Für große \(k\) wird der Bereich \(1,\ldots,k\) in Blöcke zerlegt und von mehreren Threads parallel verarbeitet; danach werden die Teilsummen exakt aufsummiert. Die Python- und Java-Implementierungen leiten die Mathematik nicht neu her, sondern rufen denselben kompilierten Kern auf und lesen dessen Ausgabe ein.
Für festes \(n\) besitzt jede Resttabelle höchstens \(n\) Restklassen. Das Hinzufügen einer neuen Zehnerpotenz kostet daher im schlimmsten Fall \(O(n)\) Zeit, weil jeder bisher erreichbare Rest einen verschobenen Zustand erzeugen kann. Auch der Verknüpfungsschritt arbeitet über Restklassen statt über alle Teilmengen.
Hat das kleinste Duodigit-Vielfache von \(n\) die Länge \(t_n\), dann liegt der Aufwand für dieses \(n\) bei \(O(t_n n)\) bis auf kleine konstante Faktoren aus der endlichen Menge möglicher Offsets. Das ist erheblich besser als eine naive Suche über alle \(2^{t_n-1}\) Teilmengen der unteren Positionen.
Für die äußere Summe ergibt sich insgesamt
$$\sum_{n=1}^{k} O(t_n n),$$
wobei die Implementierung diese Arbeit über mehrere CPU-Kerne parallelisiert, weil die Werte \(d(1),d(2),\ldots,d(k)\) unabhängig voneinander sind.
Her pozitif tamsayı \(n\) için \(d(n)\), ondalık gösteriminde en fazla iki farklı rakam kullanan en küçük pozitif \(n\) katı olarak tanımlanır; böyle sayılara duodigit denir. Amaç
$$D(k)=\sum_{n=1}^{k} d(n)$$
toplamını hesaplamaktır.
\(n\)'in katlarını tek tek taramak pratik değildir; çünkü ilk uygun kat, \(n\)'den çok daha büyük olabilir ve çok sayıda basamak içerebilir. Bu yüzden uygulama, rakam kısıtını modüler bir altküme-toplam problemine dönüştürüp aramayı basamak sayısını artırarak yapar.
Ana fikir, sabit basamak uzunluğundaki her aday duodigit sayıyı tek tip bir cebirsel biçimde yazmaktır. Böylece bölünebilme testi bir kongruansa dönüşür ve bütün ondalık dizeleri üretmek yerine yalnızca kalan sınıfları üzerinde çalışmak yeterli olur.
Bir \(t\ge 1\) basamak uzunluğu ve baştaki rakam \(f\in\{1,\ldots,9\}\) seçilsin. İkinci rakam \(f+g\) olsun; burada
$$-f \le g \le 9-f,\qquad g\ne 0.$$
Aynı rakamın tekrarından oluşan omurga sayı
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f$$
şeklindedir. Eğer \(S\subseteq \{0,1,\ldots,t-2\}\), \(f\) yerine \(f+g\) yazılacak başta olmayan pozisyonların kümesiyse aday sayı
$$N=fR_t+g\sum_{j\in S}10^j$$
olur. En soldaki basamak \(S\)'ye dahil edilmez; böylece ilk rakam hep \(f\) kalır. Tek rakam türü içeren özel durum ise \(S=\varnothing\) olup \(N=fR_t\) verir.
Şunu tanımlayalım:
$$s(S)=\sum_{j\in S}10^j.$$
O zaman \(n\mid N\) koşulu
$$g\,s(S)\equiv -fR_t \pmod n$$
ile eşdeğerdir. Burada
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n)$$
yazalım. Çözüm ancak \(d\mid r\) ise vardır. Bu sağlanınca denklemi \(d\) ile bölüp
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}$$
elde ederiz. Artık \(\gcd(g/d,n/d)=1\) olduğundan \((g/d)^{-1}\) modulo \(n/d\) vardır ve bütün uygun kalanlar
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}$$
biçimindedir. Modulo \(n\) açısından bu şu listeyi verir:
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
Yani \(\{f,f+g\}\) rakam çifti için aritmetik test, kısa bir hedef kalan listesine indirgenmiş olur.
Uzunluk \(t\) için ayarlanabilir basamak değerleri \(1,10,\ldots,10^{t-2}\)'dir. Uygulama bu on kuvvetlerini iki gruba ayırır; bunlara \(X\) ve \(Y\) diyelim. Seçilen küme de \(S=A\cup B\) olacak şekilde \(A\subseteq X\), \(B\subseteq Y\) biçiminde yazılır.
Her yarı için iki nicelik tutulur:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
ve aynı tanım \(B\) için de geçerlidir. Böylece
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n$$
olur. Bu tam bir meet-in-the-middle ayrımıdır: hedef kalan \(w\) verilince, yalnızca
$$x+y\equiv w\pmod n$$
eşitliğini sağlayan \(x\) ve \(y\) kalanlarını eşleştirmek yeterlidir.
Sabit \(t\), \(f\) ve \(g\) için temel terim \(fR_t\) değişmez. Dolayısıyla \(N\)'yi küçültmek
$$N=fR_t+g\,s(S)$$
ifadesindeki \(s(S)\)'yi uygun yönde seçmek demektir. \(g\gt 0\) ise daha küçük altküme toplamı daha küçük sayı üretir; bu yüzden her kalan sınıfı için yalnızca \(\sigma\)'nın minimum değeri gerekir. \(g\lt 0\) ise daha büyük altküme toplamı daha küçük sayı üretir; o durumda yalnızca maksimum değer gerekir.
Bu nedenle her kalan sınıfında sadece iki uç değer saklanır: o kalanı veren en küçük ve en büyük gerçek altküme toplamı. Bütün altkümeleri saklamaya gerek yoktur.
Arama \(t=1,2,3,\ldots\) uzunlukları üzerinde yürür. Her yeni uzunlukta \(fR_t\) omurgası güncellenir ve gelecekte seçilebilecek bir alt basamak değeri \(10^{t-1}\) daha kullanılabilir hale gelir.
Yeni bir \(10^j\) ağırlığı bir kalan kümesine eklendiğinde, var olan her altküme bu ağırlığı ya alır ya almaz. Böylece her kayıtlı \(u\) kalanı için
$$u+10^j \pmod n$$
şeklinde kaymış yeni bir kalan oluşur ve ilgili altküme toplamı \(10^j\) kadar artar. Uygulama, yeni basamak değerini genişletmesi daha ucuz olan tarafa ekler; böylece iki tablo pratik boyutta kalırken mümkün olan toplamların hiçbiri kaybolmaz.
Önemli bir özel durum da vardır: Eğer \(10\mid n\) ise her \(n\) katı \(0\) ile bitmelidir. O halde ikinci rakam mutlaka \(0\) olmalıdır; formülde bu \(g=-f\) demektir ve diğer bütün offset değerleri atlanabilir.
\(n=12\) için \(t=2\), \(f=1\), \(g=1\) alalım. \(R_2=11\) ve \(S=\{0\}\) seçilirse
$$N=1\cdot 11+1\cdot 1=12$$
elde edilir. Kongruans biçiminde
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12}$$
olduğundan \(s(S)=1\) hemen çalışır.
\(n=103\) için negatif offset gerekir. \(t=3\), \(f=5\), \(g=-4\) ve \(S=\{1\}\) alırsak
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
ve gerçekten \(515=5\cdot 103\) olur. Bu da aramanın hem \(g\gt 0\) hem \(g\lt 0\) durumlarını desteklemek zorunda olduğunu gösterir.
Asıl sayı kuramı araması C++ uygulamasında yapılır. Uygulama, izin verilen her rakam ofseti \(g\in\{-9,\ldots,-1,1,\ldots,9\}\) için önce EBOB indirgemesini ve kongruansı \(n/d\) modunda çözmekte kullanılacak modüler tersi hazırlar. Böylece imkansız rakam çiftleri çok erken elenir ve geriye kalan her çift küçük bir hedef kalan listesine dönüşür.
İki adet kalan tablosu tutulur. Her tablo boş altküme ile başlar. Yeni bir alt basamak değeri \(10^j\) geldiğinde, seçilen tablo bütün erişilebilir kalanlarını iki olasılıkla günceller: \(10^j\)'yi dışarıda bırakmak veya dahil etmek. Modulo \(n\) her kalan sınıfı için yalnızca o kalanı üreten en küçük ve en büyük gerçek altküme toplamı saklanır.
Geçerli uzunluk \(t\) ve baş rakam \(f\) için uygulama önce tek-rakamlı tekrar sayısı \(fR_t\)'yi sınar. Bu yetmezse her uygun ikinci rakam denenir. Her uygun hedef kalan \(w\) için iki tablo birleştirilir: birinci tablodaki \(x\) kalanı, ikinci tablodaki \(w-x\) kalanı ile eşleştirilirse toplam doğru kalanı verir. Saklanan uç değerler de o \(g\) işareti için en küçük sayısal adayı yeniden kurar.
\(d(n)\) bulunduğunda C++ uygulaması bunu toplamın üzerine ekler. Büyük \(k\) değerlerinde \(1,\ldots,k\) aralığı bloklara ayrılıp iş parçacıkları arasında paylaştırılır; sonra kısmi toplamlar tam olarak birleştirilir. Python ve Java uygulamaları bu matematiği yeniden yazmaz; aynı derlenmiş çekirdeği çağırır ve üretilen sonucu ayrıştırır.
Sabit bir \(n\) için her kalan tablosunda en fazla \(n\) farklı kalan sınıfı bulunur. Yeni bir on kuvveti eklemek, en kötü durumda \(O(n)\) zaman alır; çünkü erişilebilir her kalan bir kaymış durum üretebilir. Birleştirme adımı da bütün altkümeler üzerinde değil, kalan sınıfları üzerinde çalışır.
\(n\) için en küçük duodigit katın uzunluğu \(t_n\) ise, bu \(n\) üzerindeki aramanın maliyeti olası ofsetlerin sabit sayıda olmasından gelen küçük katsayılar dışında \(O(t_n n)\) ölçeğindedir. Bu, alt basamakların bütün \(2^{t_n-1}\) altkümelerini denemekten çok daha iyidir.
Dış toplam için toplam iş yükü
$$\sum_{n=1}^{k} O(t_n n)$$
şeklindedir. Uygulama, \(d(1),d(2),\ldots,d(k)\) değerleri birbirinden bağımsız olduğu için bu işi çok çekirdekli biçimde paralelleştirir.
Para cada entero positivo \(n\), se define \(d(n)\) como el menor múltiplo positivo de \(n\) cuya expansión decimal usa como mucho dos dígitos distintos; a ese tipo de número se le llama duodigit. El objetivo es calcular
$$D(k)=\sum_{n=1}^{k} d(n).$$
Buscar directamente entre los múltiplos de \(n\) es inviable, porque el primer múltiplo válido puede ser mucho mayor que \(n\) y puede tener bastantes cifras. Por eso la implementación transforma la restricción sobre los dígitos en un problema modular de suma de subconjuntos y recorre los candidatos por longitud decimal creciente.
La idea central es describir de manera algebraica uniforme cualquier duodigit de longitud fija. Con ello, la condición de divisibilidad pasa a ser una congruencia, y ya no hace falta enumerar todas las cadenas decimales posibles.
Fijemos una longitud decimal \(t\ge 1\) y un dígito inicial \(f\in\{1,\ldots,9\}\). El segundo dígito será \(f+g\), con
$$-f \le g \le 9-f,\qquad g\ne 0.$$
La columna vertebral formada por el mismo dígito repetido es
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
Si \(S\subseteq \{0,1,\ldots,t-2\}\) es el conjunto de posiciones no iniciales donde sustituimos \(f\) por \(f+g\), entonces el candidato queda
$$N=fR_t+g\sum_{j\in S}10^j.$$
La posición inicial no pertenece a \(S\), así que la primera cifra sigue siendo \(f\). El caso especial de una sola cifra repetida corresponde a \(S=\varnothing\), y da \(N=fR_t\).
Definamos
$$s(S)=\sum_{j\in S}10^j.$$
Entonces \(n\mid N\) equivale a
$$g\,s(S)\equiv -fR_t \pmod n.$$
Escribimos
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
Solo hay solución si \(d\mid r\). En ese caso dividimos entre \(d\) y obtenemos
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
Como \(\gcd(g/d,n/d)=1\), existe \((g/d)^{-1}\) módulo \(n/d\). Por tanto, todos los residuos válidos vienen dados por
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
Vistos módulo \(n\), los residuos aceptables son
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
Así, la prueba aritmética para un par de dígitos \(\{f,f+g\}\) queda reducida a una lista corta de clases residuales objetivo.
Para una longitud \(t\), los pesos ajustables son \(1,10,\ldots,10^{t-2}\). La implementación reparte esas potencias de diez entre dos grupos, digamos \(X\) y \(Y\), y expresa el conjunto elegido como \(S=A\cup B\), con \(A\subseteq X\) y \(B\subseteq Y\).
En cada mitad importan dos cantidades:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
y análogamente para \(B\). Entonces
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
Esto es una descomposición meet-in-the-middle: si se exige un residuo objetivo \(w\), basta encontrar residuos \(x\) y \(y\) tales que
$$x+y\equiv w\pmod n.$$
Con \(t\), \(f\) y \(g\) fijos, el término base \(fR_t\) es constante. Minimizar \(N\) equivale a optimizar \(s(S)\) en
$$N=fR_t+g\,s(S).$$
Si \(g\gt 0\), una suma de subconjunto más pequeña produce un número más pequeño, así que por cada residuo solo hace falta el mínimo valor posible de \(\sigma\). Si \(g\lt 0\), una suma más grande produce un número más pequeño, así que solo hace falta el máximo.
Por eso cada clase residual guarda únicamente dos extremos: la menor y la mayor suma real de subconjunto que producen ese residuo. No es necesario guardar todas las combinaciones.
La búsqueda recorre las longitudes \(t=1,2,3,\ldots\). En cada nueva longitud se actualiza la base repetida \(fR_t\), y aparece un nuevo peso inferior \(10^{t-1}\) que podrá usarse en futuras selecciones.
Cuando se añade un nuevo peso \(10^j\) a una colección de residuos, cada subconjunto existente puede dejarlo fuera o incluirlo. Así, de cada residuo almacenado \(u\) nace un residuo desplazado
$$u+10^j \pmod n,$$
mientras que la suma real del subconjunto aumenta en \(10^j\). La implementación inserta el nuevo peso en el lado cuya expansión resulta más barata, manteniendo las dos tablas manejables sin perder ninguna suma posible.
También hay un caso especial importante: si \(10\mid n\), cualquier múltiplo de \(n\) debe terminar en \(0\). Entonces el segundo dígito tiene que ser \(0\); en la fórmula eso significa \(g=-f\), y todos los demás desplazamientos pueden omitirse.
Para \(n=12\), tomemos \(t=2\), \(f=1\) y \(g=1\). Entonces \(R_2=11\), y con \(S=\{0\}\) obtenemos
$$N=1\cdot 11+1\cdot 1=12.$$
En forma de congruencia,
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
de modo que \(s(S)=1\) funciona de inmediato.
Para \(n=103\) hace falta un desplazamiento negativo. Si tomamos \(t=3\), \(f=5\), \(g=-4\) y \(S=\{1\}\), resulta
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
y en efecto \(515=5\cdot 103\). Esto muestra por qué la búsqueda debe contemplar tanto \(g\gt 0\) como \(g\lt 0\).
La búsqueda aritmética real vive en la implementación de C++. Para cada desplazamiento de dígitos permitido \(g\in\{-9,\ldots,-1,1,\ldots,9\}\), precalcula la reducción por el máximo común divisor y el inverso modular que hace falta para resolver la congruencia módulo \(n/d\). Así puede descartar enseguida los pares de dígitos imposibles y convertir cada par restante en una lista pequeña de residuos objetivo.
Se mantienen dos tablas de residuos. Cada tabla empieza con el subconjunto vacío. Cuando entra un nuevo peso inferior \(10^j\), la tabla elegida actualiza todos sus residuos alcanzables considerando las dos posibilidades: excluir \(10^j\) o incluirlo. Para cada clase residual módulo \(n\), solo conserva la menor y la mayor suma real de subconjunto que producen dicho residuo.
Para la longitud actual \(t\) y el dígito inicial \(f\), la implementación primero prueba el número repetido \(fR_t\). Si eso no basta, recorre todos los segundos dígitos válidos. Para cada residuo objetivo \(w\), une las dos tablas comprobando qué residuo \(x\) de la primera puede emparejarse con el residuo \(w-x\) de la segunda. A partir de los extremos almacenados reconstruye el menor candidato numérico compatible con ese signo de \(g\).
Una vez hallado \(d(n)\), la implementación de C++ lo suma al acumulado total. Para valores grandes de \(k\), el intervalo \(1,\ldots,k\) se divide en bloques y se procesa en paralelo mediante varios hilos; luego las sumas parciales se agregan exactamente. Las implementaciones en Python y Java no reimplementan la teoría; llaman al mismo núcleo compilado y analizan la salida final.
Para un \(n\) fijo, cada tabla tiene como mucho \(n\) clases residuales. Añadir una nueva potencia de diez cuesta por tanto \(O(n)\) tiempo en el peor caso, porque cada residuo alcanzable puede generar un estado desplazado. El paso de combinación también trabaja sobre clases residuales, no sobre todos los subconjuntos.
Si el menor múltiplo duodigit de \(n\) tiene longitud \(t_n\), la búsqueda para ese \(n\) opera en escala \(O(t_n n)\), salvo factores constantes pequeños procedentes del conjunto finito de desplazamientos posibles. Eso es muchísimo mejor que explorar ingenuamente los \(2^{t_n-1}\) subconjuntos de las posiciones bajas.
Para la suma exterior, el trabajo total es
$$\sum_{n=1}^{k} O(t_n n),$$
y la implementación lo paraleliza entre varios núcleos de CPU porque los valores \(d(1),d(2),\ldots,d(k)\) son independientes.
对每个正整数 \(n\)，定义 \(d(n)\) 为最小的正倍数，并且它的十进制表示中至多只出现两种不同数字；这种数称为 duodigit。题目要求计算
$$D(k)=\sum_{n=1}^{k} d(n).$$
如果直接枚举 \(n\) 的倍数，会很快变得不可行，因为第一个满足条件的倍数可能远大于 \(n\)，而且位数可能很多。实现采用的做法是把“只允许两种数字”这个条件改写成一个模意义下的子集和问题，然后按十进制长度逐层搜索。
核心思路是：对固定长度的候选 duodigit 给出统一的代数表达式。这样一来，可整除条件就会变成一个同余方程，搜索对象也从所有十进制字符串变成了少量的剩余类。
固定一个十进制长度 \(t\ge 1\)，再固定首位数字 \(f\in\{1,\ldots,9\}\)。设第二种数字为 \(f+g\)，其中
$$-f \le g \le 9-f,\qquad g\ne 0.$$
先看所有位都等于 \(f\) 的骨架数：
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
如果 \(S\subseteq \{0,1,\ldots,t-2\}\) 表示所有“非首位且要从 \(f\) 改成 \(f+g\)”的位置，那么候选数可以写成
$$N=fR_t+g\sum_{j\in S}10^j.$$
这里故意不让首位进入 \(S\)，因此最高位始终保持为 \(f\)。只有一种数字的特殊情况就是 \(S=\varnothing\)，这时 \(N=fR_t\)。
定义
$$s(S)=\sum_{j\in S}10^j.$$
那么 \(n\mid N\) 等价于
$$g\,s(S)\equiv -fR_t \pmod n.$$
记
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
这个方程有解的必要且充分条件是 \(d\mid r\)。若条件成立，就可以两边同除以 \(d\)，得到
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
由于 \(\gcd(g/d,n/d)=1\)，所以 \((g/d)^{-1}\) 在模 \(n/d\) 下存在，从而全部可行剩余类满足
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
如果把它重新看成模 \(n\) 的剩余类，那么可接受的取值是
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
也就是说，对某个数字对 \(\{f,f+g\}\) 来说，算术条件最终只剩下一小批目标剩余类需要命中。
对于长度 \(t\)，可调整的位置权重是 \(1,10,\ldots,10^{t-2}\)。实现把这些十的幂分到两个集合中，记为 \(X\) 和 \(Y\)，并把最终选择集写成 \(S=A\cup B\)，其中 \(A\subseteq X\)，\(B\subseteq Y\)。
对每一半，都记录两个量：
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
\(B\) 也同理。于是
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
这正是一个 meet-in-the-middle 结构：如果我们需要总剩余类 \(w\)，只要找到一边的剩余类 \(x\) 与另一边的剩余类 \(y\)，满足
$$x+y\equiv w\pmod n$$
即可。
在固定 \(t\)、\(f\)、\(g\) 的情况下，基础项 \(fR_t\) 是常数，因此最小化 \(N\) 等价于优化
$$N=fR_t+g\,s(S).$$
若 \(g\gt 0\)，则 \(s(S)\) 越小，\(N\) 越小，所以每个剩余类只需要记录能达到它的 最小 子集和。若 \(g\lt 0\)，则 \(s(S)\) 越大，\(N\) 越小，因此只需要记录 最大 子集和。
这就是为什么实现中对每个剩余类只保留两个极值：能产生该剩余类的最小真实和与最大真实和，而不是保存所有子集。
搜索按 \(t=1,2,3,\ldots\) 的顺序推进。每增加一位，骨架数 \(fR_t\) 会随之更新，同时也会新增一个可供未来选择的低位权重 \(10^{t-1}\)。
当新权重 \(10^j\) 被加入某个剩余表时，原来表中的每个子集都有两种选择：不用它，或者用它。于是每个已有剩余类 \(u\) 都会产生一个新剩余类
$$u+10^j \pmod n,$$
并且对应的真实子集和会增加 \(10^j\)。实现总是把这个新权重加入扩展代价更低的一侧，从而在不丢失任何可能总和的前提下，让两张表保持可控。
还有一个非常重要的特例：如果 \(10\mid n\)，那么 \(n\) 的任意倍数都必须以 \(0\) 结尾。因此第二种数字只能是 \(0\)。在上面的表示式里，这恰好意味着 \(g=-f\)，其余偏移都可以直接跳过。
对 \(n=12\)，取 \(t=2\)、\(f=1\)、\(g=1\)。此时 \(R_2=11\)，若选 \(S=\{0\}\)，就得到
$$N=1\cdot 11+1\cdot 1=12.$$
从同余角度看，
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
所以 \(s(S)=1\) 立刻成立。
对 \(n=103\)，则需要负偏移。取 \(t=3\)、\(f=5\)、\(g=-4\)、\(S=\{1\}\)，可得
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
而 \(515=5\cdot 103\)。这个例子说明搜索必须同时支持 \(g\gt 0\) 和 \(g\lt 0\) 两种情况。
真正执行数论搜索的是 C++ 实现。它会对每个允许的数字偏移 \(g\in\{-9,\ldots,-1,1,\ldots,9\}\) 预先计算 gcd 约化信息以及在模 \(n/d\) 下求解同余所需的模逆。这样一来，不可能的数字对会被很快排除，而每个可能的数字对都会被化成少量目标剩余类。
实现维护两张剩余表。每张表都从空子集开始。当一个新的低位权重 \(10^j\) 出现时，被选中的那张表会把所有可达剩余类更新一遍：一种情况是不选 \(10^j\)，另一种情况是选 \(10^j\)。对模 \(n\) 的每个剩余类，表中只保留能达到它的最小真实子集和与最大真实子集和。
对当前长度 \(t\) 和首位数字 \(f\)，实现先检查纯重复数 \(fR_t\)。若仍不满足，再遍历所有合法的第二种数字。对每个可行目标剩余类 \(w\)，它会把两张表连接起来：如果第一张表里有剩余类 \(x\)，第二张表里有剩余类 \(w-x\)，那么两半就能拼成正确的总剩余类。再根据保存的极值，就能重建出该偏移符号下的最小候选数。
找到 \(d(n)\) 之后，C++ 实现把它累加到总和中。对于较大的 \(k\)，区间 \(1,\ldots,k\) 会被切成若干块交给多个线程并行处理，最后再把部分和精确相加。Python 与 Java 实现并不重新实现这套数论逻辑，而是调用同一个已编译核心并解析其输出。
对固定的 \(n\)，每张剩余表最多只有 \(n\) 个剩余类。因此加入一个新的十进制权重在最坏情况下需要 \(O(n)\) 时间，因为每个已可达剩余类都可能生成一个平移后的新状态。表的连接步骤同样是按剩余类工作，而不是按全部子集工作。
若 \(n\) 的最小 duodigit 倍数长度为 \(t_n\)，则求解该 \(n\) 的代价在量级上是 \(O(t_n n)\)，只带有来自有限偏移集合的小常数因子。这比朴素枚举低位 \(2^{t_n-1}\) 个子集要高效得多。
对外层求和，总工作量可以写成
$$\sum_{n=1}^{k} O(t_n n),$$
而实现能够把这部分工作分摊到多个 CPU 核心上，因为 \(d(1),d(2),\ldots,d(k)\) 彼此独立。
Для каждого положительного целого \(n\) обозначим через \(d(n)\) наименьшее положительное кратное \(n\), в десятичной записи которого встречается не более двух различных цифр; такое число называют duodigit. Требуется вычислить
$$D(k)=\sum_{n=1}^{k} d(n).$$
Прямой перебор кратных \(n\) здесь непрактичен, потому что первое подходящее кратное может быть намного больше \(n\) и иметь много цифр. Поэтому реализация переписывает ограничение на цифры как модульную задачу о суммах подмножеств и ведет поиск по возрастанию длины десятичной записи.
Главная идея состоит в том, чтобы задавать любой duodigit фиксированной длины одной и той же алгебраической формулой. Тогда условие делимости превращается в сравнение по модулю, и вместо полного перебора десятичных строк достаточно работать с классами вычетов.
Зафиксируем длину \(t\ge 1\) и ведущую цифру \(f\in\{1,\ldots,9\}\). Пусть вторая цифра равна \(f+g\), где
$$-f \le g \le 9-f,\qquad g\ne 0.$$
Число, состоящее только из цифры \(f\), имеет вид
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
Если \(S\subseteq \{0,1,\ldots,t-2\}\) — множество неведущих позиций, где цифра \(f\) заменяется на \(f+g\), то кандидат записывается так:
$$N=fR_t+g\sum_{j\in S}10^j.$$
Старшая позиция не входит в \(S\), поэтому первая цифра всегда остается равной \(f\). Частный случай с одной повторяющейся цифрой соответствует \(S=\varnothing\), то есть \(N=fR_t\).
Положим
$$s(S)=\sum_{j\in S}10^j.$$
Тогда условие \(n\mid N\) равносильно
$$g\,s(S)\equiv -fR_t \pmod n.$$
Обозначим
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
Решение существует тогда и только тогда, когда \(d\mid r\). Если это выполнено, делим сравнение на \(d\) и получаем
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
Так как \(\gcd(g/d,n/d)=1\), существует обратный элемент \((g/d)^{-1}\) по модулю \(n/d\). Следовательно, все допустимые вычеты описываются формулой
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
Если снова смотреть по модулю \(n\), допустимыми будут вычеты
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
Итак, арифметическая проверка для пары цифр \(\{f,f+g\}\) сводится к короткому списку целевых классов вычетов.
Для длины \(t\) изменяемые разрядные веса равны \(1,10,\ldots,10^{t-2}\). Реализация распределяет эти степени десяти между двумя группами, обозначим их \(X\) и \(Y\), а выбранное множество записывает как \(S=A\cup B\), где \(A\subseteq X\) и \(B\subseteq Y\).
Для каждой половины важны две величины:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
и аналогично для \(B\). Тогда
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
Это и есть схема meet-in-the-middle: если нужен суммарный вычет \(w\), достаточно найти вычеты \(x\) и \(y\), удовлетворяющие
$$x+y\equiv w\pmod n.$$
При фиксированных \(t\), \(f\) и \(g\) базовый член \(fR_t\) постоянен. Поэтому минимизация числа \(N\) равносильна оптимизации \(s(S)\) в выражении
$$N=fR_t+g\,s(S).$$
Если \(g\gt 0\), меньшее значение \(s(S)\) дает меньшее число, значит для каждого вычета нужен только минимум \(\sigma\). Если \(g\lt 0\), меньшее число получается при большем \(s(S)\), значит нужен только максимум.
Именно поэтому для каждого класса вычетов хранятся лишь два экстремума: наименьшая и наибольшая достижимые реальные суммы подмножеств. Полный список подмножеств не нужен.
Поиск идет по длинам \(t=1,2,3,\ldots\). На каждом шаге обновляется повторяющаяся основа \(fR_t\), и становится доступен еще один младший вес \(10^{t-1}\), который можно включать в будущие подмножества.
Когда новый вес \(10^j\) добавляется в одну из таблиц вычетов, каждое уже существующее подмножество либо не берет этот вес, либо берет его. Поэтому из каждого сохраненного вычета \(u\) возникает сдвинутый вычет
$$u+10^j \pmod n,$$
а соответствующая реальная сумма подмножества увеличивается на \(10^j\). Реализация добавляет новый вес в ту таблицу, расширение которой дешевле, сохраняя обе таблицы управляемыми по размеру и не теряя ни одной возможной суммы.
Есть и важный частный случай: если \(10\mid n\), то любое кратное \(n\) должно оканчиваться на \(0\). Значит, второй цифрой обязана быть \(0\). В нашей записи это означает \(g=-f\), и все остальные смещения можно сразу отбросить.
Для \(n=12\) возьмем \(t=2\), \(f=1\), \(g=1\). Тогда \(R_2=11\), а при \(S=\{0\}\) получаем
$$N=1\cdot 11+1\cdot 1=12.$$
В форме сравнения это
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
так что \(s(S)=1\) подходит сразу.
Для \(n=103\) нужен отрицательный сдвиг. Если взять \(t=3\), \(f=5\), \(g=-4\) и \(S=\{1\}\), то
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
и действительно \(515=5\cdot 103\). Этот пример показывает, почему поиск обязан учитывать как \(g\gt 0\), так и \(g\lt 0\).
Фактический числовой поиск выполняет реализация на C++. Для каждого допустимого смещения цифр \(g\in\{-9,\ldots,-1,1,\ldots,9\}\) она заранее вычисляет данные для сокращения по gcd и модульный обратный элемент, необходимый для решения сравнения по модулю \(n/d\). Благодаря этому невозможные пары цифр отбрасываются быстро, а каждая возможная пара превращается в короткий список целевых вычетов.
Поддерживаются две таблицы вычетов. Обе начинаются с пустого подмножества. Когда появляется новый младший вес \(10^j\), выбранная таблица обновляет все достижимые вычеты, рассматривая обе возможности: не брать \(10^j\) или взять \(10^j\). Для каждого класса вычетов по модулю \(n\) таблица хранит только наименьшую и наибольшую реальные суммы подмножеств, которые этот вычет дают.
Для текущей длины \(t\) и ведущей цифры \(f\) реализация сначала проверяет число \(fR_t\) с одной повторяющейся цифрой. Если этого недостаточно, перебираются все допустимые вторые цифры. Для каждого подходящего целевого вычета \(w\) две таблицы объединяются так: если в первой есть вычет \(x\), а во второй есть вычет \(w-x\), то вместе они дают нужный суммарный вычет. По сохраненным экстремумам восстанавливается наименьший числовой кандидат для данного знака \(g\).
После нахождения \(d(n)\) реализация на C++ прибавляет его к общей сумме. Для больших \(k\) диапазон \(1,\ldots,k\) делится на блоки и обрабатывается параллельно несколькими потоками, а затем частичные суммы складываются точно. Реализации на Python и Java не переписывают эту теорию чисел, а вызывают то же скомпилированное ядро и разбирают его вывод.
Для фиксированного \(n\) каждая таблица вычетов содержит не более \(n\) классов. Поэтому добавление новой степени десяти в худшем случае требует \(O(n)\) времени, так как каждый достижимый вычет может породить одно сдвинутое состояние. Шаг объединения тоже работает с классами вычетов, а не со всеми подмножествами.
Если минимальное duodigit-кратное числа \(n\) имеет длину \(t_n\), то стоимость поиска для этого \(n\) имеет масштаб \(O(t_n n)\) с точностью до небольших постоянных факторов, связанных с конечным набором допустимых смещений. Это намного лучше наивного перебора всех \(2^{t_n-1}\) подмножеств младших позиций.
Для внешней суммы общий объем работы равен
$$\sum_{n=1}^{k} O(t_n n),$$
и реализация распараллеливает его по ядрам CPU, поскольку значения \(d(1),d(2),\ldots,d(k)\) независимы друг от друга.
لكل عدد صحيح موجب \(n\)، نعرّف \(d(n)\) بأنه أصغر مضاعف موجب لـ \(n\) تكون كتابته العشرية محتوية على رقمين مختلفين على الأكثر؛ ويسمى هذا النوع من الأعداد duodigit. المطلوب هو حساب
$$D(k)=\sum_{n=1}^{k} d(n).$$
البحث المباشر بين مضاعفات \(n\) غير عملي، لأن أول مضاعف صالح قد يكون أكبر بكثير من \(n\) وقد يمتلك عددا كبيرا من الخانات. لذلك تحوّل الشيفرة شرط الأرقام إلى مسألة مجموعات جزئية تحت الحسابيات المعيارية، ثم تبحث حسب طول العدد العشري تصاعديا.
الفكرة الأساسية هي تمثيل كل duodigit ذي طول ثابت بصيغة جبرية موحدة. عندها يتحول شرط القسمة إلى توافقية وحيدة، ويصبح البحث قائما على فئات البواقي بدلا من تعداد جميع السلاسل العشرية الممكنة.
نثبت طولا عشريا \(t\ge 1\) ورقما أولا \(f\in\{1,\ldots,9\}\). وليكن الرقم الثاني هو \(f+g\)، حيث
$$-f \le g \le 9-f,\qquad g\ne 0.$$
العدد الأساسي المؤلف من تكرار الرقم \(f\) هو
$$R_t=1+10+\cdots+10^{t-1}=\frac{10^t-1}{9},\qquad fR_t=ff\ldots f.$$
إذا كانت \(S\subseteq \{0,1,\ldots,t-2\}\) هي مجموعة المواضع غير الأولى التي نستبدل فيها \(f\) بالرقم \(f+g\)، فإن العدد المرشح يكتب بالشكل
$$N=fR_t+g\sum_{j\in S}10^j.$$
الموضع الأول غير موجود داخل \(S\)، ولذلك تبقى الخانة الأولى مساوية دائما لـ \(f\). أما الحالة الخاصة التي تستعمل رقما واحدا فقط فتقابل \(S=\varnothing\)، وعندها يكون \(N=fR_t\).
لنعرّف
$$s(S)=\sum_{j\in S}10^j.$$
عندئذ يكون الشرط \(n\mid N\) مكافئا لـ
$$g\,s(S)\equiv -fR_t \pmod n.$$
ونكتب
$$r\equiv -fR_t \pmod n,\qquad d=\gcd(g,n).$$
لا يوجد حل إلا إذا تحقق \(d\mid r\). وإذا تحقق ذلك قسمنا على \(d\) فتصير المعادلة
$$\frac{g}{d}\,s(S)\equiv \frac{r}{d}\pmod{n/d}.$$
وبما أن \(\gcd(g/d,n/d)=1\)، فإن المعكوس \((g/d)^{-1}\) موجود modulo \(n/d\). لذلك توصف جميع البواقي المسموح بها بالعلاقة
$$s(S)\equiv w_0 \pmod{n/d},\qquad w_0\equiv \frac{r}{d}\left(\frac{g}{d}\right)^{-1}\pmod{n/d}.$$
وإذا نظرنا إليها modulo \(n\)، فإن البواقي المقبولة هي
$$w_0,\ w_0+\frac{n}{d},\ w_0+2\frac{n}{d},\ \ldots,\ w_0+(d-1)\frac{n}{d}.$$
وهكذا ينكمش الاختبار الحسابي لزوج الأرقام \(\{f,f+g\}\) إلى قائمة قصيرة من فئات البواقي المستهدفة.
عند الطول \(t\)، تكون أوزان الخانات القابلة للتغيير هي \(1,10,\ldots,10^{t-2}\). تقوم الشيفرة بتوزيع هذه القوى العشرية على مجموعتين نسميهما \(X\) و\(Y\)، ثم تكتب المجموعة المختارة على صورة \(S=A\cup B\) حيث \(A\subseteq X\) و\(B\subseteq Y\).
في كل نصف نهتم بكمّيتين:
$$\rho(A)\equiv \sum_{j\in A}10^j \pmod n,\qquad \sigma(A)=\sum_{j\in A}10^j,$$
وبالمثل بالنسبة إلى \(B\). عندها نحصل على
$$s(S)=\sigma(A)+\sigma(B),\qquad s(S)\equiv \rho(A)+\rho(B)\pmod n.$$
هذه هي بنية meet-in-the-middle: فإذا أردنا الباقي الكلي \(w\)، يكفي أن نجد بواقي \(x\) و\(y\) تحققان
$$x+y\equiv w\pmod n.$$
عندما تكون \(t\) و\(f\) و\(g\) ثابتة، يكون الحد الأساسي \(fR_t\) ثابتا أيضا. لذلك فإن تصغير \(N\) يكافئ تحسين \(s(S)\) في الصيغة
$$N=fR_t+g\,s(S).$$
إذا كان \(g\gt 0\)، فإن تصغير \(s(S)\) يؤدي إلى تصغير \(N\)، ولذلك نحتاج فقط إلى أصغر قيمة ممكنة لـ \(\sigma\) في كل فئة باق. وإذا كان \(g\lt 0\)، فإن تكبير \(s(S)\) يؤدي إلى تصغير \(N\)، ولذلك نحتاج فقط إلى أكبر قيمة ممكنة.
لهذا السبب تحتفظ كل فئة باق بقيمتين فقط: أصغر مجموع حقيقي لمجموعة جزئية يحقق ذلك الباقي، وأكبر مجموع حقيقي يحققه. أما تخزين جميع المجموعات الجزئية فليس ضروريا.
يسير البحث عبر الأطوال \(t=1,2,3,\ldots\). وفي كل طول جديد يتم تحديث العدد الأساسي \(fR_t\)، كما يصبح الوزن السفلي الجديد \(10^{t-1}\) متاحا للاستخدام في الاختيارات اللاحقة.
عندما يضاف الوزن \(10^j\) إلى أحد جدولي البواقي، فإن كل مجموعة جزئية موجودة سابقا تملك احتمالين: إما أن تستبعد هذا الوزن أو أن تضيفه. ومن ثم يولد كل باق محفوظ \(u\) باقا مزاحا هو
$$u+10^j \pmod n,$$
بينما يزداد المجموع الحقيقي الموافق بمقدار \(10^j\). وتقوم الشيفرة بإضافة الوزن الجديد إلى الجانب الأقل كلفة في التوسيع، لكي يبقى الجدولان عمليين من دون فقدان أي مجموع ممكن.
وهناك حالة خاصة مهمة: إذا كان \(10\mid n\)، فإن كل مضاعف لـ \(n\) يجب أن ينتهي بالرقم \(0\). لذلك لا بد أن يكون الرقم الثاني هو \(0\)، وهذا يعني في الصيغة السابقة أن \(g=-f\)، ويمكن حينها تجاهل جميع الإزاحات الأخرى.
بالنسبة إلى \(n=12\)، نأخذ \(t=2\) و\(f=1\) و\(g=1\). عندئذ \(R_2=11\)، وإذا اخترنا \(S=\{0\}\) نحصل على
$$N=1\cdot 11+1\cdot 1=12.$$
وبصيغة التوافقية،
$$1\cdot s(S)\equiv -11\equiv 1\pmod{12},$$
ومن ثم تعمل القيمة \(s(S)=1\) مباشرة.
أما بالنسبة إلى \(n=103\)، فنحتاج إلى إزاحة سالبة. إذا أخذنا \(t=3\) و\(f=5\) و\(g=-4\) و\(S=\{1\}\)، فإن
$$N=5\cdot 111-4\cdot 10=555-40=515,$$
وفعلا \(515=5\cdot 103\). وهذا المثال يوضح لماذا يجب أن يدعم البحث كلا الحالين \(g\gt 0\) و\(g\lt 0\).
التنفيذ العددي الفعلي يوجد في تطبيق C++. فهو يحسب مسبقا، لكل إزاحة رقمية مسموحة \(g\in\{-9,\ldots,-1,1,\ldots,9\}\)، بيانات الاختزال عبر القاسم المشترك الأكبر وكذلك المعكوس المعياري اللازم لحل التوافقية modulo \(n/d\). وبهذا يمكن استبعاد أزواج الأرقام المستحيلة بسرعة وتحويل كل زوج ممكن إلى عدد صغير من البواقي المستهدفة.
تُحافَظ على جدولين للبواقي. يبدأ كل جدول بالمجموعة الجزئية الفارغة. وعندما يدخل وزن سفلي جديد \(10^j\)، يحدّث الجدول المختار جميع البواقي القابلة للوصول عبر احتمالين: عدم استعمال \(10^j\) أو استعماله. ولكل فئة باق modulo \(n\)، يحتفظ فقط بأصغر مجموع حقيقي للمجموعة الجزئية وأكبر مجموع حقيقي يحققان ذلك الباقي.
بالنسبة إلى الطول الحالي \(t\) والرقم الأول \(f\)، تختبر الشيفرة أولا العدد المكرر \(fR_t\). وإذا لم ينجح ذلك، فإنها تمر على جميع الأرقام الثانية المسموح بها. ولكل باق هدف \(w\)، تصل الجدولين معا بفحص ما إذا كان هناك باق \(x\) في الجدول الأول يقابله الباقي \(w-x\) في الجدول الثاني. ومن القيم الحدية المخزنة تعيد بناء أصغر مرشح عددي متوافق مع إشارة \(g\).
بعد العثور على \(d(n)\)، تضيفه نسخة C++ إلى المجموع الكلي. وعند القيم الكبيرة لـ \(k\)، يُقسَّم المجال \(1,\ldots,k\) إلى كتل وتتم معالجته على التوازي بواسطة عدة خيوط، ثم تُجمع المجاميع الجزئية بدقة كاملة. أما نسختا Python وJava فلا تعيدان تنفيذ البرهان العددي، بل تستدعيان النواة المترجمة نفسها وتقرآن الناتج النهائي.
لكل \(n\) ثابت، لا يحتوي كل جدول بواقي على أكثر من \(n\) فئة باق. لذلك فإن إضافة قوة عشرية جديدة تكلف في أسوأ الأحوال زمنا من رتبة \(O(n)\)، لأن كل باق قابل للوصول قد يولد حالة مزاحة واحدة. وخطوة الدمج أيضا تعمل على فئات البواقي لا على جميع المجموعات الجزئية.
إذا كان طول أصغر مضاعف duodigit للعدد \(n\) هو \(t_n\)، فإن كلفة البحث الخاصة بهذا \(n\) تكون من رتبة \(O(t_n n)\) مع عوامل ثابتة صغيرة فقط ناتجة عن المجموعة المحدودة من الإزاحات الممكنة. وهذا أفضل بكثير من الفحص الساذج لجميع المجموعات الجزئية وعددها \(2^{t_n-1}\) في الخانات السفلية.
أما في الجمع الخارجي فالحجم الكلي للعمل هو
$$\sum_{n=1}^{k} O(t_n n),$$
وتستغل الشيفرة التوازي بين الأنوية لأن القيم \(d(1),d(2),\ldots,d(k)\) مستقلة بعضها عن بعض.