Let \(f(10^K)\) denote the number of pairs \((p,q)\) with \(1 \le p \lt q \lt 10^K\) such that the decimal representations of \(p\) and \(q\) share at least one digit. For Problem 612 we need
$$f(10^{18}) \bmod 1000267129.$$
A direct scan is impossible: there are \(10^{18}-1\) candidate numbers and about \(\binom{10^{18}-1}{2}\) pairs. The workable idea is to forget the exact values and remember only which decimal digits occur in each number.
The solution counts numbers by their exact digit sets, then subtracts the pairs whose digit sets are disjoint.
For a positive integer \(n\), let \(S(n)\subseteq\{0,1,\dots,9\}\) be the set of digits appearing in its usual decimal expansion. Two numbers are friends exactly when
$$S(p)\cap S(q)\neq \varnothing.$$
For each mask \(A\subseteq\{0,1,\dots,9\}\), define \(C_K(A)\) as the number of integers \(n\) with \(1\le n\lt 10^K\) and \(S(n)=A\).
Once all values \(C_K(A)\) are known, the original problem becomes a counting problem over only \(2^{10}=1024\) masks.
Let \(D_\ell(A)\) be the number of \(\ell\)-digit positive integers whose digit set is exactly \(A\). Because a decimal representation cannot start with zero, the base layer is
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$$
and all other one-digit states are zero.
If an \(\ell\)-digit number currently uses digit set \(A\), then appending a digit \(x\in\{0,\dots,9\}\) produces an \((\ell+1)\)-digit number with digit set \(A\cup\{x\}\). So the transition is simply
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
Summing over all permitted lengths gives
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
This matches the range \(1\le n\lt 10^K\): every such number has between \(1\) and \(K\) digits, and leading zeros are never introduced.
Let
$$M=10^K-1.$$
Then the total number of unordered pairs is
$$\binom{M}{2}.$$
A pair is not friendly precisely when the two digit sets are disjoint. If \(N_K\) denotes the number of unordered pairs with
$$A\cap B=\varnothing,$$
then the desired answer is
$$f(10^K)=\binom{M}{2}-N_K.$$
So the task is reduced to counting disjoint mask pairs.
For every mask \(T\subseteq\{0,\dots,9\}\), define
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
Now fix a mask \(A\). A second number is disjoint from it exactly when its mask \(B\) is contained in the complement
$$\overline{A}=\{0,1,\dots,9\}\setminus A.$$
Therefore the number of choices for the second number is \(Z_K(\overline{A})\), and the number of ordered disjoint pairs is
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$$
The empty mask never occurs for a positive integer, so a disjoint pair can never be a self-pair. Hence every unordered disjoint pair appears exactly twice in the ordered count, which gives
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
The values \(Z_K(T)\) are computed by the standard subset-zeta transform in \(O(10\cdot 2^{10})\) time.
Now the numbers run from \(1\) to \(99\), so \(M=99\) and
$$\binom{99}{2}=4851.$$
The exact mask counts are easy to list:
\(\{d\}\) with \(d\in\{1,\dots,9\}\): two numbers, namely \(d\) and \(dd\).
\(\{0,d\}\): one number, namely \(d0\).
\(\{a,b\}\) with \(1\le a\lt b\le 9\): two numbers, namely \(ab\) and \(ba\).
There are no other masks below \(100\).
Now count disjoint unordered pairs by type:
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
Therefore
$$N_2=144+144+1008+504+1512=3312,$$
and the number of friend pairs is
$$f(10^2)=4851-3312=1539,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations keep small arrays indexed by the 1024 digit masks. One array stores the current length layer, another stores cumulative counts over all lengths up to \(K\). The process starts from the nine one-digit states, repeatedly appends each decimal digit \(0\) through \(9\), and adds every finished layer into the totals.
Next, the implementation copies the exact-mask counts into another 1024-entry array and performs ten subset-zeta passes, one pass per digit. After that transform, each mask stores the sum of all counts over its submasks, so the number of masks disjoint from a given mask can be read directly from its complement.
Finally, the implementation accumulates all ordered disjoint pairs, multiplies by the modular inverse of \(2\) to obtain unordered disjoint pairs, computes \(\binom{10^K-1}{2}\) modulo \(1000267129\), and subtracts. For the actual Project Euler input it sets \(K=18\).
The length DP uses \(K\) layers, \(2^{10}\) masks, and \(10\) appended digits, so it costs \(O(K\cdot 10 \cdot 2^{10})\) time. The subset-zeta transform costs \(O(10\cdot 2^{10})\) time. Memory usage is \(O(2^{10})\), because only a few arrays of length \(1024\) are stored.
With decimal digits fixed, the whole method is tiny. For \(K=18\), the runtime is effectively constant relative to the enormous size of the original search space.
Sei \(f(10^K)\) die Anzahl der Paare \((p,q)\) mit \(1 \le p \lt q \lt 10^K\), deren Dezimaldarstellungen mindestens eine gemeinsame Ziffer besitzen. Für Problem 612 wird gesucht:
$$f(10^{18}) \bmod 1000267129.$$
Direktes Durchsuchen ist aussichtslos: Es gibt \(10^{18}-1\) Kandidaten und ungefähr \(\binom{10^{18}-1}{2}\) Paare. Deshalb speichert die Lösung nicht die exakten Werte, sondern nur die Menge der vorkommenden Dezimalziffern.
Die Lösung zählt zunächst Zahlen nach ihrer exakten Ziffernmenge und zieht dann diejenigen Paare ab, deren Ziffernmengen disjunkt sind.
Für eine positive ganze Zahl \(n\) sei \(S(n)\subseteq\{0,1,\dots,9\}\) die Menge der Ziffern, die in ihrer üblichen Dezimaldarstellung vorkommen. Zwei Zahlen sind genau dann Freunde, wenn
$$S(p)\cap S(q)\neq \varnothing.$$
Für jede Maske \(A\subseteq\{0,1,\dots,9\}\) definieren wir \(C_K(A)\) als die Anzahl der Zahlen \(n\) mit \(1\le n\lt 10^K\) und \(S(n)=A\).
Sobald alle Werte \(C_K(A)\) bekannt sind, ist das ursprüngliche Problem auf nur \(2^{10}=1024\) Masken reduziert.
Sei \(D_\ell(A)\) die Anzahl der positiven \(\ell\)-stelligen Zahlen, deren Ziffernmenge genau \(A\) ist. Weil eine Dezimaldarstellung nicht mit Null beginnen darf, lautet die Basis
$$D_1(\{d\})=1 \quad \text{für } d\in\{1,\dots,9\},$$
während alle übrigen Zustände der Länge \(1\) gleich null sind.
Wenn eine \(\ell\)-stellige Zahl aktuell die Ziffernmenge \(A\) besitzt, dann erzeugt das Anhängen einer Ziffer \(x\in\{0,\dots,9\}\) eine \((\ell+1)\)-stellige Zahl mit Ziffernmenge \(A\cup\{x\}\). Der Übergang ist also
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
Über alle zulässigen Längen aufsummiert erhält man
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
Das passt exakt zum Bereich \(1\le n\lt 10^K\): Jede solche Zahl hat zwischen \(1\) und \(K\) Stellen, und führende Nullen werden nie eingeführt.
Setze
$$M=10^K-1.$$
Dann ist die Gesamtzahl ungeordneter Paare
$$\binom{M}{2}.$$
Ein Paar ist genau dann kein Freundespaar, wenn die beiden Ziffernmengen disjunkt sind. Bezeichnet \(N_K\) die Anzahl ungeordneter Paare mit
$$A\cap B=\varnothing,$$
dann ist die gesuchte Größe
$$f(10^K)=\binom{M}{2}-N_K.$$
Damit bleibt nur noch die Zählung disjunkter Maskenpaare.
Für jede Maske \(T\subseteq\{0,\dots,9\}\) definieren wir
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
Fixiere nun eine Maske \(A\). Eine zweite Zahl ist genau dann disjunkt dazu, wenn ihre Maske \(B\) in der Komplementmenge
$$\overline{A}=\{0,1,\dots,9\}\setminus A$$
enthalten ist. Also gibt es \(Z_K(\overline{A})\) Möglichkeiten für die zweite Zahl, und damit
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A})$$
geordnete disjunkte Paare.
Die leere Maske kommt bei positiven Zahlen nie vor, daher kann ein disjunktes Paar niemals ein Selbstpaar sein. Jedes ungeordnete disjunkte Paar wird also genau zweimal gezählt, woraus folgt
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
Die Werte \(Z_K(T)\) entstehen über die Standard-Zeta-Transformation auf Teilmengen in \(O(10\cdot 2^{10})\) Zeit.
Hier laufen die Zahlen von \(1\) bis \(99\), also ist \(M=99\) und
$$\binom{99}{2}=4851.$$
Die exakten Maskenzahlen lassen sich vollständig auflisten:
\(\{d\}\) mit \(d\in\{1,\dots,9\}\): zwei Zahlen, nämlich \(d\) und \(dd\).
\(\{0,d\}\): eine Zahl, nämlich \(d0\).
\(\{a,b\}\) mit \(1\le a\lt b\le 9\): zwei Zahlen, nämlich \(ab\) und \(ba\).
Weitere Masken treten unter \(100\) nicht auf.
Nun zählen wir die ungeordneten disjunkten Paare nach Typ:
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
Also gilt
$$N_2=144+144+1008+504+1512=3312,$$
und damit
$$f(10^2)=4851-3312=1539,$$
genau der Kontrollwert aus der Implementierung.
Die C++, Python- und Java-Implementierungen arbeiten mit kleinen Arrays über den 1024 Ziffernmasken. Ein Array speichert die aktuelle Längenschicht, ein weiteres die kumulierten Häufigkeiten über alle Längen bis \(K\). Gestartet wird mit den neun einstelligen Zuständen; anschließend wird wiederholt jede Dezimalziffer \(0\) bis \(9\) angehängt und jede fertige Schicht in die Gesamtsummen übernommen.
Danach kopiert die Implementierung die exakten Maskenzahlen in ein zweites 1024-Feld und führt zehn Zeta-Pässe über Teilmengen aus, einen pro Ziffer. Nach dieser Transformation enthält jede Maske die Summe aller ihrer Teilmengen, sodass die Zahl disjunkter Partner direkt über die Komplementmaske abgelesen werden kann.
Zum Schluss summiert die Implementierung alle geordneten disjunkten Paare, multipliziert mit dem modularen Inversen von \(2\), um ungeordnete Paare zu erhalten, berechnet \(\binom{10^K-1}{2}\) modulo \(1000267129\) und subtrahiert. Für die eigentliche Aufgabe wird \(K=18\) gesetzt.
Die Längen-DP verwendet \(K\) Schichten, \(2^{10}\) Masken und \(10\) anzuhängende Ziffern. Das ergibt \(O(K\cdot 10 \cdot 2^{10})\) Zeit. Die Teilmengen-Zeta-Transformation benötigt \(O(10\cdot 2^{10})\) Zeit. Der Speicherbedarf ist \(O(2^{10})\), da nur wenige Arrays der Länge \(1024\) gehalten werden.
Da die Dezimalbasis fest ist, bleibt das Verfahren extrem klein. Für \(K=18\) ist die Laufzeit im Vergleich zum ursprünglichen Suchraum praktisch konstant.
\(f(10^K)\), \(1 \le p \lt q \lt 10^K\) koşulunu sağlayan ve onluk yazımlarında en az bir ortak rakam bulunan \((p,q)\) çiftlerinin sayısı olsun. Problem 612 için aranan değer
$$f(10^{18}) \bmod 1000267129$$
ifadesidir. Doğrudan tarama mümkün değildir; çünkü \(10^{18}-1\) sayı ve yaklaşık \(\binom{10^{18}-1}{2}\) çift vardır. Bu yüzden çözüm, sayıların kendisini değil, hangi rakamları içerdiğini sayar.
Yöntem önce her tam rakam kümesi için kaç sayı olduğunu bulur, sonra rakam kümeleri ayrık olan çiftleri toplam çiftlerden çıkarır.
Pozitif bir \(n\) tamsayısı için \(S(n)\subseteq\{0,1,\dots,9\}\), \(n\)'nin normal onluk yazımında görünen rakamların kümesi olsun. İki sayı tam olarak şu durumda arkadaştır:
$$S(p)\cap S(q)\neq \varnothing.$$
Her \(A\subseteq\{0,1,\dots,9\}\) maskesi için \(C_K(A)\), \(1\le n\lt 10^K\) aralığında olup rakam kümesi tam olarak \(A\) olan sayı adedini göstersin.
Tüm \(C_K(A)\) değerleri bilindiğinde sorun yalnızca \(2^{10}=1024\) maske üzerinde yapılan bir sayım problemine dönüşür.
\(D_\ell(A)\), rakam kümesi tam olarak \(A\) olan \(\ell\) basamaklı pozitif sayıların adedi olsun. Onluk yazım sıfırla başlayamayacağı için başlangıç katmanı
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\}$$
şeklindedir; diğer tüm tek basamaklı durumlar sıfırdır.
Bir \(\ell\) basamaklı sayının mevcut rakam kümesi \(A\) ise sonuna \(x\in\{0,\dots,9\}\) rakamını eklemek, rakam kümesini \(A\cup\{x\}\) yapar. Geçiş bu yüzden
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9)$$
biçimindedir. Tüm uzunlukları toplayınca
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A)$$
elde edilir. Bu, \(1\le n\lt 10^K\) aralığıyla tam uyumludur: her sayı \(1\) ile \(K\) arasında basamağa sahiptir ve hiçbir aşamada başa sıfır eklenmez.
Şimdi
$$M=10^K-1$$
olsun. Toplam sırasız çift sayısı
$$\binom{M}{2}$$
olur. Bir çift tam olarak rakam kümeleri ayrık olduğunda arkadaş değildir. Eğer \(N_K\),
$$A\cap B=\varnothing$$
koşulunu sağlayan sırasız çiftlerin sayısıysa, aradığımız değer
$$f(10^K)=\binom{M}{2}-N_K$$
şeklindedir. Dolayısıyla asıl iş ayrık maske çiftlerini saymaktır.
Her \(T\subseteq\{0,\dots,9\}\) maskesi için
$$Z_K(T)=\sum_{B\subseteq T} C_K(B)$$
tanımını yapalım. Şimdi sabit bir \(A\) maskesi alalım. İkinci sayının \(A\) ile ayrık olması için maskesinin,
$$\overline{A}=\{0,1,\dots,9\}\setminus A$$
tümleyeni içinde kalması gerekir. Bu nedenle ikinci sayı için seçenek sayısı \(Z_K(\overline{A})\) olur ve sıralı ayrık çift sayısı
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A})$$
şeklinde yazılır.
Boş maske hiçbir pozitif sayıda oluşmadığından ayrık bir çift asla kendi kendisiyle eşleşemez. Bu yüzden her sırasız ayrık çift sıralı toplamda tam iki kez sayılır:
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
\(Z_K(T)\) değerleri standart subset-zeta dönüşümü ile \(O(10\cdot 2^{10})\) zamanda hesaplanır.
Bu durumda sayılar \(1\) ile \(99\) arasındadır; yani \(M=99\) ve
$$\binom{99}{2}=4851.$$
Tam maske adetleri kolayca listelenebilir:
\(\{d\}\), \(d\in\{1,\dots,9\}\): iki sayı vardır; \(d\) ve \(dd\).
\(\{0,d\}\): tek sayı vardır; \(d0\).
\(\{a,b\}\), \(1\le a\lt b\le 9\): iki sayı vardır; \(ab\) ve \(ba\).
\(100\)'ün altında başka maske tipi yoktur.
Şimdi sırasız ayrık çiftleri tipe göre sayalım:
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
Böylece
$$N_2=144+144+1008+504+1512=3312$$
ve arkadaş çift sayısı
$$f(10^2)=4851-3312=1539$$
olur. Bu da implementasyonun kullandığı kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları, 1024 rakam maskesi üzerinde indekslenen küçük diziler kullanır. Bir dizi mevcut basamak katmanını, bir diğeri ise \(K\)'ye kadar olan tüm uzunlukların birikimli sayılarını tutar. Süreç dokuz adet tek basamaklı durumla başlar; sonra her duruma \(0\) ile \(9\) arasındaki tüm rakamlar eklenir ve tamamlanan her katman toplam sayılara eklenir.
Daha sonra implementasyon tam maske sayılarını başka bir 1024 elemanlı diziye kopyalar ve her rakam için bir kez olmak üzere on adet subset-zeta geçişi yapar. Bu dönüşümden sonra her maske, tüm altmaskelerinin toplamını taşır; böylece bir maskeye ayrık olan partner sayısı, onun tümleyeninden doğrudan okunur.
Son aşamada implementasyon tüm sıralı ayrık çiftleri toplar, sırasız çifte dönmek için \(2\)'nin modüler tersini kullanır, \(\binom{10^K-1}{2}\) değerini \(1000267129\) modunda hesaplar ve çıkarma yapar. Gerçek soru için \(K=18\) alınır.
Basamak DP'si \(K\) katman, \(2^{10}\) maske ve \(10\) eklenecek rakam kullandığı için zaman maliyeti \(O(K\cdot 10 \cdot 2^{10})\) olur. Subset-zeta dönüşümü \(O(10\cdot 2^{10})\) zamanda çalışır. Bellek kullanımı \(O(2^{10})\)'dir; çünkü yalnızca uzunluğu \(1024\) olan birkaç dizi tutulur.
Onluk taban sabit olduğundan yöntem son derece hafiftir. \(K=18\) için çalışma süresi, özgün arama uzayının büyüklüğüne kıyasla pratikte sabit sayılır.
Sea \(f(10^K)\) el número de pares \((p,q)\) con \(1 \le p \lt q \lt 10^K\) tales que las representaciones decimales de \(p\) y \(q\) comparten al menos un dígito. En el Problema 612 se pide
$$f(10^{18}) \bmod 1000267129.$$
Un barrido directo es imposible: hay \(10^{18}-1\) números candidatos y aproximadamente \(\binom{10^{18}-1}{2}\) pares. Por eso la solución deja de mirar los valores exactos y solo recuerda qué dígitos aparecen en cada número.
La idea es contar cuántos números tienen cada conjunto exacto de dígitos y, después, restar los pares cuyos conjuntos de dígitos son disjuntos.
Para un entero positivo \(n\), sea \(S(n)\subseteq\{0,1,\dots,9\}\) el conjunto de dígitos que aparecen en su representación decimal usual. Dos números son amigos exactamente cuando
$$S(p)\cap S(q)\neq \varnothing.$$
Para cada máscara \(A\subseteq\{0,1,\dots,9\}\), definimos \(C_K(A)\) como la cantidad de enteros \(n\) con \(1\le n\lt 10^K\) y \(S(n)=A\).
Cuando se conocen todos los valores \(C_K(A)\), el problema original se reduce a contar sobre solo \(2^{10}=1024\) máscaras.
Sea \(D_\ell(A)\) el número de enteros positivos de \(\ell\) cifras cuyo conjunto de dígitos es exactamente \(A\). Como una representación decimal no puede comenzar con cero, la capa base es
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$$
y todos los demás estados de una cifra valen cero.
Si un número de \(\ell\) cifras usa actualmente el conjunto \(A\), entonces al añadir un dígito \(x\in\{0,\dots,9\}\) se obtiene un número de \((\ell+1)\) cifras con conjunto \(A\cup\{x\}\). Por tanto, la transición es
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
Sumando todas las longitudes permitidas obtenemos
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
Esto coincide exactamente con el rango \(1\le n\lt 10^K\): todo entero de ese intervalo tiene entre \(1\) y \(K\) cifras y nunca se introducen ceros iniciales.
Definimos
$$M=10^K-1.$$
Entonces el número total de pares no ordenados es
$$\binom{M}{2}.$$
Un par no es amistoso exactamente cuando los conjuntos de dígitos son disjuntos. Si \(N_K\) denota el número de pares no ordenados tales que
$$A\cap B=\varnothing,$$
entonces la respuesta buscada es
$$f(10^K)=\binom{M}{2}-N_K.$$
Así, todo se reduce a contar pares de máscaras disjuntas.
Para cada máscara \(T\subseteq\{0,\dots,9\}\), definimos
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
Ahora fijemos una máscara \(A\). Un segundo número es disjunto de ella exactamente cuando su máscara \(B\) está contenida en el complemento
$$\overline{A}=\{0,1,\dots,9\}\setminus A.$$
Por tanto, el número de opciones para el segundo número es \(Z_K(\overline{A})\), y el número de pares disjuntos ordenados es
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$$
La máscara vacía nunca aparece para un entero positivo, así que un par disjunto nunca puede ser un autopar. En consecuencia, cada par disjunto no ordenado se cuenta exactamente dos veces, y
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
Los valores \(Z_K(T)\) se obtienen con la transformada zeta sobre subconjuntos en \(O(10\cdot 2^{10})\) tiempo.
Ahora los números van de \(1\) a \(99\), de modo que \(M=99\) y
$$\binom{99}{2}=4851.$$
Los conteos exactos por máscara son fáciles de enumerar:
\(\{d\}\) con \(d\in\{1,\dots,9\}\): dos números, \(d\) y \(dd\).
\(\{0,d\}\): un número, \(d0\).
\(\{a,b\}\) con \(1\le a\lt b\le 9\): dos números, \(ab\) y \(ba\).
No aparecen otras máscaras por debajo de \(100\).
Contemos ahora los pares disjuntos no ordenados por tipo:
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
Por lo tanto,
$$N_2=144+144+1008+504+1512=3312,$$
y el número de pares amigos es
$$f(10^2)=4851-3312=1539,$$
que coincide con el valor de verificación de la implementación.
Las implementaciones en C++, Python y Java mantienen arreglos pequeños indexados por las 1024 máscaras de dígitos. Un arreglo representa la capa de la longitud actual y otro acumula los conteos totales de todas las longitudes hasta \(K\). El proceso empieza con los nueve estados de una cifra, añade repetidamente cada dígito decimal \(0\) a \(9\) y suma cada capa terminada al acumulado global.
Después, la implementación copia los conteos exactos por máscara a otro arreglo de 1024 entradas y realiza diez pasadas de transformada zeta por subconjuntos, una por cada dígito. Tras esa transformación, cada máscara contiene la suma de todas sus submáscaras, de modo que el número de compañeros disjuntos de una máscara se obtiene directamente desde su complemento.
Al final, la implementación acumula todos los pares disjuntos ordenados, multiplica por el inverso modular de \(2\) para obtener pares no ordenados, calcula \(\binom{10^K-1}{2}\) módulo \(1000267129\) y resta. Para la entrada real del problema se usa \(K=18\).
La DP por longitud usa \(K\) capas, \(2^{10}\) máscaras y \(10\) dígitos posibles por transición, así que cuesta \(O(K\cdot 10 \cdot 2^{10})\) tiempo. La transformada zeta sobre subconjuntos cuesta \(O(10\cdot 2^{10})\) tiempo. La memoria es \(O(2^{10})\), porque solo se almacenan unos pocos arreglos de longitud \(1024\).
Como la base decimal es fija, el método es diminuto. Para \(K=18\), el tiempo de ejecución es prácticamente constante comparado con el tamaño astronómico del espacio de búsqueda original.
记 \(f(10^K)\) 为所有满足 \(1 \le p \lt q \lt 10^K\) 且 \(p,q\) 的十进制表示至少共享一个数字的数对 \((p,q)\) 的个数。第 612 题要求计算
$$f(10^{18}) \bmod 1000267129.$$
直接枚举完全不可行：候选整数有 \(10^{18}-1\) 个，而数对总量约为 \(\binom{10^{18}-1}{2}\)。因此解法必须丢掉“具体是哪个数”这一信息，只保留“这个数出现过哪些十进制数字”。
整体思路分成两层：先统计每一种“数字集合”对应多少个整数，再把数字集合互不相交的数对从总数中减掉。
对任意正整数 \(n\)，记 \(S(n)\subseteq\{0,1,\dots,9\}\) 为 \(n\) 的通常十进制表示中出现过的数字集合。于是两个数是 friend，当且仅当
$$S(p)\cap S(q)\neq \varnothing.$$
对每个掩码 \(A\subseteq\{0,1,\dots,9\}\)，定义 \(C_K(A)\) 为满足 \(1\le n\lt 10^K\) 且 \(S(n)=A\) 的整数个数。
这样一来，原问题不再依赖于 \(10^{18}\) 这个巨大范围里的具体数值，而只依赖于 \(2^{10}=1024\) 个掩码状态。
设 \(D_\ell(A)\) 表示“恰好是 \(\ell\) 位、且数字集合正好等于 \(A\)”的正整数个数。因为十进制表示不能以 \(0\) 开头，所以一位数的初始条件是
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$$
其余所有一位状态都为 \(0\)。
如果一个 \(\ell\) 位数当前已经使用的数字集合是 \(A\)，那么在末尾追加一个数字 \(x\in\{0,\dots,9\}\) 后，就得到一个 \((\ell+1)\) 位数，其数字集合变成 \(A\cup\{x\}\)。因此状态转移只有一条简单规则：
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
把所有长度层累计起来，就得到
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
这与区间 \(1\le n\lt 10^K\) 完全一致：每个这样的正整数都有 \(1\) 到 \(K\) 位，而且整个 DP 过程中从未引入前导零。
令
$$M=10^K-1.$$
那么所有无序数对的总数为
$$\binom{M}{2}.$$
一个数对 不是 friend，当且仅当它们的数字集合互不相交。如果记 \(N_K\) 为满足
$$A\cap B=\varnothing$$
的无序数对个数，那么目标答案就是
$$f(10^K)=\binom{M}{2}-N_K.$$
于是问题被转化成：怎样高效地统计“掩码互斥”的数对。
对每个掩码 \(T\subseteq\{0,\dots,9\}\)，定义
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
现在固定一个掩码 \(A\)。另一个数与它互不相交，当且仅当那个数的掩码 \(B\) 完全包含在补集
$$\overline{A}=\{0,1,\dots,9\}\setminus A$$
之内。因此，与 \(A\) 互斥的第二个数一共有 \(Z_K(\overline{A})\) 种可能，所有有序互斥数对总数为
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$$
由于正整数不可能对应空掩码，所以互斥数对不可能是“同一个对象与自己配对”。这意味着每个无序互斥数对都会在有序统计里恰好出现两次，于是
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
所有 \(Z_K(T)\) 可以通过标准的子集 zeta 变换在 \(O(10\cdot 2^{10})\) 时间内一次性求出。
这时考虑的整数是 \(1\) 到 \(99\)，所以 \(M=99\)，总数对为
$$\binom{99}{2}=4851.$$
精确掩码的个数可以完整写出来：
\(\{d\}\)，其中 \(d\in\{1,\dots,9\}\)：共有两个数，即 \(d\) 和 \(dd\)。
\(\{0,d\}\)：共有一个数，即 \(d0\)。
\(\{a,b\}\)，其中 \(1\le a\lt b\le 9\)：共有两个数，即 \(ab\) 和 \(ba\)。
在 \(100\) 以下不会再出现其他类型的掩码。
于是无序互斥数对按类型分解为
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
因此
$$N_2=144+144+1008+504+1512=3312,$$
所以 friend 数对总数为
$$f(10^2)=4851-3312=1539.$$
这正好与实现中使用的校验值一致。
C++、Python 和 Java 实现都只维护几个长度为 \(1024\) 的数组，数组下标就是 10 位数字掩码。第一个数组表示“当前位数层”的状态，第二个数组累计从 \(1\) 位到 \(K\) 位的总出现次数。程序先建立九个一位数初始状态，再反复给每个状态追加 \(0\) 到 \(9\) 的十进制数字，并把每一层的结果加到累计数组中。
随后，实现会把“精确掩码计数”复制到另一组 1024 项数组里，并按十个数字各做一次子集 zeta 变换。变换结束后，每个掩码位置保存的就是它所有子掩码计数之和，因此某个掩码有多少个互斥伙伴，可以直接从它的补集位置读出来。
最后，实现把所有有序互斥数对累加起来，再乘以 \(2\) 的模逆元得到无序互斥数对；与此同时计算 \(\binom{10^K-1}{2}\) 在模 \(1000267129\) 下的值，并做一次减法。正式题目中取 \(K=18\)。
按位数的 DP 共有 \(K\) 层，每层处理 \(2^{10}\) 个掩码，并对每个掩码尝试追加 \(10\) 个数字，因此时间复杂度是 \(O(K\cdot 10 \cdot 2^{10})\)。子集 zeta 变换需要 \(O(10\cdot 2^{10})\) 时间。空间复杂度为 \(O(2^{10})\)，因为只保存少量长度为 \(1024\) 的数组。
由于十进制这一维是固定的，这个算法实际上非常轻量。对 \(K=18\) 来说，相对于原始搜索空间的规模，运行时间几乎可以视为常数。
Обозначим через \(f(10^K)\) число пар \((p,q)\), для которых \(1 \le p \lt q \lt 10^K\) и десятичные записи \(p\) и \(q\) имеют хотя бы одну общую цифру. В задаче 612 требуется найти
$$f(10^{18}) \bmod 1000267129.$$
Прямой перебор невозможен: кандидатов \(10^{18}-1\), а число пар порядка \(\binom{10^{18}-1}{2}\). Поэтому решение забывает точные значения чисел и хранит только то, какие цифры встречаются в десятичной записи.
Сначала подсчитывается, сколько чисел соответствует каждой точной маске цифр, а затем из общего числа пар вычитаются пары с непересекающимися масками.
Для положительного целого \(n\) обозначим через \(S(n)\subseteq\{0,1,\dots,9\}\) множество цифр, встречающихся в обычной десятичной записи числа \(n\). Тогда два числа являются друзьями ровно тогда, когда
$$S(p)\cap S(q)\neq \varnothing.$$
Для каждой маски \(A\subseteq\{0,1,\dots,9\}\) определим \(C_K(A)\) как число целых \(n\), удовлетворяющих \(1\le n\lt 10^K\) и \(S(n)=A\).
После этого исходная задача сводится к подсчетам всего на \(2^{10}=1024\) масках.
Пусть \(D_\ell(A)\) обозначает количество \(\ell\)-значных положительных чисел, у которых множество цифр в точности равно \(A\). Так как десятичная запись не может начинаться с нуля, базовый слой имеет вид
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$$
а все остальные одноразрядные состояния равны нулю.
Если \(\ell\)-значное число использует множество цифр \(A\), то после приписывания цифры \(x\in\{0,\dots,9\}\) получится \((\ell+1)\)-значное число с множеством \(A\cup\{x\}\). Следовательно, переход выглядит так:
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
Суммируя по всем допустимым длинам, получаем
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
Это точно соответствует диапазону \(1\le n\lt 10^K\): каждое такое число имеет от \(1\) до \(K\) цифр, и ведущие нули нигде не появляются.
Положим
$$M=10^K-1.$$
Тогда общее число неупорядоченных пар равно
$$\binom{M}{2}.$$
Пара не является дружеской тогда и только тогда, когда множества цифр не пересекаются. Если \(N_K\) обозначает число неупорядоченных пар, для которых
$$A\cap B=\varnothing,$$
то ответ имеет вид
$$f(10^K)=\binom{M}{2}-N_K.$$
Значит, нужно быстро посчитать пары непересекающихся масок.
Для каждой маски \(T\subseteq\{0,\dots,9\}\) введем величину
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
Зафиксируем маску \(A\). Вторая маска \(B\) не пересекается с \(A\) тогда и только тогда, когда \(B\) содержится в дополнении
$$\overline{A}=\{0,1,\dots,9\}\setminus A.$$
Следовательно, число возможных вторых чисел равно \(Z_K(\overline{A})\), а число упорядоченных непересекающихся пар равно
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$$
Пустая маска не может соответствовать положительному числу, поэтому непересекающаяся пара никогда не является самопарой. Значит, каждая неупорядоченная непересекающаяся пара учитывается ровно дважды, и потому
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
Все значения \(Z_K(T)\) вычисляются стандартным дзета-преобразованием по подмножествам за \(O(10\cdot 2^{10})\) времени.
Теперь рассматриваются числа от \(1\) до \(99\), так что \(M=99\) и
$$\binom{99}{2}=4851.$$
Точные количества масок легко перечислить:
\(\{d\}\), где \(d\in\{1,\dots,9\}\): два числа, а именно \(d\) и \(dd\).
\(\{0,d\}\): одно число, а именно \(d0\).
\(\{a,b\}\), где \(1\le a\lt b\le 9\): два числа, а именно \(ab\) и \(ba\).
Других типов масок ниже \(100\) нет.
Тогда неупорядоченные непересекающиеся пары по типам дают
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
Отсюда
$$N_2=144+144+1008+504+1512=3312,$$
а значит
$$f(10^2)=4851-3312=1539,$$
что полностью совпадает с контрольным значением реализации.
Реализации на C++, Python и Java используют небольшие массивы, индексируемые 1024 масками цифр. Один массив хранит текущий слой по длине, другой накапливает общее количество по всем длинам до \(K\). Алгоритм стартует с девяти одноразрядных состояний, затем многократно приписывает к каждому состоянию любую десятичную цифру от \(0\) до \(9\) и добавляет готовый слой в общий счетчик.
После этого точные количества масок копируются в другой массив длины \(1024\), и выполняются десять проходов дзета-преобразования по подмножествам, по одному на каждую цифру. После преобразования в каждой позиции лежит сумма по всем подмаскам, поэтому число масок, непересекающихся с данной, можно сразу прочитать по ее дополнению.
В финале реализация суммирует все упорядоченные непересекающиеся пары, умножает на модульную обратную к \(2\), чтобы получить неупорядоченные пары, вычисляет \(\binom{10^K-1}{2}\) по модулю \(1000267129\) и вычитает. Для реального ответа берется \(K=18\).
DP по длине использует \(K\) слоев, \(2^{10}\) масок и \(10\) возможных добавляемых цифр, поэтому его временная сложность равна \(O(K\cdot 10 \cdot 2^{10})\). Дзета-преобразование по подмножествам стоит \(O(10\cdot 2^{10})\) времени. Память равна \(O(2^{10})\), потому что хранятся лишь несколько массивов длины \(1024\).
Так как десятичная база фиксирована, метод получается очень маленьким. Для \(K=18\) время работы практически постоянно по сравнению с колоссальным размером исходного пространства поиска.
لنعرّف \(f(10^K)\) بأنه عدد الأزواج \((p,q)\) التي تحقق \(1 \le p \lt q \lt 10^K\) ويشترك فيها العددان في رقم عشري واحد على الأقل. في المسألة 612 نريد حساب
$$f(10^{18}) \bmod 1000267129.$$
الفحص المباشر مستحيل عمليًا: لدينا \(10^{18}-1\) عددًا مرشحًا، وعدد الأزواج يقارب \(\binom{10^{18}-1}{2}\). لذلك تتخلى الفكرة الصحيحة عن قيمة العدد نفسها، وتحتفظ فقط بمجموعة الأرقام العشرية التي تظهر فيه.
الفكرة الأساسية هي عدّ الأعداد بحسب مجموعة الأرقام التي تستعملها بالضبط، ثم طرح الأزواج التي تكون مجموعتا أرقامها متباعدتين تمامًا.
لكل عدد صحيح موجب \(n\)، نرمز بـ \(S(n)\subseteq\{0,1,\dots,9\}\) إلى مجموعة الأرقام التي تظهر في كتابته العشرية المعتادة. عندئذ يكون العددان صديقين بالضبط عندما
$$S(p)\cap S(q)\neq \varnothing.$$
ولكل قناع \(A\subseteq\{0,1,\dots,9\}\)، نعرّف \(C_K(A)\) على أنه عدد الأعداد \(n\) التي تحقق \(1\le n\lt 10^K\) ولها مجموعة أرقام مساوية تمامًا لـ \(A\).
بمجرد معرفة جميع القيم \(C_K(A)\)، تتحول المسألة كلها إلى عدٍّ على \(2^{10}=1024\) حالة فقط.
لنعرّف \(D_\ell(A)\) بأنه عدد الأعداد الموجبة ذات \(\ell\) خانات التي تكون مجموعة أرقامها بالضبط \(A\). وبما أن الكتابة العشرية لا يمكن أن تبدأ بصفر، فإن طبقة البداية هي
$$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$$
وجميع الحالات الأخرى ذات الخانة الواحدة تساوي صفرًا.
إذا كان عدد ذو \(\ell\) خانات يستخدم حاليًا مجموعة الأرقام \(A\)، فإن إلحاق رقم \(x\in\{0,\dots,9\}\) به ينتج عددًا ذا \((\ell+1)\) خانات ومجموعة أرقام \(A\cup\{x\}\). لذا يكون الانتقال
$$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$$
وبجمع جميع الأطوال المسموح بها نحصل على
$$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$$
وهذا يطابق المجال \(1\le n\lt 10^K\) تمامًا: كل عدد في هذا المجال له بين \(1\) و\(K\) خانات، ولا تُدخَل أصفار بادئة في أي مرحلة.
لنضع
$$M=10^K-1.$$
إذن عدد الأزواج غير المرتبة الكلي هو
$$\binom{M}{2}.$$
والزوج يكون غير صديق بالضبط عندما تكون مجموعتا الأرقام متباعدتين. فإذا رمزنا بـ \(N_K\) إلى عدد الأزواج غير المرتبة التي تحقق
$$A\cap B=\varnothing,$$
فإن الجواب المطلوب هو
$$f(10^K)=\binom{M}{2}-N_K.$$
إذًا بقيت مهمة واحدة: عدّ أزواج الأقنعة المتباعدة.
لكل قناع \(T\subseteq\{0,\dots,9\}\)، نعرّف
$$Z_K(T)=\sum_{B\subseteq T} C_K(B).$$
ثبّت الآن قناعًا \(A\). يكون العدد الثاني متباعدًا عنه تمامًا إذا كان قناعه \(B\) محتوى بالكامل في المتمم
$$\overline{A}=\{0,1,\dots,9\}\setminus A.$$
إذن عدد الاختيارات للعدد الثاني هو \(Z_K(\overline{A})\)، وعدد الأزواج المرتبة المتباعدة هو
$$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$$
القناع الفارغ لا يظهر أبدًا مع عدد موجب، ولذلك لا يمكن أن يكون الزوج المتباعد زوجًا ذاتيًا. ومن ثم فإن كل زوج غير مرتب يُحسب مرتين بالضبط في العد المرتب، فنحصل على
$$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$$
وتُحسب جميع القيم \(Z_K(T)\) دفعة واحدة بتحويل zeta على المجموعات الجزئية في زمن \(O(10\cdot 2^{10})\).
الآن الأعداد هي من \(1\) إلى \(99\)، لذا \(M=99\) ويكون
$$\binom{99}{2}=4851.$$
ومن السهل كتابة أعداد كل قناع بدقة:
\(\{d\}\) حيث \(d\in\{1,\dots,9\}\): عددان، وهما \(d\) و\(dd\).
\(\{0,d\}\): عدد واحد، وهو \(d0\).
\(\{a,b\}\) حيث \(1\le a\lt b\le 9\): عددان، وهما \(ab\) و\(ba\).
ولا تظهر أي أقنعة أخرى تحت \(100\).
وعندها تتفكك الأزواج غير المرتبة المتباعدة حسب النوع إلى
$$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$$
إذًا
$$N_2=144+144+1008+504+1512=3312,$$
ومن ثم يكون عدد أزواج الأصدقاء
$$f(10^2)=4851-3312=1539,$$
وهو بالضبط نفس مقدار التحقق الذي تستخدمه التنفيذات.
تحتفظ تنفيذات C++ وPython وJava بمصفوفات صغيرة مفهرسة بالأقنعة الرقمية وعددها \(1024\). تمثل إحدى المصفوفات طبقة الطول الحالية، وتمثل أخرى المجاميع التراكمية لجميع الأطوال حتى \(K\). تبدأ العملية من الحالات التسع ذات الخانة الواحدة، ثم تُلحَق بكل حالة جميع الأرقام العشرية من \(0\) إلى \(9\)، وتُضاف كل طبقة منتهية إلى المجاميع الكلية.
بعد ذلك تنسخ التنفيذات أعداد الأقنعة الدقيقة إلى مصفوفة أخرى بطول \(1024\)، وتنفذ عشر تمريرات لتحويل zeta على المجموعات الجزئية، تمريرة لكل رقم. بعد هذا التحويل تصبح كل خانة مساوية لمجموع جميع الأقنعة الجزئية التابعة لها، ولذلك يمكن استخراج عدد الشركاء المتباعدين لأي قناع مباشرة من قناعه المتمم.
وفي النهاية تجمع التنفيذات جميع الأزواج المرتبة المتباعدة، ثم تضرب في المعكوس الضربي لـ \(2\) للحصول على الأزواج غير المرتبة، وتحسب \(\binom{10^K-1}{2}\) بترديد \(1000267129\)، ثم تطرح. وفي مسألة Project Euler الفعلية يؤخذ \(K=18\).
تستخدم DP حسب الطول \(K\) طبقات و\(2^{10}\) قناعًا و\(10\) أرقام محتملة في كل انتقال، ولذلك تكون الكلفة الزمنية \(O(K\cdot 10 \cdot 2^{10})\). أما تحويل zeta على المجموعات الجزئية فيكلف \(O(10\cdot 2^{10})\) زمنًا. واستهلاك الذاكرة هو \(O(2^{10})\)، لأن المخزن الفعلي لا يتجاوز بضع مصفوفات طول كل منها \(1024\).
وبما أن قاعدة العد العشري ثابتة، فهذه الخوارزمية صغيرة جدًا في الواقع. وعند \(K=18\) يصبح زمن التنفيذ شبه ثابت مقارنةً بحجم فضاء البحث الأصلي.