A very odd number, as encoded by the implementations, is a positive integer divisible by \(105\) whose decimal expansion uses each of the five odd digits \(1,3,5,7,9\) a positive odd number of times. The problem asks for the \(10^{16}\)-th such number in increasing numerical order.
Direct enumeration is hopeless. Even after the divisibility filters, the search space contains huge blocks of repeated-digit permutations, and the target index is far beyond what brute force could reach. The successful approach is to work with digit-count vectors, separate the divisibility conditions, count multiset permutations by their remainder modulo \(7\), and then reconstruct the answer digit by digit in lexicographic order.
The key point is that the value of a candidate number depends on two different kinds of data: how many times each odd digit appears, and in which order those digits are arranged. The code treats those two layers separately.
For a fixed length \(L\), write
$$c=(c_1,c_3,c_5,c_7,c_9),$$
where \(c_d\) is the number of occurrences of digit \(d\). Every component must be a positive odd integer, so we may write \(c_d=2a_d+1\) with \(a_d\ge 0\). Therefore
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
Immediately, every valid length is odd and at least \(5\). For a chosen length, the problem first reduces to listing all possible count vectors \(c\). Since all digits are nonzero, there is no leading-zero complication: within a fixed length, numerical order is exactly lexicographic order on the digit strings.
Once a count vector \(c\) is fixed, divisibility by \(3\) depends only on the digit sum:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
No permutation can change that sum, so this is an early filter on the vector itself.
Divisibility by \(5\) is even more rigid. Because only odd digits are allowed, the last digit must be \(5\). Hence \(c_5\ge 1\), and after reserving the final digit we are left with the shorter multiset
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
If the whole number is written as \(10P+5\), then divisibility by \(7\) becomes
$$10P+5\equiv 0 \pmod 7.$$
Since \(10\equiv 3 \pmod 7\) and \(3^{-1}\equiv 5 \pmod 7\), this is equivalent to
$$P\equiv 3 \pmod 7.$$
So for each admissible count vector, the counting problem is exact and finite: how many distinct permutations of the multiset \(c'\) have remainder \(3\) modulo \(7\)?
For any nonnegative state
$$u=(u_1,u_3,u_5,u_7,u_9),$$
define \(R_u[r]\) to be the number of distinct digit strings using exactly those counts and having value congruent to \(r\pmod 7\). The empty state is the base case:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \text{ for } r\ne 0.$$
If \(|u|=u_1+u_3+u_5+u_7+u_9=m\) and we place digit \(d\) as the most significant digit of the remaining block, then the rest of the block has length \(m-1\), so its contribution is shifted by a factor \(10^{m-1}\). This gives the transition
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r],$$
where \(e_d\) subtracts one copy of digit \(d\). Memoization makes this effective because the same count state appears repeatedly while scanning many candidate vectors and many suffixes during reconstruction.
Length \(5\) would force one copy of each digit \(1,3,5,7,9\). Their sum is \(25\), which is not divisible by \(3\), so no length-\(5\) number can work.
The smallest possible length is therefore \(7\). To keep the number as small as possible, the first count vector to test is
$$c=(3,1,1,1,1),$$
meaning three \(1\)'s and one copy of each of \(3,5,7,9\). Its digit sum is
$$3\cdot 1+3+5+7+9=27,$$
so the divisibility-by-\(3\) condition is satisfied. Reserving the last digit \(5\) leaves the multiset \(\{1,1,1,3,7,9\}\). We need the prefix \(P\) to satisfy \(P\equiv 3\pmod 7\). Among the lexicographically ordered distinct permutations of that multiset, the first one with remainder \(3\) is
$$P=111793.$$
Hence the smallest very odd number is
$$1117935,$$
which indeed is divisible by \(105\). This is exactly the first validation example used by the implementations.
After counting how many valid numbers exist for each odd length, we locate the unique length block containing the target index. Inside that block, the answer is built digit by digit.
Suppose a prefix has already been fixed, and let \(\rho\) be its contribution modulo \(7\) in the full length-\(L\) decimal number. If the remaining middle block is the integer \(S\), then the unfinished number has the form
$$\rho + 10S + 5 \pmod 7.$$
Therefore the suffix must satisfy
$$10S\equiv -(\rho+5)\pmod 7,$$
or equivalently
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
For each tentative next digit, the code subtracts the already used digits from every admissible total count vector, asks the DP table how many suffix permutations hit that required remainder, and sums those completion counts. The first digit whose completion count contains the target rank is chosen. Because digits are tested in increasing order, this is exactly lexicographic rank selection within the correct length.
The implementations iterate through odd lengths \(L=5,7,9,\dots\). For each \(L\), they generate every count vector with positive odd entries summing to \(L\). Vectors failing the digit-sum test modulo \(3\) are discarded immediately, and vectors with no \(5\) are impossible because the last digit is forced to be \(5\).
Every surviving vector contributes the number of permutations of \(c'\) whose remainder modulo \(7\) is \(3\). Adding these contributions gives the size of the entire length-\(L\) block. The C++ and Java implementations split this counting stage across several worker tasks; the Python implementation performs the same arithmetic serially.
The central cache stores, for each multiset state \(u\), a table of seven counts, one for each remainder class modulo \(7\). The only arithmetic precomputation needed is \(10^k \bmod 7\) for relevant powers \(k\), because the DP transition depends on the decimal place of the digit being inserted.
This cache is reused in two places: first when counting how many valid numbers a whole count vector contributes, and later when asking how many suffixes can complete a partially fixed prefix.
Once the target length is known, the code keeps a running record of how many copies of each digit have already been used and what the current prefix contributes modulo \(7\). At each position before the final digit, it tries the candidate digits \(1,3,5,7,9\) in increasing order.
For each candidate, it scans all admissible total count vectors of that length, checks which ones are still compatible with the chosen prefix and the reserved final \(5\), converts the leftover counts into a suffix state, and reads from the DP table how many suffixes satisfy the needed remainder. If that total is smaller than the remaining rank, the code skips the whole block at once. Otherwise it fixes the candidate digit and moves to the next position. After all earlier positions are decided, the last digit \(5\) is appended.
Let \(M\) be the length of the final answer. Because the digit alphabet has fixed size \(5\) and the modulus is fixed at \(7\), the dynamic-programming state space is controlled entirely by the count vectors. The number of nonnegative count states with total size at most \(M-1\) is
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
so the memoized remainder tables require \(O(M^5)\) states and the same polynomial order of work, up to constant factors coming from the five digit choices and seven remainders.
For a fixed length \(L\), the raw number of positive odd count vectors is
$$\binom{\frac{L-5}{2}+4}{4},$$
before the divisibility filters remove many of them. Reconstruction tries at most five candidate digits at each of the first \(L-1\) positions and scans the admissible vectors for that length, so its extra cost is linear in \(L\) times the number of surviving vectors. In practice, this is tiny compared with brute-force enumeration of the actual integers, because the algorithm works with aggregated multiset states rather than individual numbers.
Eine sehr ungerade Zahl ist in den Implementierungen eine positive ganze Zahl, die durch \(105\) teilbar ist und in ihrer Dezimalschreibweise jede der fünf ungeraden Ziffern \(1,3,5,7,9\) eine positive ungerade Anzahl von Malen enthält. Gesucht ist die \(10^{16}\)-te solche Zahl in aufsteigender numerischer Reihenfolge.
Vollständiges Aufzählen ist unmöglich. Selbst nach den Teilbarkeitsfiltern bleiben riesige Blöcke von Permutationen mit Wiederholungen übrig, und der Zielindex ist astronomisch groß. Daher arbeitet die Lösung mit Zählvektoren, trennt die Bedingungen für \(3\), \(5\) und \(7\), zählt Multimengen-Permutationen nach ihrem Rest modulo \(7\) und rekonstruiert die gesuchte Zahl anschließend zifferweise in lexikographischer Reihenfolge.
Der Wert einer Kandidatenzahl hängt von zwei verschiedenen Ebenen ab: erstens davon, wie oft jede ungerade Ziffer vorkommt, und zweitens von der Reihenfolge dieser Ziffern. Genau diese Trennung nutzt die Herleitung.
Für eine feste Länge \(L\) schreiben wir
$$c=(c_1,c_3,c_5,c_7,c_9),$$
wobei \(c_d\) die Anzahl der Vorkommen der Ziffer \(d\) bezeichnet. Jede Komponente muss positiv und ungerade sein, also \(c_d=2a_d+1\) mit \(a_d\ge 0\). Damit gilt
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
Also ist jede gültige Länge ungerade und mindestens \(5\). Für eine feste Länge reduziert sich das Problem zunächst auf die Liste aller möglichen Zählvektoren \(c\). Da keine Nullziffer vorkommt, gibt es keinen Sonderfall mit führenden Nullen: Bei fester Länge stimmt die numerische Ordnung mit der lexikographischen Ordnung überein.
Ist der Zählvektor \(c\) fest, dann hängt die Teilbarkeit durch \(3\) nur von der Ziffernsumme ab:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
Keine Permutation ändert diese Summe, also kann dieser Test sofort auf dem Vektor selbst erfolgen.
Die Teilbarkeit durch \(5\) ist noch starrer. Weil nur ungerade Ziffern erlaubt sind, muss die letzte Ziffer eine \(5\) sein. Daher gilt \(c_5\ge 1\), und nach dem Reservieren der Endziffer bleibt die kürzere Multimenge
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
Schreibt man die ganze Zahl als \(10P+5\), dann wird die Bedingung für \(7\) zu
$$10P+5\equiv 0 \pmod 7.$$
Mit \(10\equiv 3 \pmod 7\) und \(3^{-1}\equiv 5 \pmod 7\) ist das gleichbedeutend mit
$$P\equiv 3 \pmod 7.$$
Für jeden zulässigen Zählvektor bleibt also eine saubere Restfrage übrig: Wie viele verschiedene Permutationen der Multimenge \(c'\) haben Rest \(3\) modulo \(7\)?
Für jeden nichtnegativen Zustand
$$u=(u_1,u_3,u_5,u_7,u_9)$$
sei \(R_u[r]\) die Anzahl der verschiedenen Ziffernfolgen mit genau diesen Häufigkeiten und Wert \(r\pmod 7\). Der leere Zustand ist der Startfall:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
Hat \(u\) die Gesamtlänge \(m\) und setzt man Ziffer \(d\) an die vorderste noch freie Stelle, dann verschiebt sich der Rest des Blocks um den Faktor \(10^{m-1}\). Daraus folgt die Übergangsformel
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
Memoisierung ist hier entscheidend, weil dieselben Zählzustände sowohl beim Blockzählen als auch später bei vielen Suffixabfragen immer wieder auftauchen.
Bei Länge \(5\) müsste jede Ziffer \(1,3,5,7,9\) genau einmal vorkommen. Die Ziffernsumme wäre dann \(25\), also nicht durch \(3\) teilbar. Es gibt daher keine gültige Zahl der Länge \(5\).
Die kleinste mögliche Länge ist also \(7\). Um den Zahlenwert möglichst klein zu halten, betrachtet man zuerst den Vektor
$$c=(3,1,1,1,1),$$
also drei Einsen und je eine \(3,5,7,9\). Die Ziffernsumme ist
$$3\cdot 1+3+5+7+9=27,$$
also durch \(3\) teilbar. Nach dem Reservieren der letzten \(5\) bleibt die Multimenge \(\{1,1,1,3,7,9\}\). Für deren Präfix \(P\) brauchen wir \(P\equiv 3\pmod 7\). Unter den lexikographisch geordneten verschiedenen Permutationen ist die erste mit Rest \(3\)
$$P=111793.$$
Damit erhält man als kleinste sehr ungerade Zahl
$$1117935,$$
und genau dieses Beispiel dient den Implementierungen als erster Korrektheitstest.
Nachdem für jede ungerade Länge gezählt wurde, wie viele gültige Zahlen existieren, ist der Zielindex in genau einem Längenblock lokalisiert. Innerhalb dieses Blocks wird die Antwort Ziffer für Ziffer aufgebaut.
Sei \(\rho\) der aktuelle Beitrag des bereits festgelegten Präfixes modulo \(7\) in der vollständigen Zahl der Länge \(L\). Ist \(S\) der noch offene Mittelblock, dann hat die unfertige Zahl die Form
$$\rho + 10S + 5 \pmod 7.$$
Also muss der Suffixblock die Kongruenz
$$10S\equiv -(\rho+5)\pmod 7$$
oder äquivalent
$$S\equiv -(\rho+5)\cdot 5 \pmod 7$$
erfüllen. Für jede versuchsweise nächste Ziffer zieht der Code die bereits verwendeten Häufigkeiten von allen zulässigen Gesamtvektoren ab, fragt die DP-Tabelle nach der nötigen Suffix-Restklasse und summiert die Anzahl der Vervollständigungen. Die erste Ziffer, deren Block den gesuchten Rang enthält, wird genommen. Weil die Ziffern aufsteigend getestet werden, ist das genau lexikographische Rangselektion.
Die Implementierungen durchlaufen die ungeraden Längen \(L=5,7,9,\dots\). Für jede Länge erzeugen sie alle Zählvektoren mit positiven ungeraden Einträgen und Summe \(L\). Vektoren, deren Ziffernsumme modulo \(3\) scheitert, werden sofort verworfen; ebenso Vektoren ohne \(5\), weil die Endziffer fest auf \(5\) gesetzt ist.
Jeder verbleibende Vektor trägt die Anzahl der Permutationen von \(c'\) mit Rest \(3\) modulo \(7\) bei. Die Summe dieser Beiträge ist die Größe des gesamten Längenblocks. C++ und Java parallelisieren diese Zählphase über mehrere Arbeitseinheiten, Python rechnet dieselbe Mathematik seriell.
Das Zentrum der Lösung ist ein Cache, der für jeden Multimengen-Zustand \(u\) ein Feld mit sieben Einträgen speichert, je einen für jede Restklasse modulo \(7\). Als einzige Zahlentheorie-Vorbereitung werden Potenzen \(10^k \bmod 7\) vorab berechnet, weil jeder DP-Übergang die Stellenwertverschiebung einer Ziffer benötigt.
Dieser Cache wird an zwei Stellen wiederverwendet: zuerst beim Zählen ganzer Zählvektoren und später noch einmal, wenn für ein schon teilweise festes Präfix alle zulässigen Suffixe abgefragt werden.
Sobald die Ziellänge feststeht, führen die Programme mit, wie viele Kopien jeder Ziffer bereits benutzt wurden und welchen Restbeitrag das aktuelle Präfix modulo \(7\) hat. An jeder Position vor der letzten Ziffer werden die Kandidaten \(1,3,5,7,9\) in aufsteigender Reihenfolge ausprobiert.
Für jeden Kandidaten werden alle zulässigen Gesamtvektoren dieser Länge geprüft: Ist der Vektor noch mit dem Präfix und der reservierten Schluss-\(5\) vereinbar, dann entsteht daraus ein Suffix-Zustand, und die DP-Tabelle liefert die Zahl der Suffixe mit dem benötigten Rest. Ist diese Gesamtzahl kleiner als der noch gesuchte Rang, wird der ganze Block übersprungen. Andernfalls wird die Ziffer fest gewählt und die nächste Position behandelt. Am Ende wird die letzte \(5\) angehängt.
Sei \(M\) die Länge der gesuchten Endantwort. Weil sowohl das Ziffernalphabet als auch der Modul \(7\) fest sind, wird der Zustandsraum vollständig durch die Zählvektoren bestimmt. Die Anzahl nichtnegativer Zustände mit Gesamtsumme höchstens \(M-1\) ist
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
also benötigen die memoisierten Resttabellen \(O(M^5)\) Zustände und dieselbe polynomielle Größenordnung an Rechenarbeit, abgesehen von konstanten Faktoren durch fünf Ziffern und sieben Restklassen.
Für eine feste Länge \(L\) beträgt die rohe Anzahl positiver ungerader Zählvektoren
$$\binom{\frac{L-5}{2}+4}{4},$$
bevor die Teilbarkeitsfilter viele davon entfernen. Die Rekonstruktion probiert an den ersten \(L-1\) Stellen jeweils höchstens fünf Kandidaten und scannt die zulässigen Vektoren dieser Länge, also ist ihr Zusatzaufwand linear in \(L\) mal der Zahl der überlebenden Vektoren. Praktisch ist das winzig im Vergleich zur direkten Enumeration aller ganzen Zahlen, weil die Lösung nur mit aggregierten Multimengen-Zuständen arbeitet.
Uygulamaların kullandığı tanıma göre çok garip bir sayı, \(105\)'e bölünen ve onluk yazımında \(1,3,5,7,9\) rakamlarının her birini pozitif tek sayıda kez içeren pozitif bir tamsayıdır. İstenen şey, artan sayısal sıradaki \(10^{16}\). böyle sayıyı bulmaktır.
Doğrudan listeleme imkansızdır. Bölünebilme filtrelerinden sonra bile tekrar eden rakam permütasyonlarından oluşan çok büyük bloklar kalır ve hedef indeks kaba kuvvetin çok ötesindedir. Bu yüzden çözüm, rakam sayım vektörleriyle çalışır, \(3\), \(5\) ve \(7\) koşullarını birbirinden ayırır, çoklu küme permütasyonlarını mod \(7\) kalanlarına göre sayar ve ardından cevabı leksikografik sırada basamak basamak kurar.
Bir aday sayının değeri iki ayrı bileşene bağlıdır: her tek rakamın kaç kez kullanıldığı ve bu rakamların hangi sırayla dizildiği. Çözüm tam olarak bu iki katmanı ayırır.
Sabit bir \(L\) uzunluğu için
$$c=(c_1,c_3,c_5,c_7,c_9)$$
yazalım; burada \(c_d\), \(d\) rakamının tekrar sayısıdır. Her bileşen pozitif ve tek olmalıdır; dolayısıyla \(c_d=2a_d+1\) biçiminde yazılabilir ve \(a_d\ge 0\) olur. O zaman
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
Böylece geçerli her uzunluğun en az \(5\) ve tek olduğu hemen çıkar. Sabit bir uzunlukta ilk iş, bu koşulu sağlayan bütün sayım vektörlerini üretmektir. Kullanılan rakamların hiçbiri sıfır olmadığı için baştaki sıfır sorunu yoktur; aynı uzunluk içinde sayısal sıra ile leksikografik sıra aynıdır.
Bir sayım vektörü \(c\) sabitlendiğinde, \(3\)'e bölünebilme yalnızca rakam toplamına bağlıdır:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
Hiçbir permütasyon bu toplamı değiştirmez; dolayısıyla bu koşul vektör üzerinde erken bir filtredir.
\(5\)'e bölünebilme daha da katıdır. Sadece tek rakamlar kullanılabildiği için son basamak mutlaka \(5\) olmalıdır. Bu yüzden \(c_5\ge 1\) gerekir ve son basamağı ayırdıktan sonra geriye şu daha kısa çoklu küme kalır:
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
Tam sayıyı \(10P+5\) biçiminde yazarsak, \(7\) koşulu
$$10P+5\equiv 0 \pmod 7$$
olur. \(10\equiv 3 \pmod 7\) ve \(3^{-1}\equiv 5 \pmod 7\) olduğundan bu,
$$P\equiv 3 \pmod 7$$
ile eşdeğerdir. Yani her geçerli sayım vektörü için asıl soru şudur: \(c'\) çoklu kümesinin farklı permütasyonlarından kaç tanesi mod \(7\)'de \(3\) kalanı verir?
Herhangi bir negatif olmayan
$$u=(u_1,u_3,u_5,u_7,u_9)$$
durumu için \(R_u[r]\), tam olarak bu adetlerle kurulan ve değeri \(r\pmod 7\) olan farklı rakam dizilerinin sayısı olsun. Boş durum taban durumudur:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
\(|u|=u_1+u_3+u_5+u_7+u_9=m\) iken kalan bloğun en başına \(d\) rakamını koyarsak, geri kalan kısım \(m-1\) basamak sola kaymış olur. Bu da şu geçişi verir:
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
Burada \(e_d\), ilgili rakamdan bir kopya eksiltir. Memoization kritik önemdedir; çünkü aynı durumlar hem uzunluk bloklarını sayarken hem de daha sonra çok sayıdaki son-ek sorgusunda tekrar tekrar ortaya çıkar.
\(5\) basamaklı durumda her rakam \(1,3,5,7,9\) tam bir kez görünmek zorundadır. Bu rakamların toplamı \(25\) eder ve \(3\)'e bölünmez. Dolayısıyla \(5\) basamaklı geçerli sayı yoktur.
O halde en küçük aday uzunluk \(7\)'dir. Sayıyı mümkün olduğunca küçük tutmak için önce
$$c=(3,1,1,1,1)$$
vektörüne bakılır; yani üç tane \(1\), ayrıca birer tane \(3,5,7,9\). Rakam toplamı
$$3\cdot 1+3+5+7+9=27$$
olduğundan \(3\) filtresini geçer. Son basamaktaki \(5\) ayrılınca geriye \(\{1,1,1,3,7,9\}\) kalır. Ön ek \(P\) için gereken koşul \(P\equiv 3\pmod 7\)'dir. Bu çoklu kümenin leksikografik sıradaki farklı permütasyonları arasında bu koşulu sağlayan ilki
$$P=111793$$
olur. Böylece en küçük çok garip sayı
$$1117935$$
çıkar; bu örnek uygulamaların doğrulama kontrolüyle de aynıdır.
Her tek uzunluk için kaç geçerli sayı olduğu sayıldıktan sonra, hedef indeksin düştüğü uzunluk bloğu belirlenir. O blok içinde cevap soldan sağa birer basamak eklenerek kurulur.
Diyelim ki bir ön ek sabitlendi ve \(\rho\), bu ön ekin tam \(L\) basamaklı sayıya yaptığı mod \(7\) katkısı olsun. Ortada henüz yerleştirilmemiş bölüm \(S\) ise, tamamlanmamış sayı
$$\rho + 10S + 5 \pmod 7$$
şeklindedir. O halde son ek şu koşulu sağlamalıdır:
$$10S\equiv -(\rho+5)\pmod 7,$$
ya da eşdeğer olarak
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
Her aday sonraki rakam için, kod kullanılan rakam sayılarını bütün uygun toplam vektörlerden çıkarır, kalan durumun bu gerekli kalanı verip vermediğini DP tablosundan sayar ve toplam tamamlama sayısını elde eder. Hedef sırayı içine alan ilk rakam seçilir. Rakamlar artan sırada denendiği için bu işlem tam olarak leksikografik sıra seçimidir.
Uygulamalar \(L=5,7,9,\dots\) biçimindeki tek uzunlukları sırayla dolaşır. Her \(L\) için, toplamı \(L\) olan ve bütün bileşenleri pozitif tek sayı olan sayım vektörleri üretilir. Rakam toplamı mod \(3\) koşulunu geçmeyen vektörler anında elenir; \(5\) içermeyen vektörler de imkansızdır çünkü son basamak sabit \(5\)'tir.
Kalan her vektör, \(c'\) çoklu kümesinin mod \(7\)'de \(3\) kalanı veren permütasyon sayısını katkı olarak ekler. Bu katkıların toplamı o uzunluğun blok büyüklüğünü verir. C++ ve Java sürümleri bu sayım aşamasını birkaç iş parçasına böler; Python sürümü aynı hesabı tek akışta yapar.
Çözümün merkezinde, her çoklu küme durumu \(u\) için yedi elemanlı bir tablo tutan bir önbellek vardır; her eleman mod \(7\)'de bir kalan sınıfını temsil eder. Gerekli tek aritmetik ön hesap, \(10^k \bmod 7\) değerleridir; çünkü DP geçişi eklenen rakamın onluk basamağını bilmek zorundadır.
Aynı önbellek iki kez kullanılır: önce bütün bir sayım vektörünün kaç sayı ürettiğini bulurken, sonra da kısmen belirlenmiş bir ön eki tamamlayabilecek son eklerin sayısını sorarken.
Hedef uzunluk belli olduktan sonra programlar, her rakamdan kaç kopya kullanıldığını ve mevcut ön ekin mod \(7\)'ye katkısını izler. Son basamak dışındaki her konumda aday rakamlar \(1,3,5,7,9\) artan sırayla denenir.
Her aday için, o uzunluktaki bütün uygun toplam vektörler taranır: aday ön ek ve ayrılmış son \(5\) ile uyumlu olanlar için kalan rakamlar bir son-ek durumuna dönüştürülür ve DP tablosundan gerekli kalanı veren son ek sayısı okunur. Bu toplam, aranan sıradan küçükse bütün blok atlanır. Değilse aday rakam sabitlenir ve sonraki konuma geçilir. En sonda sabit \(5\) eklenir.
Nihai cevabın uzunluğu \(M\) olsun. Rakam alfabesi \(5\) elemanlı ve modül \(7\) sabit olduğu için, durum uzayını bütünüyle sayım vektörleri belirler. Toplamı en fazla \(M-1\) olan negatif olmayan durum sayısı
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5}$$
olduğundan, memoize kalan tabloları \(O(M^5)\) mertebesinde durum ve aynı polinom mertebesinde işlem gerektirir; sabit çarpanlar yalnızca beş rakam seçeneği ve yedi kalan sınıfından gelir.
Sabit bir \(L\) uzunluğu için, filtrelerden önceki ham pozitif tek sayım vektörü sayısı
$$\binom{\frac{L-5}{2}+4}{4}$$
kadardır. Yeniden kurma aşaması ilk \(L-1\) konumun her birinde en fazla beş aday dener ve bu uzunluktaki uygun vektörleri tarar; dolayısıyla ek maliyet \(L\) ile hayatta kalan vektör sayısının çarpımı ölçeğindedir. Pratikte bu, gerçek tamsayıları tek tek dolaşmaya kıyasla çok küçüktür; çünkü algoritma tek tek sayılar yerine toplulaştırılmış çoklu küme durumlarıyla çalışır.
Según la definición que siguen las implementaciones, un número muy impar es un entero positivo divisible por \(105\) cuya expansión decimal contiene cada uno de los cinco dígitos impares \(1,3,5,7,9\) un número positivo e impar de veces. El objetivo es hallar el número número \(10^{16}\) de esta familia en orden numérico creciente.
Enumerar todos los candidatos no es viable. Incluso después de filtrar por divisibilidad, siguen quedando bloques enormes de permutaciones con dígitos repetidos, y el índice buscado está muy por encima del alcance de la fuerza bruta. La solución correcta trabaja con vectores de conteo, separa las condiciones de divisibilidad, cuenta permutaciones de multiconjuntos según su resto módulo \(7\) y luego reconstruye el resultado dígito a dígito en orden lexicográfico.
El valor de un candidato depende de dos capas distintas: cuántas veces aparece cada dígito impar y en qué orden se colocan esos dígitos. La derivación explota precisamente esa separación.
Para una longitud fija \(L\), escribimos
$$c=(c_1,c_3,c_5,c_7,c_9),$$
donde \(c_d\) es el número de apariciones del dígito \(d\). Cada componente debe ser positivo e impar, así que podemos poner \(c_d=2a_d+1\) con \(a_d\ge 0\). Entonces
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
De aquí se deduce enseguida que toda longitud válida es impar y al menos \(5\). Para una longitud concreta, el primer subproblema consiste en listar todos los vectores \(c\) posibles. Como no aparece el dígito cero, no existe un caso especial de ceros iniciales: para una longitud fija, el orden numérico coincide con el orden lexicográfico.
Una vez fijado el vector \(c\), la divisibilidad por \(3\) depende solo de la suma de cifras:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
Ninguna permutación altera esa suma, así que se trata de un filtro temprano sobre el propio vector.
La divisibilidad por \(5\) es todavía más rígida. Como solo se permiten dígitos impares, la última cifra debe ser \(5\). Por tanto \(c_5\ge 1\), y al reservar esa última cifra queda el multiconjunto más corto
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
Si escribimos el número completo como \(10P+5\), la condición de divisibilidad por \(7\) pasa a ser
$$10P+5\equiv 0 \pmod 7.$$
Como \(10\equiv 3 \pmod 7\) y \(3^{-1}\equiv 5 \pmod 7\), esto equivale a
$$P\equiv 3 \pmod 7.$$
Así, para cada vector admisible, la pregunta se vuelve muy concreta: ¿cuántas permutaciones distintas del multiconjunto \(c'\) tienen resto \(3\) módulo \(7\)?
Para cualquier estado no negativo
$$u=(u_1,u_3,u_5,u_7,u_9),$$
definimos \(R_u[r]\) como el número de cadenas de dígitos distintas que usan exactamente esas cantidades y cuyo valor es congruente con \(r\pmod 7\). El estado vacío es el caso base:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
Si la longitud total es \(m\) y colocamos el dígito \(d\) como cifra más significativa del bloque restante, el resto del bloque queda desplazado por \(10^{m-1}\). Por tanto, la transición es
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
La memoización es lo que vuelve viable este recuento, porque los mismos estados aparecen repetidamente al contar muchos vectores totales y también al responder consultas de sufijos durante la reconstrucción.
La longitud \(5\) obligaría a usar exactamente una vez cada dígito \(1,3,5,7,9\). Su suma es \(25\), que no es divisible por \(3\). Por eso no existe ningún número válido de longitud \(5\).
La primera longitud posible es entonces \(7\). Para mantener el valor lo más pequeño posible, el primer vector a estudiar es
$$c=(3,1,1,1,1),$$
es decir, tres unos y una copia de \(3,5,7,9\). La suma de cifras es
$$3\cdot 1+3+5+7+9=27,$$
así que supera el filtro de divisibilidad por \(3\). Al reservar el \(5\) final queda el multiconjunto \(\{1,1,1,3,7,9\}\). Necesitamos que el prefijo \(P\) cumpla \(P\equiv 3\pmod 7\). Entre las permutaciones distintas ordenadas lexicográficamente, la primera que cumple eso es
$$P=111793.$$
Por tanto, el menor número muy impar es
$$1117935,$$
y precisamente ese es el primer ejemplo de validación utilizado por las implementaciones.
Una vez contados los números válidos de cada longitud impar, se localiza el bloque de longitud que contiene el índice buscado. Dentro de ese bloque, la respuesta se construye fijando una cifra cada vez.
Supongamos que ya se ha fijado un prefijo y que \(\rho\) es su contribución módulo \(7\) dentro del número completo de longitud \(L\). Si \(S\) denota el bloque intermedio todavía no construido, el número parcial tiene la forma
$$\rho + 10S + 5 \pmod 7.$$
Así, el sufijo debe satisfacer
$$10S\equiv -(\rho+5)\pmod 7,$$
o de forma equivalente
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
Para cada dígito candidato, el código resta del vector total las copias ya usadas, consulta en la tabla DP cuántos sufijos alcanzan el resto exigido y suma esas completaciones sobre todos los vectores totales admisibles. El primer dígito cuyo bloque contiene el rango restante se acepta. Como los candidatos se prueban en orden creciente, el procedimiento implementa exactamente la selección lexicográfica.
Las implementaciones recorren las longitudes impares \(L=5,7,9,\dots\). Para cada \(L\), generan todos los vectores de conteo con entradas impares positivas cuya suma es \(L\). Los vectores que no pasan la prueba de suma de cifras módulo \(3\) se descartan enseguida, y los vectores sin \(5\) también son imposibles porque la última cifra está forzada.
Cada vector que sobrevive aporta el número de permutaciones de \(c'\) con resto \(3\) módulo \(7\). La suma de esas aportaciones da el tamaño completo del bloque de longitud \(L\). Las implementaciones en C++ y Java paralelizan esta fase de conteo; la versión en Python realiza la misma cuenta en serie.
El corazón de la solución es una caché que guarda, para cada estado de multiconjunto \(u\), un arreglo de siete entradas, una por cada clase de resto módulo \(7\). La única precomputación aritmética necesaria son las potencias \(10^k \bmod 7\), ya que cada transición DP depende del peso decimal de la cifra que se coloca.
La misma caché se reutiliza en dos momentos: primero al contar cuántos números genera un vector total y luego al preguntar cuántos sufijos pueden completar un prefijo ya fijado.
Una vez conocida la longitud objetivo, los programas mantienen cuántas copias de cada dígito se han usado y cuál es la contribución módulo \(7\) del prefijo actual. En cada posición anterior a la última, prueban los candidatos \(1,3,5,7,9\) en orden creciente.
Para cada candidato, se recorren todos los vectores totales admisibles de esa longitud: si el vector sigue siendo compatible con el prefijo elegido y con el \(5\) final reservado, se transforma en un estado de sufijo y la tabla DP devuelve cuántos sufijos tienen el resto requerido. Si ese total es menor que el rango restante, se salta todo el bloque. En caso contrario, la cifra se fija y el proceso continúa. Al final se añade el \(5\) final.
Sea \(M\) la longitud de la respuesta final. Como el alfabeto de dígitos tiene tamaño fijo \(5\) y el módulo \(7\) también es fijo, el tamaño del espacio de estados depende solo de los vectores de conteo. El número de estados no negativos con suma total a lo sumo \(M-1\) es
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
de modo que las tablas memoizadas de restos ocupan \(O(M^5)\) estados y requieren el mismo orden polinómico de trabajo, salvo factores constantes procedentes de las cinco opciones de dígito y los siete restos.
Para una longitud fija \(L\), el número bruto de vectores de conteo impares positivos es
$$\binom{\frac{L-5}{2}+4}{4}$$
antes de aplicar los filtros de divisibilidad. La reconstrucción prueba como máximo cinco candidatos en cada una de las primeras \(L-1\) posiciones y recorre los vectores admisibles de esa longitud, así que su coste adicional es lineal en \(L\) por el número de vectores supervivientes. En la práctica, eso es muchísimo menor que enumerar los enteros reales, porque el algoritmo trabaja con estados agregados de multiconjunto y no con números individuales.
按照这些实现所采用的定义，“Very Odd Number” 是指这样一种正整数：它能被 \(105\) 整除，并且十进制表示中五个奇数字 \(1,3,5,7,9\) 都出现了正的奇数次。题目要求按数值从小到大排序后，求出其中第 \(10^{16}\) 个数。
直接枚举完全不可行。即使先用整除条件过滤，仍然会留下规模巨大的重复数字排列块，而目标排名又远超暴力搜索的能力范围。可行的方法是先按数字出现次数建立状态，把对 \(3\)、\(5\)、\(7\) 的限制拆开处理，再用一个按模 \(7\) 余数分类的多重集排列 DP 来计数，最后按字典序逐位重建答案。
一个候选数的结构由两层信息决定：第一层是每个奇数字出现了多少次，第二层是这些数字以什么顺序排列。整个解法正是围绕这两层分离展开的。
对固定长度 \(L\)，记
$$c=(c_1,c_3,c_5,c_7,c_9),$$
其中 \(c_d\) 表示数字 \(d\) 的出现次数。每个分量都必须是正奇数，因此可以写成 \(c_d=2a_d+1\)，其中 \(a_d\ge 0\)。于是
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
这立刻说明所有合法长度都必须是奇数，而且至少为 \(5\)。对固定长度而言，第一步就是列出所有满足条件的计数向量 \(c\)。由于只会使用非零数字，所以不存在前导零的特殊情况；在固定长度内，数值顺序和字典序完全一致。
一旦计数向量 \(c\) 固定，能否被 \(3\) 整除只取决于数位和：
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
任何排列都不会改变这个和，所以这是对计数向量本身的一个早期筛选。
被 \(5\) 整除的条件更刚性。因为允许使用的只有奇数字，所以末位只能是 \(5\)。因此必须有 \(c_5\ge 1\)，预留最后一个 \(5\) 之后，前面部分对应的多重集变成
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
如果把整个数写成 \(10P+5\)，那么被 \(7\) 整除等价于
$$10P+5\equiv 0 \pmod 7.$$
由于 \(10\equiv 3 \pmod 7\)，而 \(3^{-1}\equiv 5 \pmod 7\)，所以它又等价于
$$P\equiv 3 \pmod 7.$$
这样一来，对于每个合法计数向量，问题就变成：由多重集 \(c'\) 组成的不同排列中，有多少个在模 \(7\) 下余数为 \(3\)？
对任意非负状态
$$u=(u_1,u_3,u_5,u_7,u_9),$$
定义 \(R_u[r]\) 为：恰好使用这些个数的数字，并且其十进制值满足 \( \equiv r \pmod 7\) 的不同数字串数量。空状态是基础情况：
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
若总长度 \(|u|=u_1+u_3+u_5+u_7+u_9=m\)，并把数字 \(d\) 放在当前剩余块的最高位，那么其余部分会整体乘上 \(10^{m-1}\)。于是转移就是
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
这里 \(e_d\) 表示把数字 \(d\) 的计数减少 \(1\)。记忆化之所以关键，是因为同一个计数状态会在不同总向量和不同后缀查询中反复出现；一旦算过，就可以被大量复用。
若长度为 \(5\)，那就只能让 \(1,3,5,7,9\) 各出现一次。它们的和是 \(25\)，不能被 \(3\) 整除，所以长度 \(5\) 根本没有合法数。
因此最小可能长度是 \(7\)。为了让数尽可能小，最先考虑的计数向量自然是
$$c=(3,1,1,1,1),$$
也就是三个 \(1\)，以及各一个 \(3,5,7,9\)。它的数位和为
$$3\cdot 1+3+5+7+9=27,$$
可以被 \(3\) 整除。把最后那个固定的 \(5\) 预留出去后，前缀多重集就是 \(\{1,1,1,3,7,9\}\)。我们需要前缀 \(P\) 满足 \(P\equiv 3\pmod 7\)。按字典序列出这个多重集的不同排列时，第一个满足该条件的前缀正是
$$P=111793.$$
因此最小的 very odd number 为
$$1117935,$$
这也正是实现里用于校验的第一个小样例。
先按长度统计出每个奇数长度一共贡献多少个合法数，就能确定目标排名落在哪一个长度块里。进入该长度块后，答案通过逐位确定来构造。
设当前已经固定了一个前缀，且它在完整 \(L\) 位数中的模 \(7\) 贡献为 \(\rho\)。把尚未填入的中间部分记为整数 \(S\)，那么未完成的整个数可以写成
$$\rho + 10S + 5 \pmod 7.$$
所以后缀必须满足
$$10S\equiv -(\rho+5)\pmod 7,$$
也就是
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
对每个候选下一位，代码都会从所有合法总计数向量中扣掉已经使用的数字，得到可能的后缀状态，然后从 DP 表里查出满足所需余数的后缀排列数，并把这些数量相加。第一个能够覆盖当前剩余排名的候选数字就被固定下来。由于候选数字是按从小到大的顺序尝试的，这恰好就是长度固定时的字典序排名选择。
实现依次遍历奇数长度 \(L=5,7,9,\dots\)。对每个 \(L\)，先生成所有分量为正奇数且总和为 \(L\) 的计数向量。数位和模 \(3\) 不合格的向量会被立刻丢弃；没有 \(5\) 的向量也不可能成立，因为末位必须固定为 \(5\)。
每个保留下来的向量都会贡献一个数量：预留末位 \(5\) 之后，剩余多重集在模 \(7\) 下余数为 \(3\) 的排列个数。把这些贡献加总，就得到该长度块的总大小。C++ 和 Java 实现把这一阶段并行化，Python 实现则按同样的数学逻辑串行执行。
核心缓存为每个多重集状态 \(u\) 保存一个长度为 \(7\) 的数组，对应模 \(7\) 的七个余数类。唯一需要预先算好的数论数据是 \(10^k \bmod 7\)，因为每次转移都要知道新增数字所在的十进制位权。
这套缓存会被重复使用两次：第一次是在统计整个计数向量能产生多少合法数时，第二次是在已经固定前缀后，查询还剩多少后缀可行时。
一旦目标长度确定，程序会维护两份信息：每个数字已经使用了多少次，以及当前前缀对模 \(7\) 的贡献是多少。在最后一位之前的每个位置，都按 \(1,3,5,7,9\) 的升序尝试候选数字。
对每个候选数字，程序扫描该长度的所有合法总计数向量，检查它们是否仍然与当前前缀以及预留的末位 \(5\) 相容；如果相容，就得到一个后缀状态，并从 DP 表中读出满足所需余数的后缀个数。若这个总数小于剩余排名，就说明整个候选块都可以跳过；否则当前候选数字就是答案的下一位。最后再补上固定的末位 \(5\)。
设最终答案的长度为 \(M\)。因为数字字母表固定为 \(5\) 个元素，而模数固定为 \(7\)，动态规划状态空间完全由计数向量决定。总和不超过 \(M-1\) 的非负状态数为
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
因此记忆化余数表需要 \(O(M^5)\) 级别的状态数和同量级的多项式工作量，常数因子只来自五种数字选择和七个余数类别。
对固定长度 \(L\)，在整除筛选之前，正奇数计数向量的原始数量为
$$\binom{\frac{L-5}{2}+4}{4}.$$
重建阶段在前 \(L-1\) 个位置的每一位上最多尝试五个候选数字，并扫描该长度下存活的合法向量，因此额外开销与 \(L\) 乘以合法向量数量成正比。和真正去枚举所有整数相比，这种代价非常小，因为算法始终在处理聚合后的多重集状态，而不是逐个处理具体数值。
В используемой реализациями модели очень нечётное число — это положительное целое, делящееся на \(105\), в десятичной записи которого каждая из пяти нечётных цифр \(1,3,5,7,9\) встречается положительное нечётное число раз. Нужно найти \(10^{16}\)-е такое число в порядке возрастания.
Полный перебор невозможен. Даже после фильтрации по делимости остаются огромные блоки перестановок с повторяющимися цифрами, а нужный индекс слишком велик для грубой силы. Поэтому решение работает с векторами кратностей, раскладывает условия делимости на независимые части, считает перестановки мультимножеств по остаткам modulo \(7\), а затем восстанавливает ответ по цифрам в лексикографическом порядке.
Значение кандидата определяется двумя слоями информации: сколько раз встречается каждая нечётная цифра и в каком порядке эти цифры расположены. Вся математика решения строится на отделении одного слоя от другого.
Для фиксированной длины \(L\) запишем
$$c=(c_1,c_3,c_5,c_7,c_9),$$
где \(c_d\) — количество вхождений цифры \(d\). Каждая компонента должна быть положительным нечётным числом, значит \(c_d=2a_d+1\) при \(a_d\ge 0\). Тогда
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
Отсюда сразу следует, что допустимая длина всегда нечётна и не меньше \(5\). Для заданной длины первая задача — перечислить все такие векторы \(c\). Так как цифра \(0\) вообще не используется, проблемы ведущих нулей нет: при фиксированной длине числовой порядок совпадает с лексикографическим.
После фиксации вектора \(c\) делимость на \(3\) зависит только от суммы цифр:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
Перестановка не меняет эту сумму, значит это ранний фильтр прямо на векторе кратностей.
Делимость на \(5\) ещё жёстче. Поскольку разрешены только нечётные цифры, последняя цифра обязана быть \(5\). Следовательно, \(c_5\ge 1\), а после резервирования последней цифры остаётся более короткое мультимножество
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
Если полное число записать как \(10P+5\), условие делимости на \(7\) принимает вид
$$10P+5\equiv 0 \pmod 7.$$
Так как \(10\equiv 3 \pmod 7\), а \(3^{-1}\equiv 5 \pmod 7\), это эквивалентно
$$P\equiv 3 \pmod 7.$$
Итак, для каждого допустимого вектора счёт сводится к точному вопросу: сколько различных перестановок мультимножества \(c'\) дают остаток \(3\) по модулю \(7\)?
Для любого неотрицательного состояния
$$u=(u_1,u_3,u_5,u_7,u_9)$$
обозначим через \(R_u[r]\) количество различных строк цифр с ровно такими кратностями и значением \(r\pmod 7\). Пустое состояние задаёт базу:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
Если общая длина равна \(m\), и мы ставим цифру \(d\) на самую старшую ещё не заполненную позицию, то оставшийся блок сдвигается весом \(10^{m-1}\). Поэтому переход имеет вид
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
Мемоизация здесь критична: одни и те же состояния появляются и при подсчёте целых блоков длины, и позже при многочисленных запросах о суффиксах во время восстановления ответа.
При длине \(5\) пришлось бы взять цифры \(1,3,5,7,9\) по одному разу. Их сумма равна \(25\), а это не делится на \(3\). Значит, допустимых чисел длины \(5\) нет.
Первая возможная длина — \(7\). Чтобы число было как можно меньше, естественно сначала рассмотреть вектор
$$c=(3,1,1,1,1),$$
то есть три единицы и по одной цифре \(3,5,7,9\). Сумма цифр равна
$$3\cdot 1+3+5+7+9=27,$$
поэтому фильтр делимости на \(3\) выполняется. После резервирования последней цифры \(5\) остаётся мультимножество \(\{1,1,1,3,7,9\}\). Для префикса \(P\) нужно условие \(P\equiv 3\pmod 7\). Среди различных перестановок этого мультимножества, упорядоченных лексикографически, первой подходящей оказывается
$$P=111793.$$
Следовательно, наименьшее очень нечётное число равно
$$1117935,$$
и именно этот пример используется реализациями как первая проверка корректности.
После того как подсчитано количество допустимых чисел для каждой нечётной длины, находится единственный блок длины, содержащий искомый индекс. Внутри этого блока ответ строится по цифрам.
Пусть уже зафиксирован некоторый префикс, а \(\rho\) — его вклад modulo \(7\) в полном числе длины \(L\). Если ещё не построенный средний блок обозначить через \(S\), то текущее незавершённое число имеет вид
$$\rho + 10S + 5 \pmod 7.$$
Значит, суффикс обязан удовлетворять
$$10S\equiv -(\rho+5)\pmod 7,$$
или, что то же самое,
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
Для каждой пробной следующей цифры код вычитает уже использованные количества из всех допустимых полных векторов, спрашивает у DP-таблицы число суффиксов с нужным остатком и суммирует эти варианты завершения. Первая цифра, чей блок покрывает оставшийся ранг, принимается. Поскольку цифры проверяются по возрастанию, это и есть точная лексикографическая выборка.
Реализации перебирают нечётные длины \(L=5,7,9,\dots\). Для каждой длины генерируются все векторы кратностей с положительными нечётными компонентами, сумма которых равна \(L\). Векторы, не проходящие проверку суммы цифр modulo \(3\), отбрасываются сразу, а векторы без цифры \(5\) невозможны, потому что последняя цифра фиксирована.
Каждый оставшийся вектор вносит вклад, равный числу перестановок мультимножества \(c'\) с остатком \(3\) modulo \(7\). Сумма этих вкладов даёт размер всего блока данной длины. В версиях на C++ и Java эта стадия распараллелена, а версия на Python выполняет ту же арифметику последовательно.
Центральный кэш хранит для каждого состояния мультимножества \(u\) массив из семи значений, по одному на каждый остаток modulo \(7\). Единственная числовая предвычисленная таблица — это значения \(10^k \bmod 7\), потому что каждый переход DP зависит от десятичного веса добавляемой цифры.
Этот кэш используется дважды: сначала при подсчёте вклада целого вектора кратностей, а потом при ответе на вопрос, сколько суффиксов может дополнить уже выбранный префикс.
Когда нужная длина найдена, программы поддерживают учёт того, сколько копий каждой цифры уже использовано, и текущий вклад префикса modulo \(7\). На каждой позиции до последней цифры кандидаты \(1,3,5,7,9\) пробуются в возрастающем порядке.
Для каждого кандидата просматриваются все допустимые полные векторы этой длины: если вектор ещё совместим с уже выбранным префиксом и с зарезервированной конечной \(5\), он превращается в состояние суффикса, и DP-таблица сообщает, сколько суффиксов дают нужный остаток. Если эта сумма меньше оставшегося ранга, весь блок пропускается. Иначе цифра фиксируется, и процесс продолжается. В конце приписывается последняя \(5\).
Пусть \(M\) — длина окончательного ответа. Поскольку алфавит цифр имеет фиксированный размер \(5\), а модуль всегда равен \(7\), пространство состояний полностью задаётся векторами кратностей. Число неотрицательных состояний с общей суммой не больше \(M-1\) равно
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
поэтому мемоизированные таблицы остатков занимают \(O(M^5)\) состояний и требуют того же полиномиального порядка вычислений, с небольшими константами от пяти цифр и семи классов остатков.
Для фиксированной длины \(L\) грубое число положительных нечётных векторов кратностей равно
$$\binom{\frac{L-5}{2}+4}{4}$$
до применения фильтров делимости. На этапе восстановления на каждой из первых \(L-1\) позиций пробуется не более пяти цифр и просматриваются допустимые векторы этой длины, поэтому дополнительная стоимость линейна по \(L\), умноженному на число оставшихся векторов. На практике это несравнимо меньше, чем перебирать реальные целые числа, потому что алгоритм работает с агрегированными состояниями мультимножества, а не с отдельными значениями.
بحسب التعريف الذي تتبعه هذه التطبيقات، فإن العدد «شديد الفردية» هو عدد صحيح موجب يقبل القسمة على \(105\)، وتظهر فيه كل واحدة من الأرقام الفردية الخمسة \(1,3,5,7,9\) عددًا موجبًا وفرديًا من المرات في التمثيل العشري. والمطلوب هو إيجاد العنصر رقم \(10^{16}\) من هذه الأعداد بعد ترتيبها تصاعديًا.
العدّ المباشر غير ممكن عمليًا. فحتى بعد تطبيق شروط القسمة تبقى كتل هائلة من التبديلات ذات الأرقام المكررة، كما أن الرتبة المطلوبة بعيدة جدًا عن أي أسلوب brute force. لذلك يعتمد الحل على متجهات العدّ، ويفصل شروط القسمة على \(3\) و\(5\) و\(7\)، ثم يعدّ ترتيبات متعددات المجموعات بحسب الباقي modulo \(7\)، وبعد ذلك يعيد بناء الجواب رقمًا رقمًا وفق الترتيب المعجمي.
قيمة أي مرشح تعتمد على طبقتين مختلفتين من المعلومات: عدد مرات ظهور كل رقم فردي، وترتيب هذه الأرقام داخل العدد. الفكرة الأساسية هي فصل هاتين الطبقتين ومعالجة كل واحدة بالطريقة المناسبة لها.
لطول ثابت \(L\)، نكتب
$$c=(c_1,c_3,c_5,c_7,c_9),$$
حيث يمثّل \(c_d\) عدد مرات ظهور الرقم \(d\). كل مركبة يجب أن تكون موجبة وفردية، ولذلك يمكن كتابتها على صورة \(c_d=2a_d+1\) مع \(a_d\ge 0\). وعندئذٍ
$$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$$
إذن كل طول صالح لا بد أن يكون فرديًا وألا يقل عن \(5\). وبالنسبة إلى طول ثابت، تصبح الخطوة الأولى هي توليد جميع متجهات العدّ الممكنة. وبما أن الصفر لا يظهر أصلًا بين الأرقام المسموح بها، فلا توجد حالة خاصة تتعلق بالأصفار البادئة؛ وعليه فإن الترتيب العددي يطابق الترتيب المعجمي داخل الطول نفسه.
بعد تثبيت متجه العدّ \(c\)، فإن القسمة على \(3\) تعتمد فقط على مجموع الأرقام:
$$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$$
ولا يمكن لأي ترتيب أن يغيّر هذا المجموع، ولذلك فهذا شرط ترشيح مبكر على المتجه نفسه.
أما القسمة على \(5\) فهي أشد تقييدًا، لأن الأرقام المسموح بها كلها فردية، وبالتالي لا بد أن تكون الخانة الأخيرة \(5\). لذا يلزم \(c_5\ge 1\)، وبعد حجز الرقم الأخير يبقى متعدد المجموعة الأقصر
$$c'=(c_1,c_3,c_5-1,c_7,c_9).$$
إذا كتبنا العدد كله على صورة \(10P+5\)، فإن شرط القسمة على \(7\) يصبح
$$10P+5\equiv 0 \pmod 7.$$
وبما أن \(10\equiv 3 \pmod 7\) ومعكوس \(3\) هو \(5\) modulo \(7\)، فهذا يكافئ
$$P\equiv 3 \pmod 7.$$
وهكذا ينحصر العدّ، لكل متجه صالح، في سؤال محدد جدًا: كم عدد الترتيبات المختلفة لمتعدد المجموعة \(c'\) التي تعطي باقيًا يساوي \(3\) modulo \(7\)؟
لكل حالة غير سالبة
$$u=(u_1,u_3,u_5,u_7,u_9),$$
نعرّف \(R_u[r]\) بأنه عدد السلاسل الرقمية المختلفة التي تستخدم هذه الأعداد بالضبط ويكون مقدارها مكافئًا لـ \(r\pmod 7\). والحالة الفارغة هي حالة الأساس:
$$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \quad (r\ne 0).$$
إذا كان طول الحالة الكلي هو \(m\)، ووضعنا الرقم \(d\) في أكثر خانة متبقية أهمية، فإن بقية الكتلة تنزاح بوزن \(10^{m-1}\). ومن هنا نحصل على الانتقال
$$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r].$$
هنا \(e_d\) يعني إنقاص نسخة واحدة من الرقم \(d\). أما الحفظ memoization فهو جوهري، لأن الحالة نفسها تظهر مرات كثيرة عند عدّ متجهات كلية مختلفة، ثم تعود للظهور أثناء حساب عدد الأذيال الممكنة في مرحلة إعادة البناء.
عند الطول \(5\)، سنضطر إلى استخدام الأرقام \(1,3,5,7,9\) مرة واحدة لكل منها. مجموع هذه الأرقام هو \(25\)، وهو غير قابل للقسمة على \(3\)، ولذلك لا يوجد أي عدد صالح بطول \(5\).
إذن أصغر طول ممكن هو \(7\). وللحصول على أصغر قيمة ممكنة نبدأ بالمتجه
$$c=(3,1,1,1,1),$$
أي ثلاث وحدات ونسخة واحدة من كل من \(3,5,7,9\). مجموع الأرقام يساوي
$$3\cdot 1+3+5+7+9=27,$$
ولذلك يمر شرط القسمة على \(3\). وبعد حجز الرقم الأخير \(5\) يبقى متعدد المجموعة \(\{1,1,1,3,7,9\}\). نحتاج إلى أن يحقق البادئ \(P\) الشرط \(P\equiv 3\pmod 7\). وبين الترتيبات المختلفة المرتبة ترتيبًا معجميًا، يكون أول ترتيب يحقق ذلك هو
$$P=111793.$$
ومن ثم يكون أصغر عدد شديد الفردية هو
$$1117935,$$
وهذا هو المثال الأول الذي تستعمله التطبيقات للتحقق من صحة المنهج.
بعد حساب عدد الأعداد الصالحة لكل طول فردي، نستطيع تحديد الكتلة الوحيدة التي تحتوي على الرتبة المطلوبة. وداخل هذه الكتلة يُبنى الجواب رقمًا بعد رقم.
لنفترض أن بادئة ما قد ثُبتت بالفعل، وأن \(\rho\) هو إسهام هذه البادئة modulo \(7\) داخل العدد الكامل ذي الطول \(L\). إذا رمزنا إلى الكتلة الوسطى غير المبنية بعد بالرمز \(S\)، فإن العدد غير المكتمل له الصورة
$$\rho + 10S + 5 \pmod 7.$$
ولذلك لا بد أن يحقق الذيل
$$10S\equiv -(\rho+5)\pmod 7,$$
أو بصورة مكافئة
$$S\equiv -(\rho+5)\cdot 5 \pmod 7.$$
لكل رقم مرشح في الخانة التالية، يطرح الكود الأرقام التي استُخدمت بالفعل من جميع متجهات العدّ الكلية الصالحة، ثم يسأل جدول DP عن عدد الأذيال التي تحقق الباقي المطلوب، ويجمع هذه الإكمالات. أول رقم يحتوي مجاله على الرتبة المتبقية يتم تثبيته. وبما أن التجربة تكون بترتيب \(1,3,5,7,9\) تصاعديًا، فإن العملية تطابق الاختيار المعجمي تمامًا.
تسير التطبيقات عبر الأطوال الفردية \(L=5,7,9,\dots\). ولكل طول، تُولَّد جميع متجهات العدّ ذات المركبات الفردية الموجبة التي مجموعها \(L\). المتجهات التي لا تحقق شرط مجموع الأرقام modulo \(3\) تُستبعد فورًا، كما أن أي متجه لا يحتوي على \(5\) مستحيل لأن الخانة الأخيرة ثابتة.
كل متجه يبقى بعد ذلك يساهم بعدد ترتيبات \(c'\) التي تعطي باقيًا \(3\) modulo \(7\). مجموع هذه الإسهامات هو حجم كتلة ذلك الطول كاملًا. في نسختي C++ وJava تُوزَّع هذه المرحلة على عدة مهام، بينما تطبق نسخة Python الحساب نفسه بصورة متسلسلة.
لبّ الحل هو مخزن مؤقت يحتفظ، لكل حالة متعدد مجموعة \(u\)، بجدول من سبع قيم يمثل كل منها واحدة من فئات الباقي modulo \(7\). والتحضير العددي الوحيد المطلوب مسبقًا هو قيم \(10^k \bmod 7\)، لأن كل انتقال في DP يعتمد على الوزن العشري للخانة التي توضع فيها الخانة الجديدة.
ويُعاد استخدام هذا المخزن المؤقت مرتين: مرة عند حساب مساهمة متجه عدّ كامل، ومرة أخرى عند السؤال عن عدد الأذيال القادرة على إكمال بادئة سبق تثبيتها.
عندما يُعرف الطول الهدف، تحتفظ البرامج بعدد النسخ المستخدمة من كل رقم وبإسهام البادئة الحالية modulo \(7\). وفي كل موضع قبل الخانة الأخيرة تُجرَّب الأرقام \(1,3,5,7,9\) بترتيب تصاعدي.
لكل مرشح، تُفحَص جميع متجهات العدّ الكلية الصالحة لذلك الطول: فإذا ظل المتجه منسجمًا مع البادئة المختارة ومع \(5\) الأخيرة المحجوزة، تحوّل البقية إلى حالة ذيل، ويعطي جدول DP عدد الأذيال التي تحقق الباقي المطلوب. إذا كان هذا المجموع أصغر من الرتبة المتبقية، تُتخطى الكتلة كاملة. وإلا يثبَّت الرقم المرشح وتُستكمل العملية. وفي النهاية تُضاف \(5\) الأخيرة.
لتكن \(M\) هي طول الجواب النهائي. بما أن أبجدية الأرقام ثابتة الحجم \(5\) وأن الموديل \(7\) ثابت أيضًا، فإن فضاء الحالات يتحدد بالكامل بواسطة متجهات العدّ. وعدد الحالات غير السالبة التي لا يتجاوز مجموعها \(M-1\) هو
$$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$$
ولذلك تحتاج جداول البواقي المحفوظة إلى \(O(M^5)\) حالة وإلى نفس الرتبة متعددة الحدود من العمل، مع عوامل ثابتة صغيرة ناتجة عن الخيارات الخمسة للأرقام والبواقي السبعة.
أما لِطول ثابت \(L\)، فإن العدد الخام لمتجهات العدّ الموجبة الفردية قبل تطبيق المرشحات هو
$$\binom{\frac{L-5}{2}+4}{4}.$$
وخلال إعادة البناء تُجرَّب في كل واحدة من أول \(L-1\) خانات بحد أقصى خمسة أرقام مرشحة، مع مسح المتجهات الصالحة لذلك الطول؛ لذا فالكلفة الإضافية تتناسب مع \(L\) مضروبًا في عدد المتجهات التي نجت من المرشحات. عمليًا هذا أصغر بكثير من تعداد الأعداد نفسها، لأن الخوارزمية تعمل على حالات مجمعة لمتعددات المجموعات بدلًا من الأعداد الفردية واحدة واحدة.