Call a positive integer heptaphobic if it is not divisible by 7 and it still stays non-divisible by 7 after every valid swap of two decimal digits. Swaps that would move 0 to the front are ignored, because they would not produce another number of the same length. The goal is to count all heptaphobic numbers below \(10^{13}\).
A direct test of every integer is hopeless. The implementations instead count numbers by length, fix the nonzero residue \(m=n\bmod 7\), and ask which digit patterns make it impossible for any admissible swap to force the residue to \(0\).
Take a length-\(L\) number with digits \(d_0,d_1,\dots,d_{L-1}\):
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
Modulo 7, only the positional weights matter, so define
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
Then \(n\bmod 7\) is simply \(\sum d_iw_i\bmod 7\). The whole method comes from understanding how a swap changes this residue and from compressing positions with the same weight.
If digits at positions \(i\) and \(j\) are exchanged, every other term is unchanged, so the residue changes by
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
Therefore a number with residue \(m\in\{1,\dots,6\}\) becomes divisible by 7 after that swap exactly when
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$$
This already shows why the code never needs the full decimal values of the digits. Only their residues modulo 7 matter.
Because \(10\equiv 3\pmod 7\) and \(10^6\equiv 1\pmod 7\), the powers of 10 repeat modulo 7 with period 6:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
So, for a fixed length \(L\), every non-leading position belongs to one of six weight classes. All positions in the same class have the same multiplier \(w_i\), and swapping two digits inside one class does nothing modulo 7 because then \(w_i-w_j\equiv 0\pmod 7\).
That means a whole class can be summarized by four facts:
the set of residues that occur there, the set of nonzero residues that occur there, the sum of the class digits modulo 7, and the number of ordered digit tuples that realize that same summary.
This compression is exactly what the problem needs. Pairwise swap safety depends only on which residues appear in each class, while the overall residue of the number depends only on the weighted class sums.
Take two different weight classes with weights \(a\) and \(b\), and suppose the whole number has residue \(m\). If one class contains a digit residue \(r\) and the other contains a residue \(s\), the swap between those positions is forbidden precisely when
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
Since \(a\not\equiv b\pmod 7\), the difference \(a-b\) has an inverse modulo 7. Define
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
Then the forbidden relation becomes
$$s\equiv r+t(a,b,m)\pmod 7.$$
So two class summaries are compatible exactly when the residue set of the first class, shifted by \(t(a,b,m)\), is disjoint from the residue set of the second class. That is the key simplification used by the implementations: every swap condition turns into a tiny 7-bit set-intersection test.
A concrete example helps. If \(m=5\), \(a=3\), and \(b=1\), then \(a-b\equiv 2\), its inverse is \(4\), and
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
So any residue \(r\) appearing in the weight-3 class forbids the residue \(r+1\pmod 7\) in the weight-1 class.
Swaps involving the first digit are asymmetric, because a later 0 cannot be moved to the front. Such a swap would create a leading zero and is excluded by the problem statement. For that reason the leading digit is handled separately, chosen from the residues of the digits \(1,\dots,9\), and compared with the other classes using only the nonzero residues present there.
There is also one important no-op case. If the leading weight reappears later in the number, then swapping with that position cannot change the residue at all, because the two weights are equal modulo 7. Since the original residue \(m\) is already nonzero, such swaps can never create a multiple of 7.
Fix the length \(L\), the target residue \(m\in\{1,\dots,6\}\), and the leading-digit residue \(r_0\). If the first position has weight \(w_0\), the remaining weight classes must contribute
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$$
where \(\sigma(C)\) is the stored digit-sum residue for class \(C\).
So the problem is now finite and discrete: choose one summary for each active weight class, keep every pair of chosen summaries compatible, and make the weighted sum land on the required residue. The implementations solve this with a depth-first search that always branches on the class with the fewest remaining summaries, which gives strong pruning.
For \(L=2\), the weights are \(3\) and \(1\), so a number \(10a+b\) has residue
$$m\equiv 3a+b\pmod 7.$$
The only possible digit swap produces \(10b+a\), and the residue change is
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
Take \(12\). Its residue is \(3\cdot 1+2\equiv 5\pmod 7\), but swapping gives \(21\equiv 0\pmod 7\), so \(12\) is not heptaphobic. By contrast, \(13\equiv 6\pmod 7\) and its swap \(31\equiv 3\pmod 7\), so that swap does not violate the rule. The full algorithm uses exactly this modular test, but it applies it class by class instead of number by number.
The C++, Python, and Java implementations first precompute three small constant tables: the six-term cycle of \(10^k\bmod 7\), the number of possible leading digits for each residue class, and the catalogue of summary types for a weight class of a given size. Each summary type records which residues appear, which nonzero residues appear, what the class contributes to the digit sum modulo 7, and how many ordered digit assignments produce that same summary.
For the actual bound \(10^{13}\), every non-leading weight class has size 0, 1, or 2, so these catalogues stay tiny: there is 1 summary of size 0, 8 summaries of size 1, and 35 summaries of size 2.
For a fixed length \(L\) and target residue \(m\), the implementation counts how many non-leading positions belong to each of the six weights. Every active class receives its list of possible summaries together with its weighted modular contribution. It also precomputes, for every ordered pair of distinct weight classes, which summaries can coexist without creating a forbidden swap.
Next, the leading-digit residue is chosen. That immediately removes any class summaries that would allow a forbidden nonzero swap with the front position. After that, a recursive search picks one summary for one class at a time, intersects the remaining candidate sets with the precomputed compatibility tables, updates the running residue sum, and multiplies by the number of concrete digit assignments represented by each chosen summary.
The result is summed over all nonzero residues \(m=1,\dots,6\) for a fixed length, and then over all lengths from 1 through 13. Small built-in checks on short ranges verify the logic before the final count below \(10^{13}\) is produced.
A brute-force approach would inspect almost \(10^{13}\) integers and, for each one, consider up to \(\binom{13}{2}\) digit swaps. The implemented method never iterates over concrete numbers at that scale.
For each pair \((L,m)\) with \(1\le L\le 13\) and \(m\in\{1,\dots,6\}\), there are at most six non-leading weight classes. Each class uses only a small precomputed summary catalogue, and for this bound no class has more than 35 relevant summaries. The search depth is therefore at most six, with heavy pruning from pairwise compatibility and the modular sum condition. Memory usage is \(O(1)\) relative to the numeric bound, because only small residue tables and candidate masks are stored.
In practice the running time is dominated by a modest branch-and-prune search across the \((L,m)\) cases, which is why the method is fast enough even though direct enumeration would be completely infeasible.
Eine positive ganze Zahl heißt hier heptaphob, wenn sie nicht durch 7 teilbar ist und auch nach jedem gültigen Tausch zweier Dezimalziffern nicht durch 7 teilbar wird. Tauschvorgänge, die vorne eine 0 erzeugen würden, werden ignoriert, weil sie keine Zahl derselben Länge liefern. Gesucht ist die Anzahl aller heptaphoben Zahlen unter \(10^{13}\).
Die Implementierungen prüfen die Zahlen nicht einzeln. Stattdessen wird nach Länge gezählt, der von 0 verschiedene Rest \(m=n\bmod 7\) fixiert und dann bestimmt, welche Ziffernmuster es unmöglich machen, dass ein zulässiger Tausch den Rest auf \(0\) bringt.
Betrachte eine Zahl der Länge \(L\) mit Ziffern \(d_0,d_1,\dots,d_{L-1}\):
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
Modulo 7 zählen nur die Positionsgewichte, also setzen wir
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
Dann ist \(n\bmod 7\) einfach \(\sum d_iw_i\bmod 7\). Die ganze Methode entsteht daraus, wie ein Tausch diesen Rest verändert und wie man Positionen mit gleichem Gewicht zusammenfasst.
Werden die Ziffern an den Positionen \(i\) und \(j\) vertauscht, bleiben alle anderen Terme gleich. Die Reständerung ist daher
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
Eine Zahl mit Rest \(m\in\{1,\dots,6\}\) wird also genau dann durch 7 teilbar, wenn nach dem Tausch
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7$$
gilt. Das zeigt sofort, warum der Code nur mit Ziffernresten modulo 7 arbeitet: die konkreten Dezimalwerte sind nicht mehr nötig.
Weil \(10\equiv 3\pmod 7\) und \(10^6\equiv 1\pmod 7\) gilt, wiederholen sich die Zehnerpotenzen modulo 7 mit Periode 6:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
Für eine feste Länge \(L\) gehört deshalb jede nichtführende Position zu einer von sechs Gewichtsklassen. Innerhalb einer Klasse haben alle Stellen denselben Multiplikator \(w_i\). Ein Tausch innerhalb derselben Klasse ändert modulo 7 nichts, weil dann \(w_i-w_j\equiv 0\pmod 7\).
Eine ganze Klasse lässt sich daher durch vier Daten beschreiben:
die Menge der vorkommenden Reste, die Menge der vorkommenden von 0 verschiedenen Reste, die Ziffernsumme der Klasse modulo 7 und die Anzahl geordneter Ziffernbelegungen, die genau dieselbe Zusammenfassung erzeugen.
Diese Verdichtung ist verlustfrei für das Problem. Die Tauschsicherheit zwischen zwei Klassen hängt nur davon ab, welche Reste in ihnen vorkommen, und der Gesamtrest der Zahl hängt nur von den gewichteten Klassensummen ab.
Betrachte zwei verschiedene Gewichtsklassen mit Gewichten \(a\) und \(b\), und sei der Gesamtrest der Zahl gleich \(m\). Wenn in der ersten Klasse ein Ziffernrest \(r\) und in der zweiten ein Rest \(s\) vorkommt, dann ist der Tausch genau dann verboten, wenn
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
Da \(a\not\equiv b\pmod 7\), ist \(a-b\) modulo 7 invertierbar. Setze
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
Dann wird die verbotene Beziehung zu
$$s\equiv r+t(a,b,m)\pmod 7.$$
Zwei Klassenzusammenfassungen sind also genau dann verträglich, wenn die um \(t(a,b,m)\) verschobene Restmenge der ersten Klasse disjunkt zur Restmenge der zweiten Klasse ist. Darum lassen sich alle Tauschbedingungen auf winzige 7-Bit-Schnittmengentests reduzieren.
Ein konkretes Beispiel: Für \(m=5\), \(a=3\) und \(b=1\) ist \(a-b\equiv 2\), dessen Inverses ist \(4\), also
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
Damit verbietet jeder Rest \(r\) in der Gewichtsklasse 3 den Rest \(r+1\pmod 7\) in der Gewichtsklasse 1.
Tauschvorgänge mit der ersten Ziffer sind asymmetrisch, denn eine spätere 0 darf nicht nach vorne geholt werden. Ein solcher Tausch würde eine führende Null erzeugen und ist laut Aufgabenstellung ungültig. Deshalb wird die führende Ziffer separat behandelt, aus den Resten der Ziffern \(1,\dots,9\) gewählt und mit den anderen Klassen nur über die dort vorkommenden von 0 verschiedenen Reste verglichen.
Außerdem gibt es einen wichtigen harmlosen Fall. Wenn das führende Gewicht später noch einmal vorkommt, kann ein Tausch mit dieser Stelle den Rest gar nicht ändern, weil beide Gewichte modulo 7 gleich sind. Ein bereits von 0 verschiedener Rest \(m\) kann dadurch also nie zu \(0\) werden.
Fixiere die Länge \(L\), den Zielrest \(m\in\{1,\dots,6\}\) und den Rest \(r_0\) der führenden Ziffer. Hat die erste Stelle das Gewicht \(w_0\), dann müssen die übrigen Gewichtsklassen zusammen
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7$$
beitragen, wobei \(\sigma(C)\) den gespeicherten Ziffernsummenrest der Klasse \(C\) bezeichnet.
Damit wird das Problem endlich und diskret: Für jede aktive Gewichtsklasse ist genau eine Zusammenfassung zu wählen, jedes gewählte Paar muss verträglich sein, und die gewichtete Summe muss auf dem geforderten Rest landen. Die Implementierungen lösen das mit einer Tiefensuche, die stets mit der Klasse mit den wenigsten verbleibenden Möglichkeiten verzweigt.
Für \(L=2\) sind die Gewichte \(3\) und \(1\), also hat eine Zahl \(10a+b\) den Rest
$$m\equiv 3a+b\pmod 7.$$
Der einzige mögliche Zifferntausch liefert \(10b+a\), und die Reständerung ist
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
Nimm \(12\). Der Rest ist \(3\cdot 1+2\equiv 5\pmod 7\), aber der Tausch ergibt \(21\equiv 0\pmod 7\), also ist \(12\) nicht heptaphob. Dagegen gilt \(13\equiv 6\pmod 7\) und \(31\equiv 3\pmod 7\), dieser Tausch verletzt die Bedingung also nicht. Der volle Algorithmus benutzt genau denselben Modularitätstest, nur eben klassenweise statt zahlweise.
Die C++-, Python- und Java-Implementierungen berechnen zuerst drei kleine Konstantentabellen vor: den 6-Zyklus von \(10^k\bmod 7\), die Anzahl möglicher führender Ziffern in jeder Restklasse und den Katalog aller Zusammenfassungstypen für eine Gewichtsklasse gegebener Größe. Jeder Typ speichert die vorkommenden Reste, die vorkommenden von 0 verschiedenen Reste, den Beitrag der Klasse zur Ziffernsumme modulo 7 und die Anzahl geordneter Ziffernbelegungen mit genau dieser Zusammenfassung.
Für die Schranke \(10^{13}\) hat jede nichtführende Gewichtsklasse nur die Größe 0, 1 oder 2. Entsprechend bleiben die Kataloge klein: 1 Zusammenfassung für Größe 0, 8 für Größe 1 und 35 für Größe 2.
Für feste Länge \(L\) und festen Zielrest \(m\) zählt die Implementierung zunächst, wie viele nichtführende Positionen zu jedem der sechs Gewichte gehören. Jede aktive Klasse erhält ihre Liste zulässiger Zusammenfassungen mitsamt dem gewichteten modularen Beitrag. Zusätzlich wird für jedes geordnete Paar verschiedener Gewichtsklassen vorab bestimmt, welche Zusammenfassungen gemeinsam auftreten dürfen, ohne einen verbotenen Tausch zu erzeugen.
Danach wird der Rest der führenden Ziffer gewählt. Dadurch fallen sofort alle Zusammenfassungen weg, die einen verbotenen von 0 verschiedenen Tausch mit der Frontposition zulassen würden. Anschließend wählt eine rekursive Suche schrittweise je eine Zusammenfassung pro Klasse, schneidet die verbleibenden Kandidatenmengen mit den vorberechneten Verträglichkeitstabellen zu, aktualisiert die laufende Restsumme und multipliziert mit der Anzahl konkreter Ziffernbelegungen, die durch die gewählten Zusammenfassungen repräsentiert werden.
Das Ergebnis wird für jede Länge über alle von 0 verschiedenen Reste \(m=1,\dots,6\) summiert und danach über alle Längen von 1 bis 13 addiert. Kleine eingebaute Tests auf kurzen Bereichen prüfen die Logik, bevor die endgültige Anzahl unter \(10^{13}\) berechnet wird.
Eine brute-force-Lösung müsste fast \(10^{13}\) Zahlen inspizieren und für jede bis zu \(\binom{13}{2}\) Zifferntäusche betrachten. Die implementierte Methode iteriert auf dieser Ebene überhaupt nicht über konkrete Zahlen.
Für jedes Paar \((L,m)\) mit \(1\le L\le 13\) und \(m\in\{1,\dots,6\}\) gibt es höchstens sechs nichtführende Gewichtsklassen. Jede Klasse verwendet nur einen kleinen vorberechneten Zusammenfassungskatalog, und unter dieser Schranke hat keine Klasse mehr als 35 relevante Zusammenfassungen. Die Suchtiefe ist also höchstens sechs, bei starker Prüfung durch Paarverträglichkeiten und die modulare Summenbedingung. Der Speicherbedarf ist relativ zur Zahlenschranke \(O(1)\), weil nur kleine Resttabellen und Kandidatenmasken gespeichert werden.
Praktisch dominiert deshalb eine recht kleine Branch-and-Prune-Suche über die verschiedenen \((L,m)\)-Fälle. Genau das macht das Verfahren schnell genug, obwohl direkte Enumeration vollkommen aussichtslos wäre.
Bir pozitif tam sayıya burada heptaphobic diyelim: sayı hem 7'ye bölünmeyecek hem de ondalık basamaklarından herhangi iki tanesi geçerli şekilde yer değiştirildiğinde yine 7'ye bölünmeyecek. Başa 0 getiren takaslar dikkate alınmaz; çünkü aynı uzunlukta başka bir sayı oluşturmazlar. Amaç, \(10^{13}\)'ten küçük tüm heptaphobic sayıları saymaktır.
Doğrudan her sayıyı denemek imkansızdır. Uygulamalar bunun yerine sayıları uzunluklarına göre sayar, sıfırdan farklı kalanı \(m=n\bmod 7\) sabitler ve hangi basamak desenlerinin herhangi bir geçerli takasla kalanı \(0\)'a indirmeyi imkansız hale getirdiğini araştırır.
Uzunluğu \(L\) olan ve basamakları \(d_0,d_1,\dots,d_{L-1}\) olan bir sayı alalım:
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
Mod 7 altında yalnızca konumsal ağırlıklar önemli olduğundan
$$w_i\equiv 10^{L-1-i}\pmod 7$$
tanımını yapalım. O zaman \(n\bmod 7\), yalnızca \(\sum d_iw_i\bmod 7\) olur. Bütün yöntem, bir takasın bu kalanı nasıl değiştirdiğini ve aynı ağırlığa sahip konumların nasıl tek bir sınıfta toplanabildiğini anlamaya dayanır.
\(i\) ve \(j\) konumlarındaki basamaklar yer değiştirince diğer tüm terimler sabit kalır. Bu nedenle kalan değişimi
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7$$
olur. Dolayısıyla kalanı \(m\in\{1,\dots,6\}\) olan bir sayı, o takastan sonra ancak
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7$$
ise 7'ye bölünür. Bu formül, kodun neden tam ondalık rakamlarla değil yalnızca rakamların mod 7 kalıntılarıyla çalıştığını da açıklar.
Çünkü \(10\equiv 3\pmod 7\) ve \(10^6\equiv 1\pmod 7\), 10'un kuvvetleri mod 7 altında 6 periyotla tekrar eder:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
Bu yüzden sabit bir \(L\) uzunluğu için ilk basamak dışındaki her konum altı ağırlık sınıfından birine düşer. Aynı sınıftaki tüm konumların çarpanı aynıdır; dolayısıyla aynı sınıf içindeki bir takas mod 7'yi hiç değiştirmez, çünkü \(w_i-w_j\equiv 0\pmod 7\).
Bu da bir sınıfı dört bilgiyle özetlemeyi mümkün kılar:
o sınıfta görülen kalanların kümesi, sıfır olmayan kalanların kümesi, sınıftaki basamakların toplamının mod 7 kalanı ve aynı özeti veren sıralı basamak dizilerinin sayısı.
Bu sıkıştırma problem için kayıpsızdır. İki sınıf arasındaki takas güvenliği yalnızca hangi kalıntıların görüldüğüne bağlıdır; sayının toplam kalanıysa yalnızca ağırlıklı sınıf toplamlarına bağlıdır.
Ağırlıkları \(a\) ve \(b\) olan iki farklı sınıf alalım; sayının toplam kalanı da \(m\) olsun. İlk sınıfta \(r\), ikinci sınıfta \(s\) kalıntılı bir rakam varsa, bu ikisinin takası ancak
$$m+(s-r)(a-b)\equiv 0\pmod 7$$
ise yasaktır. \(a\not\equiv b\pmod 7\) olduğundan \(a-b\)'nin mod 7 altında tersi vardır. Şu kaydırmayı tanımlayalım:
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
O zaman yasak ilişki
$$s\equiv r+t(a,b,m)\pmod 7$$
biçimine iner. Yani iki sınıf özeti, ancak birinci sınıfın artık kümesi \(t(a,b,m)\) kadar döndürüldüğünde ikinci sınıfın artık kümesiyle kesişmiyorsa uyumludur. Uygulamaların yaptığı temel hızlandırma tam olarak budur: bütün tek tek takas kontrolleri, 7 bitlik küçük küme kesişimlerine indirgenir.
Küçük bir örnek: \(m=5\), \(a=3\), \(b=1\) için \(a-b\equiv 2\) ve bunun tersi \(4\)'tür. Dolayısıyla
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
Demek ki ağırlığı 3 olan sınıfta görülen her \(r\) kalıntısı, ağırlığı 1 olan sınıfta \(r+1\pmod 7\) kalıntısını yasaklar.
İlk basamakla ilgili takaslar asimetriktir; çünkü daha sonra gelen bir 0 başa getirilemez. Böyle bir takas başta sıfır oluşturur ve problem tanımına göre geçersizdir. Bu nedenle ilk basamak ayrı seçilir, \(1,\dots,9\) rakamlarının kalıntılarından gelir ve diğer sınıflarla karşılaştırılırken yalnızca o sınıflarda bulunan sıfır olmayan kalıntılar dikkate alınır.
Bir de zararsız durum vardır: ilk basamağın ağırlığı daha sonra tekrar ediyorsa, o konumlarla yapılan takaslar kalanı hiç değiştiremez; çünkü iki ağırlık mod 7 altında aynıdır. Başlangıçta \(m\neq 0\) olduğundan böyle bir takas sayıyı 7'ye tam bölünebilir hale getiremez.
Uzunluğu \(L\), hedef kalanı \(m\in\{1,\dots,6\}\) ve ilk basamağın kalanı \(r_0\) sabit olsun. İlk konumun ağırlığı \(w_0\) ise geri kalan sınıfların toplam katkısı
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7$$
olmalıdır; burada \(\sigma(C)\), sınıf \(C\) için saklanan basamak-toplamı kalıntısıdır.
Böylece problem sonlu bir arama problemine dönüşür: her etkin ağırlık sınıfı için bir özet seç, seçilen her çift uyumlu olsun ve ağırlıklı toplam istenen kalana gelsin. Uygulamalar bunu, her adımda elde en az seçenek kalan sınıfı seçerek ilerleyen bir derinlik-öncelikli aramayla yapar.
\(L=2\) için ağırlıklar \(3\) ve \(1\)'dir; dolayısıyla \(10a+b\) sayısının kalanı
$$m\equiv 3a+b\pmod 7$$
olur. Tek mümkün takas \(10b+a\) sayısını verir ve kalan değişimi
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7$$
şeklindedir. Örneğin \(12\) için \(3\cdot 1+2\equiv 5\pmod 7\), fakat takas sonrası \(21\equiv 0\pmod 7\), yani \(12\) heptaphobic değildir. Buna karşılık \(13\equiv 6\pmod 7\) ve takas edilmiş hali \(31\equiv 3\pmod 7\) olur; bu takas bir sorun oluşturmaz. Tam algoritma da aynı modüler testi kullanır, fakat bunu tek tek sayılar yerine sınıf özetleri üzerinde yapar.
C++, Python ve Java uygulamaları önce üç sabit tablo hazırlar: \(10^k\bmod 7\)'nin 6 terimli döngüsü, her artık sınıfı için olası ilk basamak sayısı ve belli büyüklükteki bir ağırlık sınıfı için bütün özet tipleri. Her özet tipi, hangi kalıntıların görüldüğünü, hangi sıfır olmayan kalıntıların görüldüğünü, o sınıfın mod 7 altında basamak-toplamı katkısını ve aynı özeti veren sıralı basamak atamalarının kaç tane olduğunu saklar.
\(10^{13}\) sınırı için ilk basamak dışındaki her ağırlık sınıfının boyutu 0, 1 ya da 2'dir. Bu nedenle özet katalogları küçük kalır: boyut 0 için 1, boyut 1 için 8, boyut 2 için 35 olası özet vardır.
Sabit bir \(L\) uzunluğu ve \(m\) hedef kalanı için uygulama, ilk basamak dışındaki konumların altı ağırlığa nasıl dağıldığını sayar. Her etkin sınıfa, mümkün özetlerinin listesi ve her özetin ağırlıklı modüler katkısı atanır. Ayrıca farklı iki ağırlık sınıfının özetlerinin, yasak bir takas oluşturmadan birlikte bulunup bulunamayacağı da önceden tablo haline getirilir.
Daha sonra ilk basamağın kalanı seçilir. Bu seçim, baştaki konumla yasak bir sıfır olmayan takasa izin veren tüm sınıf özetlerini hemen eler. Kalan adaylar üzerinde özyineli arama yapılır: her adımda bir sınıf için bir özet seçilir, diğer sınıfların aday kümeleri hazır uyumluluk tablolarıyla daraltılır, geçerli modüler toplam güncellenir ve seçilen özetlerin temsil ettiği somut basamak atamalarının sayılarıyla çarpılır.
Elde edilen sonuç önce sabit bir uzunluk için tüm sıfır olmayan kalıntılar \(m=1,\dots,6\) üzerinde, sonra da 1'den 13'e kadar tüm uzunluklar üzerinde toplanır. Nihai \(10^{13}\) altı sayımı üretilmeden önce kısa aralıklarda yerleşik doğrulamalar yapılır.
Kaba kuvvet yaklaşımı yaklaşık \(10^{13}\) tam sayıyı dolaşmak ve her biri için en fazla \(\binom{13}{2}\) takası denemek zorunda kalırdı. Buradaki yöntem bu ölçekte hiçbir zaman somut sayıları tek tek gezmez.
\(1\le L\le 13\) ve \(m\in\{1,\dots,6\}\) için her \((L,m)\) çiftinde en fazla altı adet ilk-basamak-dışı ağırlık sınıfı vardır. Her sınıf yalnızca küçük bir ön hesaplı özet kataloğu kullanır ve bu sınır altında hiçbir sınıfta 35'ten fazla ilgili özet yoktur. Dolayısıyla arama derinliği en fazla altıdır; ikili uyumluluk kısıtları ve modüler toplam koşulu da yoğun budama sağlar. Sayısal sınıra göre bellek kullanımı \(O(1)\)'dir; çünkü yalnızca küçük artık tabloları ve aday maskeleri tutulur.
Pratikte çalışma süresine, farklı \((L,m)\) durumları üzerindeki küçük bir dal-buda araması hakimdir. Bu da doğrudan taramanın umutsuz olduğu yerde yöntemi yeterince hızlı yapar.
Llamemos heptafóbico a un entero positivo que no es divisible por 7 y que sigue sin ser divisible por 7 después de cualquier intercambio válido de dos dígitos decimales. Se ignoran los intercambios que pondrían un 0 al principio, porque ya no representarían otro número de la misma longitud. El objetivo es contar todos los números heptafóbicos menores que \(10^{13}\).
Las implementaciones no prueban los enteros uno por uno. En lugar de eso cuentan por longitud, fijan el residuo no nulo \(m=n\bmod 7\) y preguntan qué patrones de dígitos hacen imposible que un intercambio admisible fuerce el residuo a \(0\).
Tomemos un número de longitud \(L\) con dígitos \(d_0,d_1,\dots,d_{L-1}\):
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
Módulo 7 solo importan los pesos posicionales, así que definimos
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
Entonces \(n\bmod 7\) no es más que \(\sum d_iw_i\bmod 7\). Todo el método nace de entender cómo cambia este residuo cuando se intercambian dos dígitos y de agrupar las posiciones que tienen el mismo peso.
Si se permutan los dígitos en las posiciones \(i\) y \(j\), todos los demás términos permanecen iguales. Por tanto, el cambio de residuo es
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
Así, un número con residuo \(m\in\{1,\dots,6\}\) se vuelve divisible por 7 después de ese intercambio exactamente cuando
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$$
Esto explica por qué el código nunca necesita los dígitos decimales completos: basta con sus residuos módulo 7.
Como \(10\equiv 3\pmod 7\) y \(10^6\equiv 1\pmod 7\), las potencias de 10 se repiten módulo 7 con periodo 6:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
Por eso, para una longitud fija \(L\), toda posición no inicial pertenece a una de seis clases de peso. Dentro de una misma clase todas las posiciones tienen el mismo multiplicador \(w_i\), y un intercambio interno a la clase no altera el residuo porque entonces \(w_i-w_j\equiv 0\pmod 7\).
Una clase completa puede resumirse con cuatro datos:
el conjunto de residuos que aparecen, el conjunto de residuos no nulos que aparecen, la suma de los dígitos de la clase módulo 7 y el número de tuplas ordenadas de dígitos que producen exactamente ese mismo resumen.
Esta compresión es suficiente y exacta. La seguridad frente a intercambios entre dos clases depende solo de qué residuos aparecen en ellas, mientras que el residuo total del número depende solo de las sumas ponderadas de las clases.
Tomemos dos clases de peso distintas, con pesos \(a\) y \(b\), y supongamos que el número completo tiene residuo \(m\). Si una clase contiene un residuo de dígito \(r\) y la otra contiene un residuo \(s\), el intercambio entre esas posiciones está prohibido exactamente cuando
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
Como \(a\not\equiv b\pmod 7\), la diferencia \(a-b\) es invertible módulo 7. Definimos
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
Entonces la relación prohibida pasa a ser
$$s\equiv r+t(a,b,m)\pmod 7.$$
Por lo tanto, dos resúmenes de clase son compatibles exactamente cuando el conjunto de residuos de la primera clase, desplazado por \(t(a,b,m)\), es disjunto del conjunto de residuos de la segunda. Esa es la reducción esencial de la implementación: todas las comprobaciones de intercambio se convierten en pequeñas intersecciones de conjuntos de 7 bits.
Un ejemplo concreto: si \(m=5\), \(a=3\) y \(b=1\), entonces \(a-b\equiv 2\), su inverso es \(4\) y
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
Así, cualquier residuo \(r\) presente en la clase de peso 3 prohíbe el residuo \(r+1\pmod 7\) en la clase de peso 1.
Los intercambios que involucran el primer dígito son asimétricos, porque un 0 posterior no puede moverse al frente. Ese intercambio crearía un cero inicial y queda excluido por el enunciado. Por eso el primer dígito se trata por separado, se elige entre los residuos de \(1,\dots,9\) y, al compararlo con otra clase, solo se consideran los residuos no nulos presentes en esa clase.
Hay además un caso inocuo importante. Si el peso de la primera posición reaparece más adelante, intercambiar con esa posición no puede cambiar el residuo en absoluto, porque ambos pesos son iguales módulo 7. Como el residuo inicial \(m\) ya es no nulo, ese intercambio nunca puede producir divisibilidad por 7.
Fijemos la longitud \(L\), el residuo objetivo \(m\in\{1,\dots,6\}\) y el residuo \(r_0\) del primer dígito. Si la primera posición tiene peso \(w_0\), las clases restantes deben aportar
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$$
donde \(\sigma(C)\) es el residuo almacenado de la suma de dígitos de la clase \(C\).
Así, el problema pasa a ser finito y discreto: elegir un resumen para cada clase activa, exigir compatibilidad entre cada par elegido y hacer que la suma ponderada caiga en el residuo deseado. Las implementaciones lo resuelven con una búsqueda en profundidad que siempre ramifica en la clase con menos resúmenes supervivientes.
Para \(L=2\), los pesos son \(3\) y \(1\), de modo que un número \(10a+b\) tiene residuo
$$m\equiv 3a+b\pmod 7.$$
El único intercambio posible produce \(10b+a\), y el cambio de residuo es
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
Tomemos \(12\). Su residuo es \(3\cdot 1+2\equiv 5\pmod 7\), pero al intercambiar obtenemos \(21\equiv 0\pmod 7\), luego \(12\) no es heptafóbico. En cambio, \(13\equiv 6\pmod 7\) y su intercambio \(31\equiv 3\pmod 7\), así que ese intercambio no viola la regla. El algoritmo completo aplica este mismo criterio modular, pero por clases de peso en lugar de números individuales.
Las implementaciones en C++, Python y Java precalculan primero tres tablas pequeñas: el ciclo de seis términos de \(10^k\bmod 7\), cuántos dígitos iniciales posibles hay en cada clase de residuo y el catálogo de tipos de resumen para una clase de peso de tamaño dado. Cada tipo de resumen guarda qué residuos aparecen, qué residuos no nulos aparecen, cuál es la contribución de la clase a la suma de dígitos módulo 7 y cuántas asignaciones ordenadas de dígitos producen exactamente ese mismo resumen.
Para la cota \(10^{13}\), cada clase de peso no inicial tiene tamaño 0, 1 o 2. Por eso los catálogos siguen siendo pequeños: hay 1 resumen de tamaño 0, 8 de tamaño 1 y 35 de tamaño 2.
Para una longitud fija \(L\) y un residuo objetivo \(m\), la implementación cuenta cuántas posiciones no iniciales pertenecen a cada uno de los seis pesos. A cada clase activa se le asocia su lista de resúmenes posibles junto con su contribución modular ponderada. Además, para cada par ordenado de clases de peso distintas, se precalcula qué resúmenes pueden coexistir sin crear un intercambio prohibido.
Después se elige el residuo del dígito inicial. Eso elimina inmediatamente todos los resúmenes de clase que permitirían un intercambio no nulo prohibido con la primera posición. Sobre los candidatos restantes, una búsqueda recursiva escoge una clase cada vez, intersecta los conjuntos de candidatos con las tablas de compatibilidad ya preparadas, actualiza la suma modular acumulada y multiplica por el número de asignaciones concretas de dígitos representadas por los resúmenes elegidos.
El resultado se suma, para una longitud fija, sobre todos los residuos no nulos \(m=1,\dots,6\), y luego sobre todas las longitudes desde 1 hasta 13. Antes de producir el conteo final bajo \(10^{13}\), se incluyen comprobaciones internas en rangos pequeños para validar la lógica.
Un enfoque de fuerza bruta tendría que revisar casi \(10^{13}\) enteros y, para cada uno, considerar hasta \(\binom{13}{2}\) intercambios de dígitos. El método implementado nunca itera sobre números concretos a esa escala.
Para cada par \((L,m)\) con \(1\le L\le 13\) y \(m\in\{1,\dots,6\}\), hay como mucho seis clases de peso no iniciales. Cada clase usa solo un catálogo pequeño de resúmenes precalculados, y bajo esta cota ninguna clase tiene más de 35 resúmenes relevantes. La profundidad de la búsqueda es, por tanto, como mucho seis, con una poda fuerte debida a la compatibilidad por pares y a la restricción de suma modular. El uso de memoria es \(O(1)\) respecto del límite numérico, porque solo se almacenan tablas pequeñas de residuos y máscaras de candidatos.
En la práctica, el tiempo de ejecución lo domina una búsqueda branch-and-prune bastante pequeña sobre los casos \((L,m)\). Por eso el método es rápido aunque la enumeración directa sea inviable.
这里把一个正整数称为 heptaphobic：它本身不能被 7 整除，而且把任意两个十进制数字做一次合法交换之后，结果仍然不能被 7 整除。若交换会把 0 换到首位，则该交换不算合法，因为那已经不是同样位数的数。题目要求统计所有小于 \(10^{13}\) 的 heptaphobic 数。
实现并不是逐个检查整数，而是按位数分类计数，固定非零余数 \(m=n\bmod 7\)，再判断哪些数字模式能够保证任何允许的交换都不可能把余数变成 \(0\)。
设一个长度为 \(L\) 的数的各位数字为 \(d_0,d_1,\dots,d_{L-1}\)，则
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
在模 7 意义下，真正起作用的是各个位置的权重，因此定义
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
这样 \(n\bmod 7\) 就是 \(\sum d_iw_i\bmod 7\)。整套方法的核心有两点：交换两位时余数如何变化，以及如何把权重相同的位置压缩成同一类。
如果交换第 \(i\) 位和第 \(j\) 位，其余项完全不变，因此余数的变化量为
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
于是一个余数为 \(m\in\{1,\dots,6\}\) 的数，在交换后恰好会变成 7 的倍数，当且仅当
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$$
这一步已经说明了为什么实现只需要关心数字对 7 的余数，而不必关心完整的十进制数值。
因为 \(10\equiv 3\pmod 7\)，且 \(10^6\equiv 1\pmod 7\)，所以 10 的幂在模 7 下以 6 为周期循环：
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
因此，对固定长度 \(L\) 而言，除首位之外的每个位置都属于六个权重类之一。处在同一类中的位置拥有相同的乘子 \(w_i\)，而同类内部交换不会改变模 7 余数，因为这时 \(w_i-w_j\equiv 0\pmod 7\)。
所以整类位置可以压缩成四个信息：
该类中出现过哪些余数，该类中出现过哪些非零余数，该类所有数字之和对 7 的余数，以及能产生这一摘要的有序数字赋值个数。
这种压缩对本题是无损的。类与类之间的交换是否危险，只取决于各类里出现了哪些余数；整个数字的总余数，则只取决于各类的加权和。
取两个不同的权重类，它们的权重分别是 \(a\) 和 \(b\)，并假设整个数的余数是 \(m\)。如果前一类里有一个数字余数 \(r\)，后一类里有一个数字余数 \(s\)，那么这两个位置之间的交换会被禁止，当且仅当
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
由于 \(a\not\equiv b\pmod 7\)，差值 \(a-b\) 在模 7 下可逆。定义
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
那么禁用关系就变成了
$$s\equiv r+t(a,b,m)\pmod 7.$$
也就是说，当把第一类的余数集合整体平移 \(t(a,b,m)\) 之后，它必须与第二类的余数集合没有交集，这两个类摘要才是兼容的。这正是实现中的关键化简：所有交换限制都能变成一个很小的 7 位集合相交测试。
举个具体例子。若 \(m=5\)、\(a=3\)、\(b=1\)，则 \(a-b\equiv 2\)，它在模 7 下的逆元是 \(4\)，因此
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
所以，只要权重为 3 的那一类里出现余数 \(r\)，权重为 1 的那一类里就不能出现余数 \(r+1\pmod 7\)。
涉及首位的交换是非对称的，因为后面的 0 不能换到最前面。那样会产生前导零，按照题意这种交换根本不算有效。因此，首位数字必须单独选择，只能来自 \(1,\dots,9\) 的余数类别；当它与其他权重类比较时，只需要检查那些类中出现的非零余数。
还有一个重要的“无需约束”情形。如果首位的权重在后面再次出现，那么和那些位置交换根本不会改变余数，因为两个位置的权重模 7 相同。既然原始余数 \(m\) 已经不是 0，这类交换自然不可能把它变成 0。
固定长度 \(L\)、目标余数 \(m\in\{1,\dots,6\}\) 以及首位数字的余数 \(r_0\)。如果首位的权重是 \(w_0\)，那么其余各类必须满足
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$$
其中 \(\sigma(C)\) 表示类 \(C\) 保存的数字和余数。
这样一来，问题就被离散化了：对每个有效权重类选择一个摘要，要求任意两类之间都兼容，而且加权和恰好落在目标余数上。实现使用深度优先搜索来完成这一步，并且总是优先处理当前剩余候选摘要最少的那一类，从而获得很强的剪枝效果。
当 \(L=2\) 时，两个位置的权重分别是 \(3\) 和 \(1\)，因此数字 \(10a+b\) 的余数为
$$m\equiv 3a+b\pmod 7.$$
唯一可能的交换会得到 \(10b+a\)，其余数变化量为
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
例如 \(12\) 的余数是 \(3\cdot 1+2\equiv 5\pmod 7\)，但交换后得到 \(21\equiv 0\pmod 7\)，所以 \(12\) 不是 heptaphobic。相反，\(13\equiv 6\pmod 7\)，交换后 \(31\equiv 3\pmod 7\)，这个交换没有问题。完整算法做的正是同样的模运算判断，只不过它是在权重类摘要层面同时处理大量数字，而不是逐个枚举。
C++、Python 和 Java 实现首先预计算三类很小的常数表：\(10^k\bmod 7\) 的六项循环、每个余数类对应的首位可选数字个数，以及不同大小的权重类可能出现的全部摘要类型。每种摘要都记录：出现了哪些余数、出现了哪些非零余数、该类数字和对 7 的余数，以及能产生该摘要的有序数字赋值个数。
对 \(10^{13}\) 这个上界来说，每个非首位权重类的大小只可能是 0、1 或 2，所以摘要目录非常小：大小为 0 时有 1 种摘要，大小为 1 时有 8 种，大小为 2 时有 35 种。
固定长度 \(L\) 和目标余数 \(m\) 后，实现会先统计除首位以外的各个位置分别属于六个权重中的哪一个。每个有效权重类都会得到自己的摘要列表，以及每个摘要对应的加权模 7 贡献。同时，对于每一对不同的权重类，还会预先算出哪些摘要可以同时出现而不会形成禁用交换。
接着选择首位数字的余数。这个选择会立刻删除所有会与首位形成禁用非零交换的类摘要。随后，递归搜索逐类选择摘要，用预先算好的兼容表不断收缩其他类的候选集合，更新当前的模 7 累积和，并乘上所选摘要所代表的具体数字赋值数量。
对固定长度，要把所有非零余数 \(m=1,\dots,6\) 的结果加起来；然后再对 1 到 13 位的所有长度求和。实现会先在较小范围上做内置校验，再给出小于 \(10^{13}\) 的最终计数。
如果用暴力法，就必须检查将近 \(10^{13}\) 个整数，而且对每个整数都可能要测试最多 \(\binom{13}{2}\) 次数字交换。这里的实现完全避免了这种规模上的逐数遍历。
对每个 \((L,m)\) 组合，其中 \(1\le L\le 13\) 且 \(m\in\{1,\dots,6\}\)，除首位外最多只有六个权重类。每个权重类只会使用一个很小的预计算摘要目录；在本题范围内，一个类最多只会有 35 个相关摘要。因此搜索深度最多为六，而且还会受到成对兼容性约束和模和约束的强力剪枝。相对于数值上界，内存开销是 \(O(1)\)，因为只保存了很小的余数表和候选掩码。
在实际运行中，耗时主要来自针对各个 \((L,m)\) 情况的一个不大的 branch-and-prune 搜索。这就是为什么该方法足以处理 \(10^{13}\)，而直接枚举却完全不可行。
Назовем положительное целое число heptaphobic, если оно само не делится на 7 и после любого допустимого обмена двух десятичных цифр тоже не делится на 7. Обмены, которые ставят 0 в начало записи, не учитываются, потому что тогда получается уже не число той же длины. Нужно посчитать все heptaphobic-числа меньше \(10^{13}\).
Реализации не проверяют числа по одному. Вместо этого они считают по длинам, фиксируют ненулевой остаток \(m=n\bmod 7\) и определяют, какие шаблоны цифр гарантируют, что ни один допустимый обмен не сможет перевести остаток в \(0\).
Рассмотрим число длины \(L\) с цифрами \(d_0,d_1,\dots,d_{L-1}\):
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
По модулю 7 важны только позиционные веса, поэтому введем
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
Тогда \(n\bmod 7\) равно просто \(\sum d_iw_i\bmod 7\). Вся идея решения строится на том, как обмен двух цифр меняет этот остаток, и как объединить позиции с одинаковым весом.
Если поменять местами цифры в позициях \(i\) и \(j\), все остальные слагаемые останутся прежними. Поэтому изменение остатка равно
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
Следовательно, число с остатком \(m\in\{1,\dots,6\}\) превратится после такого обмена в число, делящееся на 7, тогда и только тогда, когда
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$$
Отсюда сразу видно, почему в коде достаточно работать только с остатками цифр по модулю 7, а не с самими десятичными значениями.
Так как \(10\equiv 3\pmod 7\) и \(10^6\equiv 1\pmod 7\), степени 10 по модулю 7 повторяются с периодом 6:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
Значит, при фиксированной длине \(L\) каждая неведущая позиция попадает в один из шести классов весов. Все позиции внутри одного класса имеют одинаковый множитель \(w_i\), а обмен двух цифр внутри класса ничего не меняет по модулю 7, потому что тогда \(w_i-w_j\equiv 0\pmod 7\).
Целый класс можно сжать до четырех характеристик:
какие остатки в нем встречаются, какие ненулевые остатки в нем встречаются, какова сумма цифр класса по модулю 7 и сколько упорядоченных наборов цифр дают ровно такое же описание.
Это сжатие не теряет нужной информации. Безопасность обменов между двумя классами зависит только от того, какие остатки в них присутствуют, а общий остаток числа зависит только от взвешенных сумм по классам.
Рассмотрим два разных класса весов с весами \(a\) и \(b\), и пусть общий остаток числа равен \(m\). Если в первом классе есть цифра с остатком \(r\), а во втором классе есть цифра с остатком \(s\), то обмен между этими позициями запрещен ровно тогда, когда
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
Поскольку \(a\not\equiv b\pmod 7\), разность \(a-b\) обратима по модулю 7. Определим
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
Тогда запрещающее условие принимает вид
$$s\equiv r+t(a,b,m)\pmod 7.$$
Значит, два описания классов совместимы тогда и только тогда, когда множество остатков первого класса, сдвинутое на \(t(a,b,m)\), не пересекается с множеством остатков второго класса. Именно поэтому все условия на обмены можно свести к очень маленьким проверкам пересечения 7-битных множеств.
Полезный пример: при \(m=5\), \(a=3\), \(b=1\) имеем \(a-b\equiv 2\), обратный элемент равен \(4\), поэтому
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
То есть любой остаток \(r\), появляющийся в классе веса 3, запрещает остаток \(r+1\pmod 7\) в классе веса 1.
Обмены, затрагивающие первую цифру, несимметричны, потому что более поздний 0 нельзя переносить в начало. Такой обмен создаст ведущий ноль и не считается допустимым. Поэтому первая цифра обрабатывается отдельно: она выбирается из остатков цифр \(1,\dots,9\), а при сравнении с другими классами учитываются только ненулевые остатки, реально присутствующие в этих классах.
Есть и важный безвредный случай. Если вес первой позиции повторяется позже, то обмен с такой позицией вообще не меняет остаток, потому что веса совпадают по модулю 7. Поскольку исходный остаток \(m\) уже ненулевой, такой обмен не может сделать число кратным 7.
Зафиксируем длину \(L\), целевой остаток \(m\in\{1,\dots,6\}\) и остаток первой цифры \(r_0\). Если первая позиция имеет вес \(w_0\), то оставшиеся классы должны дать вклад
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$$
где \(\sigma(C)\) обозначает сохраненный остаток суммы цифр класса \(C\).
Тем самым задача становится конечной и дискретной: нужно выбрать по одному описанию для каждого активного класса, обеспечить совместимость каждой выбранной пары и добиться нужного значения взвешенной суммы. Реализации решают это поиском в глубину, всегда ветвясь по тому классу, у которого осталось меньше всего допустимых описаний.
Для \(L=2\) веса равны \(3\) и \(1\), поэтому число \(10a+b\) имеет остаток
$$m\equiv 3a+b\pmod 7.$$
Единственный возможный обмен дает число \(10b+a\), а изменение остатка равно
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
Например, у числа \(12\) остаток равен \(3\cdot 1+2\equiv 5\pmod 7\), но после обмена получаем \(21\equiv 0\pmod 7\), значит, \(12\) не является heptaphobic. Напротив, \(13\equiv 6\pmod 7\), а его перестановка \(31\equiv 3\pmod 7\), так что этот обмен условие не нарушает. Полный алгоритм использует тот же самый модульный критерий, только применяет его не к отдельным числам, а к сжатым классам весов.
Реализации на C++, Python и Java сначала строят три маленькие постоянные таблицы: шестичленный цикл \(10^k\bmod 7\), число возможных ведущих цифр в каждом классе остатков и каталог всех типов описаний для класса весов данного размера. Каждый тип хранит, какие остатки встречаются, какие ненулевые остатки встречаются, какой вклад класс дает в сумму цифр по модулю 7 и сколько упорядоченных присваиваний цифр приводит к такому же описанию.
Для границы \(10^{13}\) размер каждого неведущего класса весов равен 0, 1 или 2. Поэтому каталоги остаются очень маленькими: 1 описание размера 0, 8 описаний размера 1 и 35 описаний размера 2.
Для фиксированных длины \(L\) и целевого остатка \(m\) реализация сначала подсчитывает, сколько неведущих позиций относится к каждому из шести весов. Для каждого активного класса создается список возможных описаний и их взвешенных модульных вкладов. Дополнительно заранее вычисляется, какие описания могут сосуществовать для каждой упорядоченной пары различных классов, не создавая запрещенного обмена.
Затем выбирается остаток ведущей цифры. Это сразу отсекает все описания классов, которые допускали бы запрещенный ненулевой обмен с первой позицией. После этого рекурсивный поиск выбирает по одному описанию класса за шаг, сужает множества кандидатов с помощью заранее подготовленных таблиц совместимости, обновляет текущую сумму по модулю 7 и умножает на количество конкретных присваиваний цифр, представляемых выбранными описаниями.
Для фиксированной длины результат суммируется по всем ненулевым остаткам \(m=1,\dots,6\), а затем по всем длинам от 1 до 13. Перед тем как выдать окончательное количество чисел меньше \(10^{13}\), код проверяет логику на коротких диапазонах.
Полный перебор потребовал бы проверить почти \(10^{13}\) чисел и для каждого рассмотреть до \(\binom{13}{2}\) обменов цифр. Реализованный метод вообще не итерируется по числам на таком уровне.
Для каждой пары \((L,m)\), где \(1\le L\le 13\) и \(m\in\{1,\dots,6\}\), существует не более шести неведущих классов весов. Каждый класс использует только маленький предварительно вычисленный каталог описаний, и при данной границе ни у одного класса нет более 35 релевантных описаний. Поэтому глубина поиска не превышает шести, а отсечения по попарной совместимости и по условию на модульную сумму работают очень сильно. Память имеет порядок \(O(1)\) относительно числовой границы, потому что хранятся лишь небольшие таблицы остатков и маски кандидатов.
На практике время работы определяется сравнительно небольшим branch-and-prune поиском по случаям \((L,m)\). Именно поэтому метод достаточно быстр, хотя прямой перебор совершенно безнадежен.
لنسمِّ العدد الصحيح الموجب heptaphobic إذا كان غير قابل للقسمة على 7، وظل كذلك بعد أي تبديل صالح بين رقمين عشريين. أمّا التبديل الذي ينقل الصفر إلى الخانة الأولى فيُهمل، لأنه لا ينتج عددًا آخر من الطول نفسه. المطلوب هو عدّ جميع الأعداد heptaphobic الأصغر من \(10^{13}\).
لا تقوم التطبيقات بفحص الأعداد واحدًا واحدًا. بدلًا من ذلك فهي تعدّ بحسب الطول، وتثبّت الباقي غير الصفري \(m=n\bmod 7\)، ثم تسأل: ما أنماط الأرقام التي تجعل من المستحيل على أي تبديل مسموح أن يحوّل الباقي إلى \(0\)؟
لنأخذ عددًا طوله \(L\) وأرقامه \(d_0,d_1,\dots,d_{L-1}\):
$$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$$
بترديد 7 لا تهم إلا أوزان الخانات، ولذلك نعرّف
$$w_i\equiv 10^{L-1-i}\pmod 7.$$
وعندئذ يكون \(n\bmod 7\) مساويًا ببساطة لـ \(\sum d_iw_i\bmod 7\). تقوم الفكرة كلها على فهم كيف يغيّر تبديل رقمين هذا الباقي، ثم على ضغط الخانات ذات الوزن نفسه في فئات واحدة.
إذا بدّلنا الرقمين في الموضعين \(i\) و\(j\)، فإن سائر الحدود تبقى كما هي، لذا يكون تغيّر الباقي
$$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$$
إذًا يصبح العدد ذو الباقي \(m\in\{1,\dots,6\}\) قابلًا للقسمة على 7 بعد ذلك التبديل إذا وفقط إذا تحقق
$$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$$
وهذا يوضح مباشرةً لماذا لا تحتاج الخوارزمية إلى القيم العشرية الكاملة للأرقام؛ فكل ما يهم هو بواقيها modulo 7.
بما أن \(10\equiv 3\pmod 7\) و\(10^6\equiv 1\pmod 7\)، فإن قوى 10 تتكرر modulo 7 بدورية طولها 6:
$$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$$
لذلك، عند تثبيت الطول \(L\)، تنتمي كل خانة غير أولى إلى واحدة من ست فئات وزن. جميع المواضع داخل الفئة الواحدة تملك المضاعف نفسه \(w_i\)، كما أن تبديل رقمين داخل الفئة نفسها لا يغيّر الباقي modulo 7 لأن \(w_i-w_j\equiv 0\pmod 7\).
ولهذا يمكن تلخيص فئة كاملة بأربع معلومات فقط:
مجموعة البواقي التي تظهر فيها، ومجموعة البواقي غير الصفرية التي تظهر فيها، وباقي مجموع أرقام الفئة modulo 7، وعدد الترتيبات الرقمية المرتبة التي تعطي الملخص نفسه.
هذا الضغط لا يفقد أي معلومة يحتاجها الحل. سلامة التبديل بين فئتين تعتمد فقط على البواقي الموجودة في كل فئة، أما الباقي الكلي للعدد فيعتمد فقط على المجاميع الموزونة لتلك الفئات.
لنأخذ فئتين مختلفتين من حيث الوزن، وزنيهما \(a\) و\(b\)، ولنفرض أن الباقي الكلي للعدد هو \(m\). إذا احتوت الفئة الأولى رقمًا ذا باقي \(r\)، واحتوت الفئة الثانية رقمًا ذا باقي \(s\)، فإن التبديل بينهما يكون ممنوعًا بالضبط عندما
$$m+(s-r)(a-b)\equiv 0\pmod 7.$$
وبما أن \(a\not\equiv b\pmod 7\)، فإن الفرق \(a-b\) قابل للعكس modulo 7. نعرّف
$$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$$
فتصبح علاقة المنع
$$s\equiv r+t(a,b,m)\pmod 7.$$
إذن يكون ملخّصا الفئتين متوافقين إذا وفقط إذا كانت مجموعة بواقي الفئة الأولى، بعد إزاحتها بمقدار \(t(a,b,m)\)، منفصلة عن مجموعة بواقي الفئة الثانية. هذه هي النقلة الأساسية في التنفيذ: جميع قيود التبديل تختزل إلى فحوص تقاطع صغيرة جدًا على مجموعات من 7 بتات.
ومثال ملموس: إذا كان \(m=5\) و\(a=3\) و\(b=1\)، فإن \(a-b\equiv 2\)، ومعكوس 2 هو \(4\)، ومن ثم
$$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$$
أي إن كل باقي \(r\) يظهر في فئة الوزن 3 يمنع ظهور الباقي \(r+1\pmod 7\) في فئة الوزن 1.
التبديلات التي تشمل الخانة الأولى ليست متناظرة، لأن الصفر اللاحق لا يجوز نقله إلى البداية. فمثل هذا التبديل يولّد صفرًا بادئًا، وهو مستبعد في نص المسألة. لذلك تُعالج الخانة الأولى على حدة، وتُختار من بواقي الأرقام \(1,\dots,9\)، وعند مقارنتها ببقية الفئات لا نهتم إلا بالبواقي غير الصفرية الموجودة هناك.
وهناك أيضًا حالة آمنة مهمة. إذا تكرر وزن الخانة الأولى لاحقًا، فإن التبديل مع ذلك الموضع لا يغيّر الباقي أصلًا، لأن الوزنين متساويان modulo 7. وبما أن الباقي الأصلي \(m\) غير صفري أصلًا، فلا يمكن لمثل هذا التبديل أن يجعل العدد من مضاعفات 7.
ثبّت الطول \(L\)، والباقي الهدف \(m\in\{1,\dots,6\}\)، وباقي الرقم الأول \(r_0\). إذا كان وزن الخانة الأولى هو \(w_0\)، فيجب على الفئات الباقية أن تحقق
$$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$$
حيث \(\sigma(C)\) هو باقي مجموع أرقام الفئة \(C\) المخزَّن في ملخصها.
وبذلك تصبح المسألة منتهية ومنفصلة: اختر ملخصًا واحدًا لكل فئة فعالة، وتأكد من توافق كل زوج مختار، واجعل المجموع الموزون ينتهي إلى الباقي المطلوب. تنفذ التطبيقات ذلك عبر بحث عُمقي يختار دائمًا الفئة ذات أقل عدد من الملخصات الباقية، مما يمنح تقليمًا قويًا.
عندما \(L=2\)، يكون الوزنان \(3\) و\(1\)، ولذلك فإن العدد \(10a+b\) يملك الباقي
$$m\equiv 3a+b\pmod 7.$$
والتبديل الوحيد الممكن يعطي \(10b+a\)، ويكون تغيّر الباقي
$$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$$
خذ مثلًا \(12\). باقيه هو \(3\cdot 1+2\equiv 5\pmod 7\)، لكن التبديل يعطي \(21\equiv 0\pmod 7\)، ولذلك فـ \(12\) ليس heptaphobic. في المقابل، \(13\equiv 6\pmod 7\) وتبديله \(31\equiv 3\pmod 7\)، فلا توجد مشكلة في هذا التبديل. الخوارزمية الكاملة تستخدم الاختبار المعياري نفسه، لكنها تطبقه على مستوى ملخصات فئات الأوزان بدلًا من اختبار كل عدد على حدة.
تبدأ تطبيقات C++ وPython وJava بحساب ثلاث جداول ثابتة صغيرة: الدورة ذات الطول 6 لـ \(10^k\bmod 7\)، وعدد الأرقام الأولى الممكنة في كل فئة باقي، وفهرس جميع أنواع الملخصات الممكنة لفئة وزن ذات حجم معيّن. كل نوع ملخص يخزن البواقي الموجودة، والبواقي غير الصفرية الموجودة، ومساهمة الفئة في مجموع الأرقام modulo 7، وعدد الترتيبات الرقمية المرتبة التي تنتج الملخص نفسه.
بالنسبة إلى الحد \(10^{13}\)، لا يتجاوز حجم أي فئة وزن غير أولى القيم 0 أو 1 أو 2. ولذلك تبقى الفهارس صغيرة جدًا: يوجد ملخص واحد للحجم 0، وثمانية ملخصات للحجم 1، وخمسة وثلاثون ملخصًا للحجم 2.
عند تثبيت الطول \(L\) والباقي الهدف \(m\)، تحسب الشيفرة عدد المواضع غير الأولى التابعة لكل واحد من الأوزان الستة. ثم تُعطى كل فئة فعالة قائمة بملخصاتها الممكنة مع مساهمة كل ملخص في الباقي الموزون. كذلك تُحسب مسبقًا، لكل زوج مرتب من فئات الأوزان المختلفة، الملخصات التي يمكن أن تتعايش من دون إنشاء تبديل ممنوع.
بعد ذلك يُختار باقي الرقم الأول. هذا الاختيار يستبعد فورًا كل ملخص فئة يسمح بتبديل غير صفري ممنوع مع الخانة الأولى. وعلى ما تبقى من مرشحين، يختار البحث العودي ملخصًا لفئة واحدة في كل خطوة، ويقص مجموعات المرشحين الباقية باستخدام جداول التوافق المحسوبة مسبقًا، ويحدّث مجموع البواقي الجاري، ثم يضرب بعدد الإسنادات الرقمية الفعلية التي تمثلها الملخصات المختارة.
تُجمع النتيجة، لطول ثابت، على جميع البواقي غير الصفرية \(m=1,\dots,6\)، ثم تُجمع على جميع الأطوال من 1 إلى 13. وقبل إنتاج العد النهائي للأعداد الأصغر من \(10^{13}\)، تُجرى اختبارات قصيرة مضمّنة للتحقق من صحة المنطق.
الأسلوب العنيف كان سيتطلب فحص ما يقارب \(10^{13}\) عددًا، ومع كل عدد قد يلزم اختبار ما يصل إلى \(\binom{13}{2}\) تبديلًا بين رقمين. الطريقة المنفذة لا تمر على الأعداد المفردة بهذا الحجم إطلاقًا.
لكل زوج \((L,m)\) حيث \(1\le L\le 13\) و\(m\in\{1,\dots,6\}\)، يوجد في أقصى الأحوال ست فئات وزن غير أولى. كل فئة تستخدم فهرسًا صغيرًا من الملخصات المحسوبة مسبقًا، وتحت هذا الحد لا يملك أي فئة أكثر من 35 ملخصًا ذا صلة. لذلك فإن عمق البحث لا يتجاوز ستة مستويات، مع تقليم قوي ناتج عن توافق الأزواج وشرط المجموع المعياري. كما أن استهلاك الذاكرة هو \(O(1)\) نسبةً إلى الحد العددي، لأن المخزن لا يتعدى جداول بواقي صغيرة وأقنعة مرشحين.
عمليًا يهيمن على زمن التنفيذ بحث branch-and-prune صغير نسبيًا عبر حالات \((L,m)\). ولهذا يكون الحل سريعًا بما يكفي، مع أن العد المباشر مستحيل عمليًا.