A positive integer is called a 123-number if its decimal expansion uses only the digits \(1\), \(2\), and \(3\), and every nonzero digit count is itself a 123-number. If \(c_1(n)\), \(c_2(n)\), and \(c_3(n)\) denote the numbers of \(1\)'s, \(2\)'s, and \(3\)'s in \(n\), then each positive value among those counts must again satisfy the same rule. The task is to locate the \(N\)-th such number in increasing order and report its value modulo \(123123123\).
The key observation is that a candidate number is determined by two layers of information: its total length and the triple of digit counts \((A,B,C)\). Once that triple is admissible, the number of corresponding decimal strings is a multinomial coefficient. The implementation therefore counts entire families of strings and jumps directly to the desired rank instead of enumerating all valid numbers one by one.
Let \(\mathcal{S}\) be the set of all positive integers that are valid as digit counts. We start with
$$1 \in \mathcal{S}.$$
For \(n>1\), membership means two things simultaneously:
$$n \in \mathcal{S} \iff \text{every digit of } n \text{ lies in } \{1,2,3\} \text{ and } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ or } c_i(n)\in\mathcal{S}.$$
This recursion is well founded because each count \(c_i(n)\) is at most the number of digits of \(n\), hence strictly smaller than \(n\) for every \(n>1\). So admissibility can be computed bottom-up: when testing \(n\), all smaller count values are already known.
Fix a length \(L\). Suppose the final string contains \(A\) copies of digit \(1\), \(B\) copies of digit \(2\), and \(C\) copies of digit \(3\). Then
$$A+B+C=L,$$
and the triple is admissible exactly when every nonzero member of \(\{A,B,C\}\) lies in \(\mathcal{S}\).
For one such admissible triple, the number of distinct strings is
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
Therefore the total number of valid 123-numbers of length \(L\) is
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
This reduces the fixed-length problem to a scan over admissible count triples rather than over all \(3^L\) raw strings.
Every valid number with fewer digits is numerically smaller than every valid number with more digits. Inside one fixed length, ordinary lexicographic order agrees with numeric order because there are no leading zeros.
So the search proceeds in two stages. First find the unique length \(L\) such that
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
Then define the residual rank inside that length by
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
Now the task is purely combinatorial: find the \(R\)-th admissible length-\(L\) string in lexicographic order.
Assume we have already fixed a prefix of length \(p\), and that this prefix uses \(p_1\) ones, \(p_2\) twos, and \(p_3\) threes. Let the remaining length be
$$r=L-p.$$
If the final count triple is \((A,B,C)\), then the suffix still needs
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
with \(a,b,c\ge 0\) and \(a+b+c=r\). For this particular final triple, the number of admissible completions of the current prefix is
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$
Summing over all admissible final triples gives the block size
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
Testing the next digit in the order \(1,2,3\) partitions all valid completions into consecutive lexicographic blocks. If the desired rank is larger than the first block, subtract that block and continue with the next digit; otherwise keep that digit and move to the next position.
The first admissible count values are
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
so \(4\notin\mathcal{S}\). That immediately explains the early lengths. For \(L=1,2,3\), every count triple uses only the values \(0,1,2,3\), so every ternary string is valid and
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
The cumulative total through length \(3\) is therefore
$$3+9+27=39.$$
Hence the \(40\)-th 123-number must be the first admissible string of length \(4\). The lexicographically smallest candidate is \(1111\), but its count triple is \((4,0,0)\), which is invalid because \(4\notin\mathcal{S}\). The next candidate is \(1112\), whose count triple is \((3,1,0)\); both positive counts \(3\) and \(1\) are admissible. Therefore the first valid length-\(4\) string is \(1112\), so the \(40\)-th 123-number is \(1112\).
The C++, Python, and Java implementations all follow the same structure. They first build a boolean table of admissible count values in increasing order, which resolves the recursive definition iteratively. Next they construct Pascal-triangle rows on demand, so every binomial coefficient needed for the multinomial formulas can be read in constant time afterward.
All counting is performed with saturation at \(N+1\). This is enough because the search never needs an exact block size once that block is already larger than the remaining rank. After the admissibility table and binomial table are available, the implementation sums \(F(1),F(2),\dots\) until it identifies the target length, then builds the answer one digit at a time by evaluating prefix-completion counts for tentative next digits \(1\), \(2\), and \(3\).
When the final decimal string is known, the remainder modulo \(123123123\) is evaluated left to right via
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$
This avoids ever converting the full answer into a large integer type.
Let \(M\) be the size of the admissibility table and \(L\) the length of the target number. Building the admissibility table costs \(O(M\log M)\) time because each candidate is scanned digit by digit, and it uses \(O(M)\) memory. Growing Pascal rows up to length \(L\) costs \(O(L^2)\) time and memory.
To locate the correct length, the implementation evaluates \(F(\ell)\) for \(\ell=1,2,\dots,L\). Each such evaluation scans \(O(\ell^2)\) count pairs, so the total cost is
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
The unranking stage performs at most three prefix queries per position, and each query scans admissible final triples in \(O(L^2)\), giving another \(O(L^3)\) phase. Overall the method runs in
$$O(M\log M+L^3)$$
time and uses \(O(M+L^2)\) memory for the target instance.
Eine positive ganze Zahl heißt 123-Zahl, wenn ihre Dezimaldarstellung nur die Ziffern \(1\), \(2\) und \(3\) enthält und jede nichtverschwindende Ziffernhäufigkeit selbst wieder eine 123-Zahl ist. Bezeichnet \(c_1(n)\), \(c_2(n)\) und \(c_3(n)\) die Anzahl der Ziffern \(1\), \(2\) und \(3\) in \(n\), so muss jeder positive Wert unter diesen Häufigkeiten dieselbe rekursive Bedingung erfüllen. Gesucht ist die \(N\)-te solche Zahl in aufsteigender Reihenfolge; ausgegeben wird nur ihr Rest modulo \(123123123\).
Die Grundidee besteht darin, nicht einzelne Zahlen zu erzeugen, sondern ganze Klassen von Zeichenketten zu zählen. Eine Kandidatenzahl wird vollständig durch ihre Länge und durch das Ziffernanzahl-Triplett \((A,B,C)\) beschrieben. Ist dieses Triplett zulässig, dann liefert ein Multinomialkoeffizient sofort die Anzahl aller dazugehörigen Anordnungen.
Sei \(\mathcal{S}\) die Menge aller positiven ganzen Zahlen, die als Ziffernhäufigkeiten erlaubt sind. Zunächst gilt
$$1 \in \mathcal{S}.$$
Für \(n>1\) bedeutet Zulässigkeit zwei Dinge gleichzeitig:
$$n \in \mathcal{S} \iff \text{jede Ziffer von } n \text{ liegt in } \{1,2,3\} \text{ und } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ oder } c_i(n)\in\mathcal{S}.$$
Diese Rekursion ist wohldefiniert, weil jede Häufigkeit \(c_i(n)\) höchstens so groß ist wie die Stellenzahl von \(n\) und damit für jedes \(n>1\) strikt kleiner als \(n\). Deshalb lässt sich die Menge von klein nach groß aufbauen: Beim Testen von \(n\) sind alle benötigten kleineren Werte bereits bekannt.
Fixiere eine Länge \(L\). Angenommen, die endgültige Zeichenkette enthält \(A\) Einsen, \(B\) Zweien und \(C\) Dreien. Dann gilt
$$A+B+C=L,$$
und das Triplett ist genau dann zulässig, wenn jeder nichtverschwindende Wert aus \(\{A,B,C\}\) in \(\mathcal{S}\) liegt.
Für ein festes zulässiges Triplett ist die Anzahl der verschiedenen Zeichenketten
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
Somit erhält man die Gesamtzahl der 123-Zahlen mit Länge \(L\) als
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
Damit wird die feste Länge nicht über alle \(3^L\) Rohstrings behandelt, sondern nur über die zulässigen Häufigkeitstripletts.
Jede gültige Zahl mit weniger Stellen ist numerisch kleiner als jede gültige Zahl mit mehr Stellen. Innerhalb einer festen Länge stimmt die lexikographische Ordnung mit der Zahlenordnung überein, weil keine führenden Nullen vorkommen.
Darum zerfällt die Suche in zwei Phasen. Zuerst bestimme die eindeutige Länge \(L\) mit
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
Dann ist der Rest-Rang innerhalb dieser Länge
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
Jetzt bleibt nur noch die kombinatorische Aufgabe, die \(R\)-te zulässige Zeichenkette der Länge \(L\) in lexikographischer Ordnung zu finden.
Sei ein Präfix der Länge \(p\) bereits festgelegt, und dieses Präfix verwende \(p_1\) Einsen, \(p_2\) Zweien und \(p_3\) Dreien. Die verbleibende Länge ist
$$r=L-p.$$
Falls das endgültige Triplett \((A,B,C)\) ist, benötigt das Suffix noch
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
wobei \(a,b,c\ge 0\) und \(a+b+c=r\) gelten müssen. Für dieses feste End-Tripel gibt es
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}$$
mögliche Fortsetzungen. Summiert über alle zulässigen End-Tripel erhält man die Blockgröße
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
Probiert man die nächste Ziffer in der Reihenfolge \(1,2,3\) aus, zerfallen alle gültigen Fortsetzungen in aufeinanderfolgende lexikographische Blöcke. Ist der gesuchte Rang größer als der erste Block, zieht man dessen Größe ab und testet die nächste Ziffer; andernfalls wird diese Ziffer festgeschrieben.
Die ersten zulässigen Häufigkeitswerte sind
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
also ist \(4\notin\mathcal{S}\). Das erklärt sofort die ersten Längen. Für \(L=1,2,3\) verwenden alle Häufigkeitstripletts nur die Werte \(0,1,2,3\), daher ist jede ternäre Zeichenkette gültig und
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
Die kumulative Gesamtzahl bis Länge \(3\) ist damit
$$3+9+27=39.$$
Also muss die \(40\)-te 123-Zahl die erste gültige Zeichenkette der Länge \(4\) sein. Der lexikographisch kleinste Kandidat ist \(1111\), aber sein Häufigkeitstriplett \((4,0,0)\) ist unzulässig, weil \(4\notin\mathcal{S}\). Der nächste Kandidat ist \(1112\) mit Triplett \((3,1,0)\); die positiven Häufigkeiten \(3\) und \(1\) sind beide zulässig. Folglich ist die erste gültige Zeichenkette der Länge \(4\) gleich \(1112\), und die \(40\)-te 123-Zahl ist \(1112\).
Die Implementierungen in C++, Python und Java folgen demselben Plan. Zuerst wird eine boolesche Tabelle zulässiger Häufigkeitswerte in aufsteigender Reihenfolge aufgebaut; so wird die rekursive Definition iterativ aufgelöst. Danach werden Zeilen des Pascalschen Dreiecks bei Bedarf erweitert, sodass alle für die Multinomialformeln benötigten Binomialkoeffizienten anschließend in konstanter Zeit verfügbar sind.
Alle Zählungen werden bei \(N+1\) abgesättigt. Das genügt, weil die Suche keinen exakten Blockwert mehr braucht, sobald klar ist, dass der Block bereits größer als der verbleibende Rang ist. Danach summiert die Implementierung \(F(1),F(2),\dots\), bis die Ziellänge feststeht, und konstruiert die Antwort dann Ziffer für Ziffer, indem sie für die Kandidaten \(1\), \(2\) und \(3\) jeweils die Anzahl zulässiger Präfix-Fortsetzungen berechnet.
Ist die endgültige Dezimalzeichenkette gefunden, wird der Rest modulo \(123123123\) von links nach rechts mit
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}$$
ausgewertet. Dadurch wird die komplette Zahl nie als großer Integer benötigt.
Seien \(M\) die Größe der Zulässigkeitstabelle und \(L\) die Länge der Zielzahl. Das Aufbauen der Zulässigkeitstabelle kostet \(O(M\log M)\) Zeit, weil jede Zahl ziffernweise geprüft wird, und \(O(M)\) Speicher. Das Erweitern des Pascalschen Dreiecks bis Länge \(L\) kostet \(O(L^2)\) Zeit und Speicher.
Um die richtige Länge zu finden, wertet die Implementierung \(F(\ell)\) für \(\ell=1,2,\dots,L\) aus. Jede dieser Auswertungen scannt \(O(\ell^2)\) Häufigkeitspaare, also insgesamt
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
Die Unranking-Phase führt höchstens drei Präfixabfragen pro Position aus, und jede Abfrage scannt zulässige End-Tripel in \(O(L^2)\). Damit entsteht eine weitere \(O(L^3)\)-Phase. Insgesamt läuft das Verfahren also in
$$O(M\log M+L^3)$$
Zeit und benötigt \(O(M+L^2)\) Speicher für die gegebene Zielinstanz.
Pozitif bir tam sayı, ondalık gösteriminde yalnızca \(1\), \(2\) ve \(3\) rakamlarını içeriyorsa ve sıfırdan farklı her rakam adedi yine bir 123-sayısıysa 123-sayısı olarak adlandırılır. \(c_1(n)\), \(c_2(n)\) ve \(c_3(n)\) sırasıyla \(n\) içindeki \(1\), \(2\) ve \(3\) adetleri olsun. Bu değerlerden pozitif olanların her biri aynı kurala yeniden uymalıdır. Amaç, artan sıradaki \(N\). böyle sayıyı bulmak ve sonucu \(123123123\) modunda vermektir.
Ana fikir, geçerli sayıları tek tek üretmek yerine onları uzunluklarına ve rakam sayım üçlülerine göre topluca saymaktır. Bir aday, toplam uzunluğu ve \((A,B,C)\) şeklindeki rakam adetleri ile belirlenir. Bu üçlü uygunsa, o üçlüye karşılık gelen tüm dizilişlerin sayısı bir multinom katsayısı ile bulunur.
\(\mathcal{S}\), rakam adedi olarak kullanılmasına izin verilen pozitif tamsayılar kümesi olsun. Başlangıç değeri
$$1 \in \mathcal{S}.$$
\(n>1\) için geçerlilik şu iki koşulun birlikte sağlanmasıdır:
$$n \in \mathcal{S} \iff n \text{ sayısının her basamağı } \{1,2,3\} \text{ içindedir ve } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ veya } c_i(n)\in\mathcal{S}.$$
Bu özyineleme sağlamdır; çünkü her \(c_i(n)\), \(n\)'in basamak sayısından büyük olamaz ve dolayısıyla \(n>1\) için her zaman \(n\)'den küçüktür. Bu yüzden geçerlilik küçükten büyüğe doğru hesaplanabilir: \(n\) test edilirken gereken daha küçük sayımlar zaten bilinmektedir.
Uzunluğu \(L\) olan bir dizi düşünelim. Sonuç dizisinde \(1\) rakamı \(A\) kez, \(2\) rakamı \(B\) kez, \(3\) rakamı \(C\) kez geçsin. O halde
$$A+B+C=L,$$
ve üçlü ancak \(\{A,B,C\}\) içindeki sıfır olmayan her değer \(\mathcal{S}\) içinde ise uygundur.
Sabit bir uygun üçlü için farklı diziliş sayısı
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}$$
olur. Dolayısıyla uzunluğu \(L\) olan tüm geçerli 123-sayılarının sayısı
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}$$
şeklindedir. Böylece problem, tüm \(3^L\) ham dizileri denemek yerine sadece uygun rakam-adedi üçlülerini taramaya indirgenir.
Daha kısa uzunluktaki her geçerli sayı, daha uzunluktaki her geçerli sayıdan küçüktür. Aynı uzunluk içinde de başta sıfır olmadığı için leksikografik sıra ile sayısal sıra aynıdır.
Bu nedenle arama iki aşamalıdır. Önce
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell)$$
eşitsizliğini sağlayan tek \(L\) bulunur. Sonra bu uzunluk içindeki artık sıra
$$R=N-\sum_{\ell=1}^{L-1} F(\ell)$$
olarak tanımlanır. Bundan sonra yapılacak iş, uzunluğu \(L\) olan geçerli diziler arasında leksikografik olarak \(R\). olanı bulmaktır.
Uzunluğu \(p\) olan bir önek sabitlenmiş olsun ve bu önekte \(p_1\) tane \(1\), \(p_2\) tane \(2\), \(p_3\) tane \(3\) kullanılmış olsun. Kalan uzunluk
$$r=L-p$$
olur. Son sayım üçlüsü \((A,B,C)\) ise sonek için gereken ek adetler
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3$$
şeklindedir; burada \(a,b,c\ge 0\) ve \(a+b+c=r\) olmalıdır. Bu tek son üçlü için mümkün sonek sayısı
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}$$
olur. Tüm uygun son üçlüler üzerinden toplanınca
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}$$
elde edilir. Bir sonraki basamağı \(1\), sonra \(2\), sonra \(3\) diye denemek, bütün geçerli tamamlanışları art arda gelen leksikografik bloklara ayırır. Aranan sıra ilk bloktan büyükse o bloğun büyüklüğü çıkarılır; değilse o rakam kesinleştirilir.
İlk uygun sayım değerleri
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
olduğundan \(4\notin\mathcal{S}\). Bu, ilk uzunlukları hemen açıklar. \(L=1,2,3\) için bütün sayım üçlüleri yalnızca \(0,1,2,3\) değerlerini kullandığı için tüm üçlü tabanlı diziler geçerlidir ve
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
İlk üç uzunluğun toplamı
$$3+9+27=39$$
eder. Dolayısıyla \(40\). 123-sayısı, uzunluğu \(4\) olan ilk geçerli dizi olmak zorundadır. Leksikografik olarak en küçük aday \(1111\)'dir; fakat sayım üçlüsü \((4,0,0)\) olduğundan geçersizdir. Sonraki aday \(1112\)'dir ve bunun sayım üçlüsü \((3,1,0)\) olur; pozitif sayımlar olan \(3\) ve \(1\) uygundur. Bu yüzden uzunluğu \(4\) olan ilk geçerli dizi \(1112\)'dir ve \(40\). 123-sayısı da \(1112\)'dir.
C++, Python ve Java uygulamalarının üçü de aynı planı uygular. Önce uygun rakam-adedi değerleri artan sırada işlenerek bir doğruluk tablosu oluşturulur; böylece özyinelemeli tanım iteratif biçimde çözülür. Ardından Pascal üçgeninin satırları ihtiyaç oldukça büyütülür ve multinom formüllerindeki binom katsayılarına sabit zamanda erişilir.
Tüm sayımlar \(N+1\) seviyesinde doyurularak tutulur. Bunun nedeni, bir blok kalan sıradan daha büyük olduğunda o bloğun tam büyüklüğüne artık ihtiyaç kalmamasıdır. Daha sonra uygulama \(F(1),F(2),\dots\) toplamlarını biriktirerek hedef uzunluğu bulur ve cevabı soldan sağa, olası sonraki rakamlar \(1\), \(2\), \(3\) için önek-tamamlanış sayılarını hesaplayarak kurar.
Son ondalık dizi elde edildiğinde, \(123123123\) modundaki değer soldan sağa
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}$$
bağıntısı ile hesaplanır. Böylece tam sonucu büyük bir tamsayı tipine dönüştürmeye gerek kalmaz.
\(M\), geçerlilik tablosunun boyutu; \(L\) ise hedef sayının uzunluğu olsun. Geçerlilik tablosunu kurmak, her aday sayı basamak basamak incelendiği için \(O(M\log M)\) zaman ve \(O(M)\) bellek gerektirir. Pascal satırlarını \(L\)'ye kadar büyütmek \(O(L^2)\) zaman ve bellek maliyetine sahiptir.
Doğru uzunluğu bulmak için uygulama \(\ell=1,2,\dots,L\) için \(F(\ell)\) değerlerini hesaplar. Her hesap \(O(\ell^2)\) sayım çifti taradığı için toplam maliyet
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3)$$
olur. Unranking aşaması her pozisyon için en fazla üç önek sorgusu yapar ve her sorgu \(O(L^2)\) zamanda uygun son üçlüleri tarar; bu da ikinci bir \(O(L^3)\) faz verir. Sonuç olarak yöntem
$$O(M\log M+L^3)$$
zamanda çalışır ve hedef örnek için \(O(M+L^2)\) bellek kullanır.
Un entero positivo se llama número 123 si su representación decimal usa solo los dígitos \(1\), \(2\) y \(3\), y además cada conteo no nulo de esos dígitos vuelve a ser un número 123. Si \(c_1(n)\), \(c_2(n)\) y \(c_3(n)\) son las cantidades de \(1\), \(2\) y \(3\) en \(n\), entonces cada valor positivo entre esos conteos debe satisfacer exactamente la misma regla. El objetivo es localizar el \(N\)-ésimo número de este tipo en orden creciente y devolver su valor módulo \(123123123\).
La idea central es no enumerar una por una todas las cadenas válidas, sino agruparlas por longitud y por triple de frecuencias \((A,B,C)\). Una vez fijado un triple admisible, el número de cadenas asociadas se obtiene con un coeficiente multinomial. Así, el algoritmo cuenta bloques enteros y salta directamente al rango buscado.
Sea \(\mathcal{S}\) el conjunto de enteros positivos permitidos como cantidades de dígitos. Empezamos con
$$1 \in \mathcal{S}.$$
Para \(n>1\), la condición de pertenencia es doble:
$$n \in \mathcal{S} \iff \text{cada dígito de } n \text{ pertenece a } \{1,2,3\} \text{ y } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ o } c_i(n)\in\mathcal{S}.$$
Esta recurrencia está bien fundada porque cada conteo \(c_i(n)\) es como mucho el número de cifras de \(n\), y por tanto es estrictamente menor que \(n\) cuando \(n>1\). Por eso la pertenencia se puede calcular de abajo hacia arriba: al evaluar \(n\), todos los conteos más pequeños ya han sido clasificados.
Fijemos una longitud \(L\). Supongamos que la cadena final contiene \(A\) unos, \(B\) doses y \(C\) treses. Entonces
$$A+B+C=L,$$
y el triple es admisible exactamente cuando cada elemento no nulo de \(\{A,B,C\}\) pertenece a \(\mathcal{S}\).
Para un triple admisible fijo, el número de cadenas distintas es
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
Por lo tanto, el número total de números 123 de longitud \(L\) es
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
Esto evita recorrer todas las \(3^L\) cadenas brutas y reemplaza la búsqueda por un recorrido sobre ternas de conteos admisibles.
Cualquier número válido con menos cifras es numéricamente menor que cualquier número válido con más cifras. Dentro de una longitud fija, el orden lexicográfico coincide con el orden numérico porque no hay ceros iniciales.
Por eso la búsqueda se separa en dos fases. Primero se encuentra la única longitud \(L\) tal que
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
Después se define el rango residual dentro de esa longitud como
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
Desde ese momento el problema pasa a ser: hallar la \(R\)-ésima cadena válida de longitud \(L\) en orden lexicográfico.
Supongamos que ya se fijó un prefijo de longitud \(p\), y que ese prefijo usa \(p_1\) unos, \(p_2\) doses y \(p_3\) treses. La longitud restante es
$$r=L-p.$$
Si el triple final de conteos es \((A,B,C)\), entonces al sufijo le faltan
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
con \(a,b,c\ge 0\) y \(a+b+c=r\). Para ese triple final concreto, el número de completaciones posibles es
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$
Al sumar sobre todos los triples finales admisibles se obtiene
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
Probar el siguiente dígito en el orden \(1,2,3\) divide todas las cadenas válidas restantes en bloques lexicográficos consecutivos. Si el rango buscado es mayor que el tamaño del primer bloque, se resta ese bloque y se prueba el siguiente dígito; en caso contrario, ese dígito se fija definitivamente.
Los primeros valores admisibles como conteos son
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
de modo que \(4\notin\mathcal{S}\). Eso explica inmediatamente los primeros tamaños. Para \(L=1,2,3\), cualquier terna de conteos solo usa los valores \(0,1,2,3\), así que todas las cadenas ternarias son válidas y
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
El total acumulado hasta longitud \(3\) es
$$3+9+27=39.$$
Por lo tanto, el \(40\)-ésimo número 123 debe ser la primera cadena válida de longitud \(4\). El candidato lexicográficamente más pequeño es \(1111\), pero su triple de conteos es \((4,0,0)\), que no es válido porque \(4\notin\mathcal{S}\). El siguiente candidato es \(1112\), cuyo triple es \((3,1,0)\); los conteos positivos \(3\) y \(1\) sí son válidos. En consecuencia, la primera cadena válida de longitud \(4\) es \(1112\), y el \(40\)-ésimo número 123 es \(1112\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero construyen una tabla booleana de conteos admisibles en orden creciente, lo que resuelve la definición recursiva de manera iterativa. Luego expanden filas del triángulo de Pascal cuando hacen falta, de modo que los coeficientes binomiales requeridos por las fórmulas multinomiales quedan disponibles en tiempo constante.
Todos los conteos se saturan en \(N+1\). Eso basta porque, una vez que un bloque ya supera el rango restante, el tamaño exacto del bloque deja de importar. Después de la precomputación, la implementación suma \(F(1),F(2),\dots\) hasta determinar la longitud objetivo, y a continuación construye la respuesta cifra por cifra calculando, para los candidatos \(1\), \(2\) y \(3\), cuántas completaciones válidas deja cada prefijo.
Cuando ya se conoce la cadena decimal final, el residuo módulo \(123123123\) se evalúa de izquierda a derecha con
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$
Así se evita convertir el número completo a un entero gigante.
Sea \(M\) el tamaño de la tabla de admisibilidad y \(L\) la longitud del número objetivo. Construir la tabla de admisibilidad cuesta \(O(M\log M)\) tiempo, porque cada candidato se inspecciona cifra a cifra, y usa \(O(M)\) memoria. Expandir el triángulo de Pascal hasta longitud \(L\) cuesta \(O(L^2)\) tiempo y memoria.
Para localizar la longitud correcta, la implementación evalúa \(F(\ell)\) para \(\ell=1,2,\dots,L\). Cada evaluación recorre \(O(\ell^2)\) pares de conteos, así que el coste total es
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
La fase de unranking realiza como máximo tres consultas de prefijo por posición, y cada consulta recorre ternas finales admisibles en \(O(L^2)\), lo que añade otra fase \(O(L^3)\). En conjunto, el método funciona en
$$O(M\log M+L^3)$$
tiempo y usa \(O(M+L^2)\) memoria para la instancia objetivo.
如果一个正整数的十进制表示只包含数字 \(1\)、\(2\)、\(3\)，并且这些数字中每一种的非零出现次数本身也仍然是 123 数，那么它就叫作 123 数。记 \(c_1(n)\)、\(c_2(n)\)、\(c_3(n)\) 分别为 \(n\) 中数字 \(1\)、\(2\)、\(3\) 的个数，那么这三个计数里每一个正值都必须再次满足同一条递归规则。题目要求按从小到大的顺序找到第 \(N\) 个这样的数，并输出它对 \(123123123\) 取模的结果。
核心思路不是逐个生成所有合法数字，而是按“长度”和“数字个数三元组 \((A,B,C)\)”来成批计数。只要一个三元组是合法的，与之对应的不同字符串个数就可以直接由多项式系数给出。因此，算法实际上是在数整块的候选集合，然后直接跳到目标排名，而不是进行暴力枚举。
设 \(\mathcal{S}\) 为所有可以作为数字出现次数的合法正整数集合。最基本的起点是
$$1 \in \mathcal{S}.$$
对于 \(n>1\)，属于 \(\mathcal{S}\) 需要同时满足两件事：
$$n \in \mathcal{S} \iff n \text{ 的每一位数字都属于 } \{1,2,3\} \text{，并且 } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ 或 } c_i(n)\in\mathcal{S}.$$
这个递归之所以可以自底向上计算，是因为每个计数 \(c_i(n)\) 至多等于 \(n\) 的位数，而当 \(n>1\) 时，位数一定严格小于 \(n\)。也就是说，在判断 \(n\) 是否合法时，所依赖的计数值总是更小的整数，因此它们的合法性已经提前算好。
固定一个长度 \(L\)。设最终字符串中数字 \(1\) 出现 \(A\) 次，数字 \(2\) 出现 \(B\) 次，数字 \(3\) 出现 \(C\) 次，那么有
$$A+B+C=L,$$
并且只有当 \(\{A,B,C\}\) 中所有非零项都属于 \(\mathcal{S}\) 时，这个三元组才是合法的。
对于一个固定的合法三元组，能够组成的不同字符串数量是
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
因此，长度为 \(L\) 的所有合法 123 数总数为
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
这样就把“检查全部 \(3^L\) 个原始字符串”的问题，转化成了“枚举所有合法计数三元组”的问题。
任何位数更少的合法数字，一定都小于任何位数更多的合法数字。在同一长度内部，由于不存在前导零，普通字典序与数值大小顺序完全一致。
因此搜索过程可以分成两步。首先找到唯一的长度 \(L\)，使得
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
然后定义该长度内部的剩余排名
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
从这一刻起，问题就变成了一个纯组合问题：求长度为 \(L\) 的合法字符串中，按字典序排列的第 \(R\) 个。
设当前已经固定了一个长度为 \(p\) 的前缀，并且这个前缀已经用了 \(p_1\) 个 \(1\)、\(p_2\) 个 \(2\)、\(p_3\) 个 \(3\)。剩余长度为
$$r=L-p.$$
如果最终总计数三元组是 \((A,B,C)\)，那么后缀还需要补上
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
其中要求 \(a,b,c\ge 0\)，并且 \(a+b+c=r\)。对于这个固定的最终三元组，合法补全方式数为
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$
再对所有合法的最终三元组求和，就得到此前缀对应的总块大小
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
按顺序尝试下一位为 \(1\)、\(2\)、\(3\)，就等于把所有合法后继划分成连续的字典序区块。如果目标排名比第一个区块大，就减去这个区块的大小并试下一位；否则这一位就确定下来。
最开始的一批合法计数值是
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
因此 \(4\notin\mathcal{S}\)。这一点立刻说明了前几种长度的情况。对于 \(L=1,2,3\)，所有计数三元组只会用到 \(0,1,2,3\)，所以所有只由 \(1,2,3\) 组成的字符串都合法，从而
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
长度不超过 \(3\) 的合法数字总数为
$$3+9+27=39.$$
所以第 \(40\) 个 123 数一定是长度 \(4\) 的第一个合法字符串。长度 \(4\) 中字典序最小的候选是 \(1111\)，但它的计数三元组是 \((4,0,0)\)，由于 \(4\notin\mathcal{S}\)，因此不合法。下一个候选是 \(1112\)，它的计数三元组为 \((3,1,0)\)，而 \(3\) 和 \(1\) 都是合法计数。于是长度 \(4\) 的第一个合法字符串就是 \(1112\)，也就是说第 \(40\) 个 123 数正是 \(1112\)。
C++、Python 和 Java 三个实现采用的是完全相同的流程。首先，它们按从小到大的顺序建立一个布尔表，记录哪些整数可以作为合法计数值，这样就把递归定义改写成了迭代预处理。接着，程序按需扩展 Pascal 三角形的各行，于是后续需要的二项式系数都可以常数时间读取。
所有计数都采用“饱和到 \(N+1\)”的策略。一旦某个区块已经比剩余排名大，那么知道它“足够大”就够了，不必再知道准确值。完成这些预处理后，程序依次累计 \(F(1),F(2),\dots\) 来确定目标长度，然后从左到右构造答案。每到一个位置，就分别测试下一位取 \(1\)、\(2\)、\(3\) 时能产生多少合法补全，从而决定应该进入哪一个字典序区块。
当最终十进制字符串确定后，对 \(123123123\) 的余数通过下面的递推从左到右计算：
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$
因此整个实现从头到尾都不需要把最终答案存成超大的整数类型。
设 \(M\) 为合法计数表的大小，\(L\) 为目标数字的长度。构造合法计数表需要 \(O(M\log M)\) 时间，因为每个候选值都要逐位检查；空间复杂度是 \(O(M)\)。将 Pascal 三角形扩展到长度 \(L\) 需要 \(O(L^2)\) 时间和 \(O(L^2)\) 空间。
为了找到正确的长度，程序需要计算 \(\ell=1,2,\dots,L\) 的 \(F(\ell)\)。每次计算都要扫描 \(O(\ell^2)\) 个计数对，因此总成本为
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
反排名阶段在每一位至多进行三次前缀查询，而每次查询都要在 \(O(L^2)\) 时间内扫描所有合法最终三元组，所以这一阶段也是 \(O(L^3)\)。综合起来，算法总时间复杂度为
$$O(M\log M+L^3),$$
目标实例的空间复杂度为 \(O(M+L^2)\)。
Положительное целое число называется 123-числом, если его десятичная запись состоит только из цифр \(1\), \(2\) и \(3\), а каждое ненулевое количество этих цифр само снова является 123-числом. Обозначим через \(c_1(n)\), \(c_2(n)\) и \(c_3(n)\) количества цифр \(1\), \(2\) и \(3\) в записи числа \(n\). Тогда каждый положительный элемент среди этих трёх значений обязан удовлетворять той же самой рекурсивной проверке. Нужно найти \(N\)-е такое число в возрастающем порядке и вывести его значение по модулю \(123123123\).
Главная идея состоит в том, чтобы не перечислять допустимые числа по одному, а считать их большими блоками. Любой кандидат полностью задаётся своей длиной и тройкой количеств \((A,B,C)\), где \(A\), \(B\), \(C\) — числа цифр \(1\), \(2\), \(3\). Если такая тройка допустима, то число соответствующих строк немедленно выражается через мультиномиальный коэффициент.
Пусть \(\mathcal{S}\) — множество всех положительных целых, которые разрешено использовать как количества цифр. Базовый случай таков:
$$1 \in \mathcal{S}.$$
Для \(n>1\) принадлежность описывается двумя условиями сразу:
$$n \in \mathcal{S} \iff \text{каждая цифра числа } n \text{ принадлежит } \{1,2,3\} \text{ и } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ или } c_i(n)\in\mathcal{S}.$$
Эта рекурсия корректна, потому что любое значение \(c_i(n)\) не превосходит числа цифр в \(n\), а значит для \(n>1\) строго меньше самого \(n\). Следовательно, допустимость можно вычислять снизу вверх: когда рассматривается \(n\), все меньшие счётчики уже классифицированы.
Зафиксируем длину \(L\). Пусть итоговая строка содержит \(A\) единиц, \(B\) двоек и \(C\) троек. Тогда
$$A+B+C=L,$$
а тройка \((A,B,C)\) допустима тогда и только тогда, когда каждый ненулевой элемент множества \(\{A,B,C\}\) лежит в \(\mathcal{S}\).
Для одной фиксированной допустимой тройки число разных строк равно
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
Значит, общее число 123-чисел длины \(L\) равно
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
Тем самым задача для фиксированной длины сводится не к перебору всех \(3^L\) строк, а к перебору допустимых троек количеств.
Любое допустимое число с меньшим количеством цифр численно меньше любого допустимого числа с большим количеством цифр. Внутри одной фиксированной длины лексикографический порядок совпадает с числовым, потому что ведущих нулей нет.
Поэтому поиск распадается на две части. Сначала нужно найти единственную длину \(L\), для которой
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
После этого определяется остаточный ранг внутри этой длины:
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
Дальше остаётся чисто комбинаторная задача: найти \(R\)-ю допустимую строку длины \(L\) в лексикографическом порядке.
Пусть уже зафиксирован префикс длины \(p\), в котором использовано \(p_1\) единиц, \(p_2\) двоек и \(p_3\) троек. Тогда оставшаяся длина равна
$$r=L-p.$$
Если итоговая тройка количеств равна \((A,B,C)\), то суффиксу ещё нужно добавить
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
где \(a,b,c\ge 0\) и \(a+b+c=r\). Для этой конкретной конечной тройки число возможных продолжений равно
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$
Суммирование по всем допустимым конечным тройкам даёт размер блока
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
Если пробовать следующую цифру в порядке \(1,2,3\), то все допустимые продолжения распадаются на последовательные лексикографические блоки. Если нужный ранг больше размера первого блока, этот блок вычитается и рассматривается следующая цифра; иначе выбранная цифра фиксируется.
Первые допустимые значения для количеств таковы:
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
Следовательно, \(4\notin\mathcal{S}\). Это сразу объясняет первые длины. Для \(L=1,2,3\) любая тройка количеств использует только значения \(0,1,2,3\), поэтому любая строка над алфавитом \(\{1,2,3\}\) допустима и
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
Суммарно до длины \(3\) получаем
$$3+9+27=39.$$
Значит, \(40\)-е 123-число должно быть первой допустимой строкой длины \(4\). Лексикографически минимальный кандидат — это \(1111\), но его тройка количеств равна \((4,0,0)\), а потому недопустима. Следующий кандидат — \(1112\), у него тройка \((3,1,0)\), и оба положительных количества \(3\) и \(1\) допустимы. Следовательно, первой допустимой строкой длины \(4\) является \(1112\), то есть \(40\)-е 123-число равно \(1112\).
Реализации на C++, Python и Java используют один и тот же план. Сначала они строят булеву таблицу допустимых значений количеств в порядке возрастания, тем самым раскрывая рекурсивное определение итеративно. Затем по мере необходимости расширяются строки треугольника Паскаля, чтобы все биномиальные коэффициенты для мультиномиальных формул были доступны за постоянное время.
Все подсчёты насыщаются на уровне \(N+1\). Этого достаточно, потому что как только размер блока уже превосходит оставшийся ранг, точное значение блока больше не нужно. После предвычислений реализация суммирует \(F(1),F(2),\dots\), пока не определит целевую длину, а затем строит ответ слева направо, вычисляя для кандидатов \(1\), \(2\) и \(3\) число допустимых продолжений текущего префикса.
Когда итоговая десятичная строка уже известна, остаток по модулю \(123123123\) вычисляется слева направо по формуле
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$
Поэтому полное значение ответа никогда не нужно хранить в виде гигантского целого.
Пусть \(M\) — размер таблицы допустимых количеств, а \(L\) — длина искомого числа. Построение таблицы допустимости требует \(O(M\log M)\) времени, поскольку каждый кандидат просматривается по цифрам, и \(O(M)\) памяти. Расширение треугольника Паскаля до длины \(L\) требует \(O(L^2)\) времени и \(O(L^2)\) памяти.
Чтобы найти правильную длину, реализация вычисляет \(F(\ell)\) для \(\ell=1,2,\dots,L\). Каждое такое вычисление перебирает \(O(\ell^2)\) пар количеств, так что суммарная стоимость равна
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
Этап unranking выполняет не более трёх префиксных запросов на позицию, а каждый запрос перебирает допустимые конечные тройки за \(O(L^2)\). Это даёт ещё одну фазу \(O(L^3)\). В итоге общий порядок работы равен
$$O(M\log M+L^3),$$
а потребление памяти для целевой задачи составляет \(O(M+L^2)\).
يُسمّى العدد الصحيح الموجب عددًا من نوع 123 إذا كانت كتابته العشرية تحتوي فقط على الأرقام \(1\) و\(2\) و\(3\)، وإذا كان كل عدد ظهور غير صفري لهذه الأرقام هو نفسه عددًا صالحًا من النوع 123. إذا رمزنا إلى عدد مرات ظهور الأرقام \(1\) و\(2\) و\(3\) في \(n\) بالرموز \(c_1(n)\) و\(c_2(n)\) و\(c_3(n)\)، فإن كل قيمة موجبة بينها يجب أن تحقق القاعدة العودية نفسها مرة أخرى. المطلوب هو إيجاد العدد رقم \(N\) في الترتيب التصاعدي ثم إخراج قيمته بترديد \(123123123\).
الفكرة الأساسية ليست توليد جميع الأعداد الصالحة واحدًا واحدًا، بل عدّها على مستوى كتل كاملة بحسب الطول وبحسب ثلاثية الأعداد \((A,B,C)\) التي تمثل عدد مرات ظهور \(1\) و\(2\) و\(3\). متى كانت هذه الثلاثية مقبولة، فإن عدد السلاسل الموافقة لها يُعطى مباشرة بمعامل متعدد الحدود، ولذلك يستطيع الحل القفز مباشرة إلى الرتبة المطلوبة.
لنرمز بـ \(\mathcal{S}\) إلى مجموعة الأعداد الصحيحة الموجبة المسموح باستخدامها كأعداد ظهور للأرقام. نبدأ من
$$1 \in \mathcal{S}.$$
وبالنسبة إلى \(n>1\)، يجب أولًا أن تكون كل خانات \(n\) ضمن المجموعة \(\{1,2,3\}\)، ثم يتحقق أيضًا الشرط
$$\forall i \in \{1,2,3\},\ c_i(n)=0 \text{ or } c_i(n)\in\mathcal{S}.$$
هذه العودية يمكن حسابها من الأصغر إلى الأكبر لأن كل قيمة \(c_i(n)\) لا تتجاوز عدد خانات \(n\)، وبالتالي فهي أصغر من \(n\) عندما يكون \(n>1\). لهذا السبب، حين نختبر العدد \(n\)، تكون جميع القيم الأصغر التي يعتمد عليها القرار معروفة مسبقًا.
ثبّت طولًا مقداره \(L\). لنفترض أن السلسلة النهائية تحتوي على \(A\) مرات للرقم \(1\)، و\(B\) مرات للرقم \(2\)، و\(C\) مرات للرقم \(3\). عندئذ
$$A+B+C=L,$$
وتكون الثلاثية مقبولة إذا وفقط إذا كانت كل قيمة غير صفرية من \(\{A,B,C\}\) تنتمي إلى \(\mathcal{S}\).
ولثلاثية مقبولة ثابتة، يكون عدد السلاسل المختلفة الممكنة هو
$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$
إذًا فإن العدد الكلي لأعداد 123 ذات الطول \(L\) يساوي
$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$
وبذلك تتحول المسألة من فحص جميع السلاسل الخام وعددها \(3^L\) إلى فحص ثلاثيات العدّ المقبولة فقط.
كل عدد صالح ذي خانات أقل هو أصغر عدديًا من أي عدد صالح ذي خانات أكثر. وداخل طول ثابت، يتطابق الترتيب القاموسي مع الترتيب العددي لأن الأعداد لا تحتوي على أصفار بادئة.
لهذا تنقسم عملية البحث إلى مرحلتين. أولًا نحدد الطول الوحيد \(L\) الذي يحقق
$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$
ثم نعرّف الرتبة المتبقية داخل هذا الطول بأنها
$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$
بعد ذلك تصبح المهمة تركيبيّة بحتة: إيجاد السلسلة الصالحة رقم \(R\) من بين السلاسل ذات الطول \(L\) عندما تُرتَّب ترتيبًا قاموسيًا.
افترض أننا ثبّتنا بالفعل بادئة طولها \(p\)، واستهلكت هذه البادئة \(p_1\) من الرقم \(1\)، و\(p_2\) من الرقم \(2\)، و\(p_3\) من الرقم \(3\). الطول المتبقي هو
$$r=L-p.$$
إذا كانت ثلاثية العدّ النهائية هي \((A,B,C)\)، فإن اللاحقة تحتاج إلى
$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$
مع الشرط \(a,b,c\ge 0\) و\(a+b+c=r\). بالنسبة إلى هذه الثلاثية النهائية الثابتة، يكون عدد الإكمالات الممكنة
$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$
وبجمع هذا المقدار على جميع الثلاثيات النهائية المقبولة نحصل على حجم الكتلة
$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$
عند تجربة الرقم التالي بالترتيب \(1\) ثم \(2\) ثم \(3\)، فإن جميع الإكمالات الصالحة تنقسم إلى كتل قاموسية متتالية. إذا كانت الرتبة المطلوبة أكبر من الكتلة الأولى، نطرح حجمها وننتقل إلى الرقم التالي؛ وإلا فإن هذا الرقم هو الاختيار الصحيح لتلك الخانة.
أول القيم المقبولة كأعداد ظهور هي
$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$
ولذلك فإن \(4\notin\mathcal{S}\). هذه الملاحظة تفسر الأطوال الأولى مباشرة. عندما يكون \(L=1,2,3\)، فإن كل ثلاثية عدّ تستخدم فقط القيم \(0,1,2,3\)، ولهذا تكون جميع السلاسل الثلاثية ممكنة وصالحة، وبالتالي
$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$
إجمالي الأعداد الصالحة حتى الطول \(3\) هو إذن
$$3+9+27=39.$$
ومن ثم فإن العدد رقم \(40\) يجب أن يكون أول سلسلة صالحة ذات طول \(4\). أصغر مرشح قاموسيًا هو \(1111\)، لكن ثلاثية عدّه هي \((4,0,0)\)، وهي غير مقبولة لأن \(4\notin\mathcal{S}\). المرشح التالي هو \(1112\)، وثلاثيته \((3,1,0)\)، والقيمتان الموجبتان \(3\) و\(1\) مقبولتان. إذن أول سلسلة صالحة ذات طول \(4\) هي \(1112\)، وبالتالي يكون العدد رقم \(40\) هو \(1112\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها. في البداية تبني جدولًا منطقيًا للقيم المقبولة كأعداد ظهور بترتيب تصاعدي، وبذلك تتحول العودية إلى معالجة تكرارية. بعد ذلك تُبنى صفوف مثلث باسكال عند الحاجة، مما يجعل معاملات الاختيار الثنائية المستخدمة في صيغ العدّ متعددة الحدود متاحة بزمن ثابت.
جميع عمليات العدّ تُشبَع عند القيمة \(N+1\). وهذا يكفي لأننا متى عرفنا أن كتلة ما أكبر من الرتبة المتبقية، فلن نحتاج إلى قيمتها الدقيقة بعد ذلك. ثم تجمع الشيفرة القيم \(F(1),F(2),\dots\) حتى تحدد الطول الهدف، وبعدها تبني الجواب خانةً خانة عبر حساب عدد الإكمالات الصالحة الناتجة عن اختيار الرقم التالي \(1\) أو \(2\) أو \(3\).
وعندما تصبح السلسلة العشرية النهائية معروفة، يُحسب الباقي modulo \(123123123\) من اليسار إلى اليمين بالعلاقة
$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$
وهكذا لا تكون هناك حاجة إلى تحويل الجواب الكامل إلى عدد صحيح ضخم.
لنرمز بـ \(M\) إلى حجم جدول القيم المقبولة، وبـ \(L\) إلى طول العدد الهدف. بناء جدول المقبولية يكلف \(O(M\log M)\) زمنًا لأن كل مرشح يُفحص خانةً خانة، ويحتاج إلى \(O(M)\) ذاكرة. أما بناء صفوف مثلث باسكال حتى الطول \(L\) فيكلف \(O(L^2)\) زمنًا وذاكرة.
ولإيجاد الطول الصحيح، تحسب الشيفرة القيم \(F(\ell)\) لكل \(\ell=1,2,\dots,L\). وكل عملية حساب من هذا النوع تمر على \(O(\ell^2)\) من أزواج العدّ، ولذلك تكون الكلفة الكلية
$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$
أما مرحلة استخراج الرتبة فتجري في كل موضع ما لا يزيد على ثلاث استعلامات للبادئة، وكل استعلام يمسح الثلاثيات النهائية المقبولة في \(O(L^2)\)، فنحصل على مرحلة إضافية من رتبة \(O(L^3)\). وبصورة إجمالية تعمل الطريقة في
$$O(M\log M+L^3)$$
زمنًا وتستخدم \(O(M+L^2)\) ذاكرة في حالة المسألة الهدف.