For Problem 494 we must evaluate \(f(90)\), where \(f(t)\) counts Collatz prefix families of length \(t\). The checkpoints built into the implementations are \(f(5)=5\), \(f(10)=55\), and \(f(20)=6771\). A direct search in the inverse Collatz tree grows too quickly, so the solution splits the count into a universal Fibonacci backbone and a small finite correction coming from exceptional seeds.
Let
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
The required counting function is evaluated by walking backward through the inverse Collatz graph. The crucial point is that almost all of the structure can be summarized by a Fibonacci term, while the remaining irregular part is concentrated in a fixed set of six seed values.
If \(T(m)=x\), then \(m\) can arise in two ways. The even predecessor is always \(2x\). An odd predecessor exists exactly when \(x\equiv 4\pmod{6}\), in which case it is \((x-1)/3\).
So the inverse predecessor set is
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
Doubling is unconditional, but the odd branch appears only in one congruence class modulo \(6\). That arithmetic restriction is the whole reason the count is structured rather than chaotic.
Whenever the odd predecessor \((x-1)/3\) is used, the result is odd. Therefore the very next inverse step cannot again use the odd-predecessor condition \(x\equiv 4\pmod{6}\). In other words, two odd-branch choices can never occur consecutively.
This creates the standard Fibonacci recurrence. If \(F_1=F_2=1\) and
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3),$$
then the backbone contribution extracted by the implementations is exactly \(F_t\). This is why the small checkpoints begin as
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
before any exceptional seed has enough remaining depth to contribute.
The correction comes from the finite seed set
$$S=\{9,19,37,51,155,159\}.$$
For each seed \(s\in S\), define its forward Collatz distance to the first power of two by
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ is a power of }2\right\}.$$
If we want families of length \(t\), the seed \(s\) matters only when the remaining depth
$$r_s=t-\lambda(s)$$
is non-negative. The count therefore splits as
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
where \(B_r(a)\) denotes the number of inverse descendants of \(a\) after \(r\) backward steps. Seeds with \(r_s<0\) contribute nothing.
The literal backward recurrence is
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{otherwise}. \end{cases}$$
This is the exact mathematical rule used by the simpler implementations: at each layer, replace every current value \(a\) by the always-valid predecessor \(2a\), and add \((a-1)/3\) only when the congruence condition holds.
There is one immediate simplification. If \(3\mid a\), then no odd predecessor can ever appear, because values divisible by \(3\) never satisfy \(x\equiv 4\pmod{6}\). Hence
$$3\mid a \implies B_r(a)=1\qquad\text{for all }r\ge 0.$$
Directly expanding the inverse tree is still too expensive for the final target. The optimized implementation therefore groups states by the number \(k\) of odd-branch moves and by the residue class modulo
$$M_k=2\cdot 3^k.$$
After a backward walk with exactly \(k\) odd-branch moves, this modulus retains exactly the parity and divisibility-by-\(3\) information needed for all future admissibility tests.
If a state is known modulo \(M_k\), the doubling update comes from solving
$$2u\equiv v \pmod{M_k},$$
which produces two residue classes for \(u\). The odd-branch update comes from
$$v=3u+1,$$
so one residue class modulo \(M_{k-1}\) lifts to a single residue class modulo \(M_k\). This turns enormous families of backward walks into residue-table counts.
The optimized implementation also batches the last part of the backward expansion in blocks of four steps. For values not divisible by \(3\), the set of admissible four-step descendants depends only on the current residue modulo \(18\).
That means long remaining depths can be reduced by repeated four-step transfers until the state reaches the precomputed residue-table horizon, after which table lookup finishes the count. The underlying count is unchanged; only the bookkeeping is compressed.
The Fibonacci backbone gives
$$F_{20}=6765.$$
Now compute the forward distances to the first power of two:
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
while \(\lambda(155)=81\) and \(\lambda(159)=50\), so the last two seeds do not contribute at \(t=20\).
The remaining depths are therefore \(5,4,3,0\). Because \(9\) and \(51\) are divisible by \(3\), each contributes exactly \(1\).
For \(19\), the backward expansion is
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
so \(B_4(19)=2\).
For \(37\), the backward expansion is
$$37 \to 74 \to 148 \to \{296,49\},$$
so \(B_3(37)=2\).
Therefore
$$f(20)=6765+1+2+2+1=6771,$$
which is exactly the checkpoint verified by the implementations.
The C++, Python, and Java implementations all begin with the same decomposition: compute the Fibonacci backbone \(F_t\), determine the six seed depths \(\lambda(s)\), and add the inverse-descendant counts for the seeds that still have non-negative remaining depth.
The Python and Java implementations keep the correction term in its most literal form. They simulate the backward recurrence layer by layer, replacing each current value by its doubled predecessor and, when permitted, its odd predecessor. That makes the mathematical structure very transparent.
The C++ implementation uses exactly the same mathematics but accelerates the correction term. It precomputes residue-class tables modulo \(2\cdot 3^k\), orders the seeds by remaining depth, reduces long tails with four-step transfers governed by residues modulo \(18\), and finally accumulates the matching residue counts for each seed. The checkpoints \(5\), \(55\), and \(6771\) are verified before the final computation of \(f(90)\).
If the correction term is implemented literally, inverse expansion is exponential in the remaining seed depth because each layer can branch. That is acceptable only for the short explanatory versions. The optimized implementation replaces most of that tree by residue tables whose widest layer has size \(2\cdot 3^k\), where \(k\) is the number of odd-branch moves being tracked. If \(R=\max_s \max(0,t-\lambda(s))\), the precomputed depth is about \(R/3\), so memory grows like \(O(3^{R/6})\) and the table-building time like \(O(R\,3^{R/6})\), followed by only a small amount of per-seed work because there are just six seeds. In practice this is what makes the final target \(t=90\) feasible.
Für Problem 494 muss \(f(90)\) berechnet werden, wobei \(f(t)\) die Anzahl der Collatz-Präfixfamilien der Länge \(t\) bezeichnet. Die in den Implementierungen geprüften Kontrollwerte sind \(f(5)=5\), \(f(10)=55\) und \(f(20)=6771\). Eine direkte Suche im inversen Collatz-Baum wächst zu schnell, deshalb zerlegt die Lösung die Anzahl in ein universelles Fibonacci-Rückgrat und eine kleine endliche Korrektur aus Ausnahme-Startwerten.
Sei
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
Die gesuchte Zählfunktion wird durch Rückwärtslaufen im inversen Collatz-Graphen bestimmt. Entscheidend ist, dass fast die gesamte Struktur in einem Fibonacci-Term steckt, während der unregelmäßige Rest auf genau sechs Startwerte konzentriert ist.
Falls \(T(m)=x\), kann \(m\) auf zwei Arten entstehen. Der gerade Vorgänger ist immer \(2x\). Ein ungerader Vorgänger existiert genau dann, wenn \(x\equiv 4\pmod{6}\) gilt; dann ist er \((x-1)/3\).
Die inverse Vorgängermenge lautet also
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
Verdoppeln ist immer erlaubt, der ungerade Zweig erscheint aber nur in einer einzigen Restklasse modulo \(6\). Genau diese arithmetische Einschränkung erzeugt die strukturierte Zählung.
Sobald der ungerade Vorgänger \((x-1)/3\) benutzt wird, ist das Ergebnis ungerade. Deshalb kann der unmittelbar nächste inverse Schritt nicht noch einmal die Bedingung \(x\equiv 4\pmod{6}\) erfüllen. Zwei ungerade Verzweigungen können also nie direkt hintereinander auftreten.
Dadurch entsteht die klassische Fibonacci-Rekurrenz. Mit \(F_1=F_2=1\) und
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3)$$
ist der vom Programm abgetrennte Rückgrat-Beitrag genau \(F_t\). Deshalb beginnen die kleinen Kontrollwerte mit
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
bevor irgendein Ausnahme-Startwert überhaupt genügend Resttiefe besitzt.
Der Korrekturterm stammt aus der endlichen Samenmenge
$$S=\{9,19,37,51,155,159\}.$$
Für jeden Startwert \(s\in S\) definieren wir seine Vorwärtsdistanz bis zur ersten Zweierpotenz als
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ eine Zweierpotenz ist}\right\}.$$
Für Präfixfamilien der Länge \(t\) ist \(s\) nur relevant, wenn die verbleibende Tiefe
$$r_s=t-\lambda(s)$$
nicht negativ ist. Damit zerfällt die Gesamtzahl in
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
wobei \(B_r(a)\) die Anzahl inverser Nachkommen von \(a\) nach \(r\) Rückwärtsschritten bezeichnet. Startwerte mit \(r_s<0\) tragen nichts bei.
Die unmittelbare Rückwärtsrekurrenz ist
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{sonst}. \end{cases}$$
Genau diese Regel verwenden die einfacheren Implementierungen: Auf jeder Ebene wird jeder aktuelle Wert \(a\) durch den stets gültigen Vorgänger \(2a\) ersetzt; zusätzlich kommt \((a-1)/3\) hinzu, falls die Kongruenzbedingung erfüllt ist.
Eine sofortige Vereinfachung lautet: Ist \(3\mid a\), dann kann nie ein ungerader Vorgänger auftreten, weil durch \(3\) teilbare Zahlen niemals \(x\equiv 4\pmod{6}\) erfüllen. Also gilt
$$3\mid a \implies B_r(a)=1\qquad\text{für alle }r\ge 0.$$
Die explizite Expansion des inversen Baums ist für das eigentliche Ziel immer noch zu teuer. Die optimierte Implementierung gruppiert Zustände deshalb nach der Zahl \(k\) der ungeraden Verzweigungen und nach ihrer Restklasse modulo
$$M_k=2\cdot 3^k.$$
Nach einem Rückwärtsweg mit genau \(k\) ungeraden Verzweigungen speichert dieser Modul genau die Paritäts- und Teilbarkeitsinformation, die für alle späteren Zulässigkeitstests benötigt wird.
Ist ein Zustand modulo \(M_k\) bekannt, folgt das Verdopplungs-Update aus
$$2u\equiv v \pmod{M_k},$$
was zwei Restklassen für \(u\) liefert. Das ungerade Update folgt aus
$$v=3u+1,$$
sodass eine Restklasse modulo \(M_{k-1}\) zu genau einer Restklasse modulo \(M_k\) angehoben wird. So werden riesige Familien von Rückwärtswegen durch Tabellen über Restklassen ersetzt.
Die optimierte Implementierung fasst den letzten Teil der Rückwärtsentwicklung außerdem in Blöcke von vier Schritten zusammen. Für Werte, die nicht durch \(3\) teilbar sind, hängt die Menge der zulässigen Vier-Schritt-Nachkommen nur von der aktuellen Restklasse modulo \(18\) ab.
Damit können lange Resttiefen durch wiederholte Vier-Schritt-Transfers reduziert werden, bis der Zustand den vorab berechneten Tabellenhorizont erreicht. Danach genügt ein Tabellenzugriff. Die Mathematik bleibt identisch; nur die Buchhaltung wird verdichtet.
Das Fibonacci-Rückgrat liefert
$$F_{20}=6765.$$
Nun berechnen wir die Vorwärtsdistanzen bis zur ersten Zweierpotenz:
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
während \(\lambda(155)=81\) und \(\lambda(159)=50\) gelten; die letzten beiden Startwerte tragen bei \(t=20\) also nichts bei.
Die verbleibenden Tiefen sind damit \(5,4,3,0\). Da \(9\) und \(51\) durch \(3\) teilbar sind, trägt jeder dieser beiden Werte genau \(1\) bei.
Für \(19\) ergibt die Rückwärtsentwicklung
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
also \(B_4(19)=2\).
Für \(37\) erhält man
$$37 \to 74 \to 148 \to \{296,49\},$$
also \(B_3(37)=2\).
Folglich ist
$$f(20)=6765+1+2+2+1=6771,$$
genau der Kontrollwert, den die Implementierungen prüfen.
Die C++-, Python- und Java-Implementierungen beginnen alle mit derselben Zerlegung: Zuerst wird das Fibonacci-Rückgrat \(F_t\) berechnet, dann werden die sechs Starttiefen \(\lambda(s)\) bestimmt, und schließlich werden die inversen Nachkommenzahlen für alle Startwerte mit nichtnegativer Resttiefe addiert.
Die Python- und Java-Implementierungen lassen den Korrekturterm in seiner direktesten Form stehen. Sie simulieren die Rückwärtsrekurrenz Ebene für Ebene, ersetzen jeden aktuellen Wert durch seinen verdoppelten Vorgänger und fügen, falls zulässig, den ungeraden Vorgänger hinzu. Dadurch ist die mathematische Struktur unmittelbar im Programm ablesbar.
Die C++-Implementierung verwendet dieselbe Mathematik, beschleunigt aber den Korrekturterm. Sie berechnet Restklassentabellen modulo \(2\cdot 3^k\) vor, ordnet die Startwerte nach Resttiefe, verkürzt lange Endstücke mit Vier-Schritt-Transfers nach Restklassen modulo \(18\) und summiert zum Schluss die passenden Tabellenwerte für jeden Startwert. Die Kontrollwerte \(5\), \(55\) und \(6771\) werden geprüft, bevor \(f(90)\) ausgegeben wird.
Wird der Korrekturterm wörtlich umgesetzt, ist die inverse Expansion exponentiell in der verbleibenden Starttiefe, weil jede Ebene verzweigen kann. Das ist nur für die kurzen, erklärenden Versionen tragbar. Die optimierte Implementierung ersetzt den größten Teil dieses Baums durch Restklassentabellen, deren breiteste Schicht die Größe \(2\cdot 3^k\) hat, wobei \(k\) die verfolgte Zahl ungerader Verzweigungen ist. Setzt man \(R=\max_s \max(0,t-\lambda(s))\), dann liegt die vorab berechnete Tiefe ungefähr bei \(R/3\); damit wächst der Speicher wie \(O(3^{R/6})\) und die Tabellenberechnung wie \(O(R\,3^{R/6})\). Danach bleibt nur noch wenig Zusatzarbeit pro Startwert, weil insgesamt nur sechs Startwerte vorkommen. So wird das Ziel \(t=90\) praktisch berechenbar.
Problem 494 için hesaplanması gereken değer \(f(90)\)'dır; burada \(f(t)\), uzunluğu \(t\) olan Collatz ön-ek ailelerinin sayısını verir. Uygulamalardaki kontrol noktaları \(f(5)=5\), \(f(10)=55\) ve \(f(20)=6771\) şeklindedir. Ters Collatz ağacında doğrudan arama çok hızlı büyüdüğü için çözüm, sayımı evrensel bir Fibonacci omurgası ile sonlu sayıda istisnai tohum düzeltmesine ayırır.
Şu dönüşümü alalım:
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
Aranan sayım fonksiyonu, ters Collatz grafiğinde geriye doğru yürünerek elde edilir. Asıl fikir şudur: yapının büyük bölümü tek bir Fibonacci terimiyle özetlenebilir; düzensiz kalan kısım ise sabit altı tohum değerde toplanır.
Eğer \(T(m)=x\) ise, \(m\) iki şekilde gelebilir. Çift öncül her zaman \(2x\)'tir. Tek öncül ise ancak \(x\equiv 4\pmod{6}\) olduğunda vardır ve o zaman \((x-1)/3\) olur.
Dolayısıyla ters öncül kümesi
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}$$
şeklindedir. İkiye katlama her zaman mümkündür; tek dal ise yalnızca mod \(6\)'da tek bir artık sınıfında ortaya çıkar. Sayımın düzenli olmasının nedeni tam olarak bu aritmetik kısıttır.
Tek öncül \((x-1)/3\) kullanıldığında sonuç tek sayıdır. Bu yüzden bir sonraki ters adımda yeniden \(x\equiv 4\pmod{6}\) koşulu sağlanamaz. Yani iki tek-dal seçimi arka arkaya gelemez.
Bu da standart Fibonacci bağıntısını doğurur. \(F_1=F_2=1\) ve
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3)$$
olduğunda, uygulamaların ayırdığı omurga katkısı tam olarak \(F_t\)'dir. Bu yüzden küçük kontrol değerleri
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
şeklinde başlar; henüz hiçbir istisnai tohumun pozitif kalan derinliği yoktur.
Düzeltme terimi şu sonlu tohum kümesinden gelir:
$$S=\{9,19,37,51,155,159\}.$$
Her \(s\in S\) için, ilk iki kuvvetine kadar olan ileri Collatz uzaklığını
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ bir }2\text{ kuvvetidir}\right\}$$
olarak tanımlayalım. Uzunluğu \(t\) olan aileler için \(s\) ancak
$$r_s=t-\lambda(s)$$
negatif değilse katkı yapar. Böylece toplam sayım
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s)$$
biçiminde ayrışır; burada \(B_r(a)\), \(a\)'nın \(r\) ters adım sonraki torun sayısıdır. \(r_s<0\) olan tohumlar hiç katkı vermez.
Doğrudan geri sayım bağıntısı
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{aksi halde}. \end{cases}$$
dedir. Daha kısa uygulamalar matematiksel olarak tam bu kuralı izler: her katmanda mevcut her \(a\) değeri için her zaman \(2a\) eklenir; uygun artık sınıfındaysa \((a-1)/3\) da eklenir.
Bir sadeleşme hemen ortaya çıkar. Eğer \(3\mid a\) ise, tek öncül hiçbir zaman oluşamaz; çünkü \(3\)'e bölünebilen sayılar asla \(x\equiv 4\pmod{6}\) olamaz. Bu nedenle
$$3\mid a \implies B_r(a)=1\qquad\text{tüm }r\ge 0\text{ için}.$$
Ters ağacı açıkça büyütmek nihai hedef için hâlâ çok pahalıdır. Bu yüzden optimize edilmiş uygulama durumları, tek-dal adımı sayısı \(k\) ile
$$M_k=2\cdot 3^k$$
modundaki artık sınıfına göre gruplar. Tam olarak \(k\) tek-dal adımı içeren bir geri yürüyüşten sonra bu modül, sonraki uygunluk testleri için gereken parity ve \(3\)'e bölünebilme bilgisini tam olarak saklar.
Bir durum \(M_k\) modunda biliniyorsa, ikiye katlama güncellemesi
$$2u\equiv v \pmod{M_k}$$
denkleminden gelir ve \(u\) için iki artık sınıfı üretir. Tek-dal güncellemesi ise
$$v=3u+1$$
eşitliğinden gelir; böylece \(M_{k-1}\) modundaki tek bir sınıf, \(M_k\) modunda tek bir sınıfa yükselir. Böylece devasa geri-yürüyüş aileleri tablo sayımlarına dönüşür.
Optimize edilmiş uygulama, geri açılımın son kısmını ayrıca dörder adımlı bloklar halinde işler. \(3\)'e bölünmeyen sayılar için izin verilen dört-adımlı torun kümesi yalnızca mevcut değerin mod \(18\)'deki artık sınıfına bağlıdır.
Böylece uzun kalan derinlikler, durum önceden hesaplanan tablo ufkuna inene kadar tekrarlı 4-adımlı transferlerle azaltılır. Sonrasında tek bir tablo bakışı sayımı tamamlar. Matematik değişmez; yalnızca kayıt tutma sıkıştırılır.
Fibonacci omurgası
$$F_{20}=6765$$
değerini verir. Şimdi ilk \(2\) kuvvetine kadar olan ileri uzaklıkları hesaplayalım:
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
ayrıca \(\lambda(155)=81\) ve \(\lambda(159)=50\) olduğundan son iki tohum \(t=20\) için katkı vermez.
Geriye kalan derinlikler sırasıyla \(5,4,3,0\) olur. \(9\) ve \(51\) sayıları \(3\)'e bölündüğü için her biri tam olarak \(1\) katkı yapar.
\(19\) için ters açılım
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\}$$
olur; dolayısıyla \(B_4(19)=2\).
\(37\) için
$$37 \to 74 \to 148 \to \{296,49\}$$
elde edilir; yani \(B_3(37)=2\).
Bu nedenle
$$f(20)=6765+1+2+2+1=6771,$$
ve bu da uygulamaların doğruladığı kontrol değeridir.
C++, Python ve Java uygulamaları aynı ayrışımla başlar: önce Fibonacci omurgası \(F_t\) hesaplanır, sonra altı tohum için \(\lambda(s)\) değerleri bulunur ve son olarak kalan derinliği negatif olmayan tohumların ters-torun sayıları eklenir.
Python ve Java uygulamaları düzeltme terimini en doğrudan haliyle bırakır. Katman katman ilerleyip her mevcut değeri ikiye katlanmış öncülüyle değiştirir, izin verildiğinde tek öncülü de eklerler. Bu, matematiksel yapıyı doğrudan görünür kılar.
C++ uygulaması aynı matematiği kullanır ama düzeltme terimini hızlandırır. \(2\cdot 3^k\) modunda artık sınıf tabloları önceden hesaplanır, tohumlar kalan derinliğe göre sıralanır, uzun kuyruklar mod \(18\) artık sınıflarına bağlı 4-adımlı transferlerle kısaltılır ve en son her tohum için uygun tablo sayıları toplanır. \(5\), \(55\) ve \(6771\) kontrol değerleri doğrulandıktan sonra \(f(90)\) hesaplanır.
Düzeltme terimi doğrudan uygulanırsa ters açılım, kalan tohum derinliğine göre üstel büyür; çünkü her katman dallanabilir. Bu, ancak kısa açıklayıcı sürümler için kabul edilebilir. Optimize edilmiş uygulama, bu ağacın büyük kısmını en geniş katmanı \(2\cdot 3^k\) boyutunda olan artık sınıf tablolarıyla değiştirir; burada \(k\), izlenen tek-dal adımı sayısıdır. \(R=\max_s \max(0,t-\lambda(s))\) yazarsak, ön-hesaplanan derinlik yaklaşık \(R/3\) olur; dolayısıyla bellek \(O(3^{R/6})\), tablo oluşturma süresi ise \(O(R\,3^{R/6})\) mertebesinde büyür. Bunun ardından, yalnızca altı tohum bulunduğu için tohum başına ek iş küçüktür. Pratikte \(t=90\)'ı mümkün kılan şey budur.
Para el Problema 494 debemos evaluar \(f(90)\), donde \(f(t)\) cuenta las familias prefijo de Collatz de longitud \(t\). Los puntos de control incorporados en las implementaciones son \(f(5)=5\), \(f(10)=55\) y \(f(20)=6771\). Una exploración directa del árbol inverso de Collatz crece demasiado rápido, así que la solución separa el conteo en una columna vertebral de Fibonacci y una pequeña corrección finita procedente de semillas excepcionales.
Sea
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
La función pedida se obtiene recorriendo hacia atrás el grafo inverso de Collatz. La observación clave es que casi toda la estructura queda resumida por un término de Fibonacci, mientras que la parte irregular restante se concentra en un conjunto fijo de seis semillas.
Si \(T(m)=x\), entonces \(m\) puede aparecer de dos maneras. El predecesor par es siempre \(2x\). Un predecesor impar existe exactamente cuando \(x\equiv 4\pmod{6}\), y en ese caso vale \((x-1)/3\).
Por tanto, el conjunto de predecesores inversos es
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
El doblado siempre está disponible, pero la rama impar solo aparece en una clase residual módulo \(6\). Esa restricción aritmética es la razón de que el conteo tenga una forma manejable.
Cada vez que se usa el predecesor impar \((x-1)/3\), el resultado es impar. Por ello, el siguiente paso inverso ya no puede volver a satisfacer la condición \(x\equiv 4\pmod{6}\). En consecuencia, dos elecciones de rama impar nunca pueden ser consecutivas.
Eso produce la recurrencia clásica de Fibonacci. Si \(F_1=F_2=1\) y
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3),$$
entonces la contribución de base separada por las implementaciones es exactamente \(F_t\). Por eso los pequeños puntos de control empiezan como
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
antes de que ninguna semilla excepcional tenga profundidad restante suficiente para contribuir.
La corrección procede del conjunto finito
$$S=\{9,19,37,51,155,159\}.$$
Para cada semilla \(s\in S\), definimos su distancia directa de Collatz hasta la primera potencia de dos por
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ es una potencia de }2\right\}.$$
Si queremos familias de longitud \(t\), la semilla \(s\) solo importa cuando la profundidad restante
$$r_s=t-\lambda(s)$$
es no negativa. Así, el conteo total se descompone como
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
donde \(B_r(a)\) denota el número de descendientes inversos de \(a\) tras \(r\) pasos hacia atrás. Las semillas con \(r_s<0\) no aportan nada.
La recurrencia literal hacia atrás es
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{en otro caso}. \end{cases}$$
Esa es exactamente la regla matemática usada por las implementaciones más sencillas: en cada capa, cada valor actual \(a\) se sustituye por su predecesor siempre válido \(2a\), y se añade \((a-1)/3\) solo cuando la condición de congruencia lo permite.
Hay una simplificación inmediata. Si \(3\mid a\), nunca puede aparecer un predecesor impar, porque los múltiplos de \(3\) jamás satisfacen \(x\equiv 4\pmod{6}\). Por tanto,
$$3\mid a \implies B_r(a)=1\qquad\text{para todo }r\ge 0.$$
Expandir explícitamente el árbol inverso sigue siendo demasiado caro para el objetivo final. La implementación optimizada agrupa entonces los estados por el número \(k\) de ramas impares usadas y por la clase residual módulo
$$M_k=2\cdot 3^k.$$
Después de un recorrido hacia atrás con exactamente \(k\) ramas impares, este módulo conserva justamente la información de paridad y divisibilidad por \(3\) necesaria para todas las decisiones futuras.
Si un estado se conoce módulo \(M_k\), la actualización por doblado proviene de resolver
$$2u\equiv v \pmod{M_k},$$
lo que produce dos clases residuales para \(u\). La actualización de rama impar proviene de
$$v=3u+1,$$
de modo que una clase residual módulo \(M_{k-1}\) se eleva a una sola clase residual módulo \(M_k\). De ese modo, enormes familias de recorridos hacia atrás quedan reducidas a conteos tabulados por residuos.
La implementación optimizada también agrupa la parte final de la expansión hacia atrás en bloques de cuatro pasos. Para valores no divisibles por \(3\), el conjunto de descendientes admisibles tras cuatro pasos depende solo de la clase residual actual módulo \(18\).
Eso permite reducir profundidades restantes largas mediante transferencias repetidas de cuatro pasos hasta alcanzar el horizonte de tablas precalculadas, y entonces una consulta de tabla completa el conteo. La matemática no cambia; solo se comprime la contabilidad.
La columna vertebral de Fibonacci aporta
$$F_{20}=6765.$$
Ahora calculamos las distancias directas hasta la primera potencia de dos:
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
mientras que \(\lambda(155)=81\) y \(\lambda(159)=50\), así que las dos últimas semillas no contribuyen cuando \(t=20\).
Las profundidades restantes son entonces \(5,4,3,0\). Como \(9\) y \(51\) son divisibles por \(3\), cada una aporta exactamente \(1\).
Para \(19\), la expansión hacia atrás es
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
por lo que \(B_4(19)=2\).
Para \(37\), la expansión es
$$37 \to 74 \to 148 \to \{296,49\},$$
de donde \(B_3(37)=2\).
Por consiguiente,
$$f(20)=6765+1+2+2+1=6771,$$
que coincide exactamente con el punto de control verificado por las implementaciones.
Las implementaciones en C++, Python y Java empiezan con la misma descomposición: primero calculan la columna vertebral de Fibonacci \(F_t\), luego determinan las seis profundidades \(\lambda(s)\) y finalmente suman los conteos de descendientes inversos de las semillas cuya profundidad restante es no negativa.
Las implementaciones de Python y Java dejan el término correctivo en su forma más literal. Simulan la recurrencia hacia atrás capa por capa, sustituyendo cada valor actual por su predecesor doblado y, cuando está permitido, por su predecesor impar. Eso hace que la estructura matemática sea muy fácil de leer directamente.
La implementación en C++ usa la misma matemática, pero acelera el término correctivo. Precalcula tablas de clases residuales módulo \(2\cdot 3^k\), ordena las semillas por profundidad restante, acorta las colas largas con transferencias de cuatro pasos gobernadas por residuos módulo \(18\), y al final acumula los conteos tabulados que corresponden a cada semilla. Los valores \(5\), \(55\) y \(6771\) se verifican antes del cálculo final de \(f(90)\).
Si el término correctivo se implementa de forma literal, la expansión inversa es exponencial en la profundidad restante de la semilla, porque cada capa puede ramificarse. Eso solo es razonable para las versiones cortas de carácter expositivo. La implementación optimizada sustituye la mayor parte de ese árbol por tablas residuales cuya capa más ancha tiene tamaño \(2\cdot 3^k\), donde \(k\) es el número de ramas impares que se está siguiendo. Si \(R=\max_s \max(0,t-\lambda(s))\), la profundidad precalculada es aproximadamente \(R/3\); así, la memoria crece como \(O(3^{R/6})\) y el tiempo de construcción de tablas como \(O(R\,3^{R/6})\), seguido por una cantidad pequeña de trabajo por semilla porque solo hay seis semillas. En la práctica, eso es lo que hace factible el objetivo final \(t=90\).
在 Problem 494 中，需要计算的是 \(f(90)\)，其中 \(f(t)\) 表示长度为 \(t\) 的 Collatz 前缀族数量。实现里给出的校验点是 \(f(5)=5\)、\(f(10)=55\) 和 \(f(20)=6771\)。如果直接在逆 Collatz 树中暴力扩展，状态数会增长得非常快，因此解法把总计数拆成两部分：一个普适的 Fibonacci 主干项，以及来自少数例外种子的有限修正项。
记
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
要求的计数函数是通过在逆 Collatz 图上向后行走得到的。关键观察是：绝大部分结构都可以浓缩成一个 Fibonacci 项，而真正不规则的部分只集中在固定的六个种子值上。
如果 \(T(m)=x\)，那么 \(m\) 的来源只有两种。偶前驱永远是 \(2x\)。奇前驱只有在 \(x\equiv 4\pmod{6}\) 时才存在，此时它等于 \((x-1)/3\)。
因此，逆向前驱集合为
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
也就是说，“乘 \(2\)”这条逆边始终存在，而“减 \(1\) 后除以 \(3\)”这条逆边只在模 \(6\) 的一个剩余类中出现。整个问题之所以能被组织起来，根源就在这条同余限制。
一旦使用奇前驱 \((x-1)/3\)，得到的结果一定是奇数。于是下一步逆向扩展时，不可能再次满足 \(x\equiv 4\pmod{6}\) 这一条件。换句话说，两次奇分支不可能连续出现。
这正好导出标准的 Fibonacci 递推。如果定义 \(F_1=F_2=1\)，并且
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3),$$
那么实现中单独抽出的主干贡献正是 \(F_t\)。这也解释了为什么较小的校验值一开始就是
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
因为在这些深度下，任何例外种子都还没有足够的剩余层数来产生额外贡献。
修正部分来自下面这个有限集合：
$$S=\{9,19,37,51,155,159\}.$$
对每个种子 \(s\in S\)，定义它沿正向 Collatz 轨道到达第一个 \(2\) 的幂所需的步数
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ 是 }2\text{ 的幂}\right\}.$$
如果目标是长度为 \(t\) 的前缀族，那么种子 \(s\) 只有在剩余深度
$$r_s=t-\lambda(s)$$
非负时才有贡献。因此总计数可以写成
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
其中 \(B_r(a)\) 表示从值 \(a\) 出发，向后走 \(r\) 步后所得到的逆向后代个数。若 \(r_s<0\)，该种子不贡献任何项。
最直接的逆向递推是
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{否则}. \end{cases}$$
这正是较短实现版本在概念上所做的事情：对当前层中的每一个值 \(a\)，总是加入 \(2a\)，而只有在同余条件成立时才额外加入 \((a-1)/3\)。
这里还有一个立刻可用的化简。如果 \(3\mid a\)，那么奇前驱永远不会出现，因为 \(3\) 的倍数不可能满足 \(x\equiv 4\pmod{6}\)。因此
$$3\mid a \implies B_r(a)=1\qquad\text{对所有 }r\ge 0.$$
即使写出了递推，如果真的把逆树完全展开，最终目标仍然太昂贵。优化后的实现因此按照“奇分支使用次数” \(k\) 和模
$$M_k=2\cdot 3^k$$
的剩余类来分组状态。经过恰好 \(k\) 次奇分支之后，这个模数恰好保留了未来所有合法性判断所需的奇偶性与对 \(3\) 的可整除信息。
如果某个状态已知为模 \(M_k\) 的某个剩余类，那么“乘 \(2\)”这条逆更新来自求解
$$2u\equiv v \pmod{M_k},$$
它会给出 \(u\) 的两个剩余类。而奇分支更新来自
$$v=3u+1,$$
因此模 \(M_{k-1}\) 的一个剩余类会提升成模 \(M_k\) 的一个剩余类。这样就能用剩余类表来代替对海量整数状态的显式枚举。
优化后的实现还会把逆向扩展的最后一段按四步一组处理。对于不被 \(3\) 整除的当前值，四步之后可能产生的后代集合只依赖于当前值模 \(18\) 的剩余类。
这意味着，长尾深度可以通过反复应用“四步转移”被压缩到预处理表的深度范围内，随后再用表查询完成计数。数学内容没有改变，改变的只是记账方式。
Fibonacci 主干给出
$$F_{20}=6765.$$
接着计算各个种子到第一个 \(2\) 的幂的正向距离：
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
而 \(\lambda(155)=81\)、\(\lambda(159)=50\)，所以后两个种子在 \(t=20\) 时没有贡献。
于是剩余深度分别为 \(5,4,3,0\)。由于 \(9\) 和 \(51\) 都能被 \(3\) 整除，它们各自只贡献 \(1\)。
对 \(19\) 而言，逆向展开为
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
所以 \(B_4(19)=2\)。
对 \(37\) 而言，逆向展开为
$$37 \to 74 \to 148 \to \{296,49\},$$
所以 \(B_3(37)=2\)。
因此
$$f(20)=6765+1+2+2+1=6771,$$
与实现中验证的校验值完全一致。
C++、Python 和 Java 实现都从同一个分解开始：先计算 Fibonacci 主干 \(F_t\)，再求出六个种子的 \(\lambda(s)\)，最后把所有剩余深度非负的种子的逆向后代计数加起来。
Python 和 Java 实现保留了最直接的修正项形式。它们逐层模拟上述逆向递推，把每个当前值替换成它的双倍前驱，并在条件允许时加入奇前驱。因此从程序文本中就可以直接读出数学结构。
C++ 实现使用完全相同的数学分解，但对修正项进行了加速。它预处理模 \(2\cdot 3^k\) 的剩余类表，按剩余深度整理种子，用由模 \(18\) 剩余类控制的四步转移来缩短长尾，最后再把每个种子对应的表计数累加起来。校验值 \(5\)、\(55\) 和 \(6771\) 会在最终计算 \(f(90)\) 之前先被验证。
如果按最直接的方式实现修正项，那么逆向展开会随着种子的剩余深度呈指数增长，因为每一层都可能分支。这只适合简短的说明性版本。优化后的实现把大部分显式树替换成剩余类表；其中最宽的一层大小为 \(2\cdot 3^k\)，这里 \(k\) 是被跟踪的奇分支次数。若记 \(R=\max_s \max(0,t-\lambda(s))\)，则预处理深度大约是 \(R/3\)，因此空间规模约为 \(O(3^{R/6})\)，建表时间约为 \(O(R\,3^{R/6})\)。之后由于只有六个种子，额外的逐种子工作量很小。也正因为如此，最终目标 \(t=90\) 才变得可行。
В задаче 494 требуется вычислить \(f(90)\), где \(f(t)\) обозначает число префиксных семейств Collatz длины \(t\). Контрольные значения, заложенные в реализациях, таковы: \(f(5)=5\), \(f(10)=55\), \(f(20)=6771\). Прямое развертывание обратного дерева Collatz растет слишком быстро, поэтому решение раскладывает ответ на универсальный вклад Фибоначчи и небольшую конечную поправку от исключительных начальных значений.
Пусть
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
Искомая функция подсчета получается движением назад по обратному графу Collatz. Главная идея состоит в том, что почти вся структура сводится к одному члену Фибоначчи, а нерегулярная часть сосредоточена в фиксированном наборе из шести начальных точек.
Если \(T(m)=x\), то значение \(m\) может возникнуть двумя способами. Четный предок всегда равен \(2x\). Нечетный предок существует ровно тогда, когда \(x\equiv 4\pmod{6}\), и тогда он равен \((x-1)/3\).
Значит, множество обратных предков имеет вид
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
Удвоение возможно всегда, а нечетный переход возникает только в одном классе вычетов по модулю \(6\). Именно это арифметическое ограничение делает счет контролируемым.
Если используется нечетный предок \((x-1)/3\), полученное число обязательно нечетно. Поэтому на следующем обратном шаге условие \(x\equiv 4\pmod{6}\) уже не может выполниться снова. Следовательно, два нечетных ветвления подряд невозможны.
Отсюда возникает стандартная рекурсия Фибоначчи. Если \(F_1=F_2=1\) и
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3),$$
то базовый вклад, выделяемый реализациями, равен ровно \(F_t\). Поэтому первые контрольные значения имеют вид
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
пока никакое исключительное начальное значение еще не обладает достаточной оставшейся глубиной.
Поправочный вклад задается конечным множеством
$$S=\{9,19,37,51,155,159\}.$$
Для каждого \(s\in S\) введем прямую Collatz-длину до первой степени двойки:
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\text{ является степенью }2\right\}.$$
Если нас интересуют семейства длины \(t\), то семя \(s\) влияет на ответ только при неотрицательной остаточной глубине
$$r_s=t-\lambda(s).$$
Тем самым общее число раскладывается как
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
где \(B_r(a)\) обозначает число обратных потомков значения \(a\) после \(r\) шагов назад. Если \(r_s<0\), соответствующее семя не дает вклада.
Прямая обратная рекурсия такова:
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{иначе}. \end{cases}$$
Именно этим правилом в сущности пользуются более короткие реализации: на каждом слое значение \(a\) заменяется обязательным предком \(2a\), а при выполнении сравнения по модулю добавляется еще и \((a-1)/3\).
Есть и немедленное упрощение. Если \(3\mid a\), то нечетный предок не появится никогда, потому что кратные \(3\) не удовлетворяют условию \(x\equiv 4\pmod{6}\). Следовательно,
$$3\mid a \implies B_r(a)=1\qquad\text{для всех }r\ge 0.$$
Явное развертывание обратного дерева все равно слишком дорого для финальной цели. Поэтому оптимизированная реализация группирует состояния по числу \(k\) нечетных ветвлений и по классу вычетов modulo
$$M_k=2\cdot 3^k.$$
После обратного пути с ровно \(k\) нечетными ветвлениями этот модуль хранит в точности ту информацию о четности и делимости на \(3\), которая нужна для всех последующих проверок допустимости.
Если состояние известно modulo \(M_k\), то обновление по удвоению возникает из сравнения
$$2u\equiv v \pmod{M_k},$$
которое дает два класса вычетов для \(u\). Обновление по нечетной ветви следует из
$$v=3u+1,$$
так что один класс по модулю \(M_{k-1}\) поднимается в единственный класс по модулю \(M_k\). Благодаря этому огромные семейства обратных путей заменяются табличным подсчетом по вычетам.
Оптимизированная реализация также объединяет последнюю часть обратного развертывания в блоки по четыре шага. Для значений, не делящихся на \(3\), множество допустимых потомков через четыре обратных шага зависит только от текущего остатка modulo \(18\).
Это позволяет сокращать длинные хвосты глубины последовательными четырехшаговыми переносами, пока состояние не дойдет до заранее рассчитанного табличного горизонта; затем счет завершается простым обращением к таблице. Математика остается той же, меняется только техника учета.
Фибоначчиевский каркас дает
$$F_{20}=6765.$$
Теперь вычислим прямые длины до первой степени двойки:
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
а также \(\lambda(155)=81\) и \(\lambda(159)=50\), поэтому два последних семени при \(t=20\) вклада не дают.
Оставшиеся глубины равны \(5,4,3,0\). Так как \(9\) и \(51\) делятся на \(3\), каждое из них дает ровно \(1\).
Для \(19\) обратное развертывание имеет вид
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
поэтому \(B_4(19)=2\).
Для \(37\) получаем
$$37 \to 74 \to 148 \to \{296,49\},$$
значит, \(B_3(37)=2\).
Следовательно,
$$f(20)=6765+1+2+2+1=6771,$$
что в точности совпадает с проверочным значением в реализациях.
Реализации на C++, Python и Java начинают с одного и того же разложения: сначала вычисляется фибоначчиевский каркас \(F_t\), затем находятся шесть величин \(\lambda(s)\), после чего добавляются числа обратных потомков для семян с неотрицательной остаточной глубиной.
Версии на Python и Java оставляют поправочный член в максимально буквальном виде. Они имитируют обратную рекурсию слой за слоем, заменяя каждое текущее значение на удвоенного предка и, когда это допустимо, на нечетного предка. Поэтому математическая структура прямо видна в программе.
Версия на C++ использует ту же самую математику, но ускоряет поправку. Она заранее строит таблицы классов вычетов modulo \(2\cdot 3^k\), упорядочивает семена по остаточной глубине, сокращает длинные хвосты четырехшаговыми переносами, зависящими от остатка modulo \(18\), и затем суммирует табличные значения, подходящие каждому семени. Контрольные числа \(5\), \(55\) и \(6771\) проверяются до финального вычисления \(f(90)\).
Если реализовать поправку буквально, обратное развертывание будет экспоненциальным по оставшейся глубине семени, поскольку каждый слой может ветвиться. Это приемлемо только для коротких пояснительных версий. Оптимизированная реализация заменяет большую часть этого дерева таблицами по классам вычетов, у которых самая широкая строка имеет размер \(2\cdot 3^k\), где \(k\) — число отслеживаемых нечетных ветвлений. Если положить \(R=\max_s \max(0,t-\lambda(s))\), то глубина предвычисления составляет примерно \(R/3\); поэтому память растет как \(O(3^{R/6})\), а время построения таблиц — как \(O(R\,3^{R/6})\). После этого остается лишь небольшой объем работы на каждое семя, поскольку семян всего шесть. Именно это и делает достижимой финальную цель \(t=90\).
في المسألة 494 نريد حساب \(f(90)\)، حيث تمثل \(f(t)\) عدد عائلات البادئات في مسألة Collatz ذات الطول \(t\). نقاط التحقق الموجودة في التطبيقات هي \(f(5)=5\) و\(f(10)=55\) و\(f(20)=6771\). التوسع المباشر في شجرة Collatz العكسية ينمو بسرعة كبيرة جدًا، لذلك يفصل الحل العد إلى حد أساسي من نوع Fibonacci وتصحيح نهائي صغير قادم من مجموعة من البذور الاستثنائية.
لنأخذ التحويل
$$T(n)=\begin{cases} n/2, & n\equiv 0 \pmod{2}, \\ 3n+1, & n\equiv 1 \pmod{2}. \end{cases}$$
يتم حساب الدالة المطلوبة بالسير إلى الخلف داخل الرسم البياني العكسي لـ Collatz. والملاحظة الحاسمة هي أن معظم البنية يمكن ضغطها في حد Fibonacci واحد، بينما الجزء غير المنتظم كله تقريبًا يتمركز في ست قيم أولية ثابتة.
إذا كان \(T(m)=x\)، فهناك طريقتان فقط لظهور \(m\). السلف الزوجي موجود دائمًا وهو \(2x\). أما السلف الفردي فلا يوجد إلا عندما يتحقق \(x\equiv 4\pmod{6}\)، وعندها يكون مساويًا لـ \((x-1)/3\).
إذن مجموعة الأسلاف العكسية هي
$$P(x)=\left\{2x\right\}\cup\left\{\frac{x-1}{3}: x\equiv 4\pmod{6}\right\}.$$
التضاعف متاح دائمًا، أما الفرع الفردي فلا يظهر إلا في فئة باقية واحدة modulo \(6\). وهذا القيد الحسابي هو السبب في أن العد يمكن تنظيمه بدل أن يكون فوضويًا.
كلما استُخدم السلف الفردي \((x-1)/3\)، كانت النتيجة عددًا فرديًا. لذلك لا يمكن أن يحقق السطر العكسي التالي الشرط \(x\equiv 4\pmod{6}\) مرة أخرى مباشرة. أي إن خطوتين فرديتين متتاليتين غير ممكنتين.
وهذا يعطي مباشرة علاقة Fibonacci القياسية. إذا أخذنا \(F_1=F_2=1\) و
$$F_t=F_{t-1}+F_{t-2}\qquad (t\ge 3),$$
فإن المساهمة الأساسية التي تفصلها التطبيقات هي بالضبط \(F_t\). ولهذا تبدأ نقاط التحقق الصغيرة على الصورة
$$f(5)=F_5=5,\qquad f(10)=F_{10}=55,$$
وذلك قبل أن تمتلك أي بذرة استثنائية عمقًا متبقيًا موجبًا يسمح لها بإضافة مساهمة جديدة.
يأتي حد التصحيح من المجموعة المنتهية
$$S=\{9,19,37,51,155,159\}.$$
ولكل بذرة \(s\in S\)، نعرّف طولها الأمامي حتى أول قوة للعدد \(2\) بواسطة
$$\lambda(s)=\min\left\{k\ge 0: T^{(k)}(s)\in\{1,2,4,8,\dots\}\right\}.$$
إذا كان المطلوب عائلات بطول \(t\)، فإن البذرة \(s\) لا تؤثر إلا عندما يكون العمق المتبقي
$$r_s=t-\lambda(s)$$
غير سالب. وعندئذ ينقسم العدد الكلي إلى
$$f(t)=F_t+\sum_{s\in S,\ r_s\ge 0} B_{r_s}(s),$$
حيث إن \(B_r(a)\) يرمز إلى عدد الأحفاد في الشجرة العكسية المنطلقين من \(a\) بعد \(r\) خطوات رجوع. أما إذا كان \(r_s<0\)، فلا توجد مساهمة من تلك البذرة.
علاقة الرجوع المباشرة هي
$$B_0(a)=1,$$
$$B_{r+1}(a)=B_r(2a)+ \begin{cases} B_r\!\left(\dfrac{a-1}{3}\right), & a\equiv 4\pmod{6},\\ 0, & \text{otherwise}. \end{cases}$$
وهذه هي القاعدة الرياضية الدقيقة التي تستخدمها النسخ الأبسط: في كل طبقة نستبدل كل قيمة حالية \(a\) بسلفها المضاعف \(2a\)، ونضيف \((a-1)/3\) فقط إذا تحققت شروط التطابق.
وهنا يوجد تبسيط مهم مباشرة. إذا كان \(3\mid a\)، فلن يظهر السلف الفردي أبدًا، لأن مضاعفات \(3\) لا تحقق الشرط \(x\equiv 4\pmod{6}\). لذلك
$$3\mid a \implies B_r(a)=1\qquad \forall r\ge 0.$$
حتى مع هذه العلاقة، يبقى التوسع الصريح للشجرة العكسية مكلفًا جدًا للهدف النهائي. لذلك تجمع النسخة المحسنة الحالات بحسب عدد الفروع الفردية \(k\) وبحسب فئة الباقي modulo
$$M_k=2\cdot 3^k.$$
بعد مسار عكسي يستخدم بالضبط \(k\) فروع فردية، يحتفظ هذا الموديل بكل معلومات الزوجية والقابلية للقسمة على \(3\) اللازمة لكل اختبارات السماحية اللاحقة.
إذا كانت الحالة معلومة modulo \(M_k\)، فإن تحديث التضاعف يأتي من حل
$$2u\equiv v \pmod{M_k},$$
وهو ما يعطي فئتين باقيتين ممكنتين لـ \(u\). أما تحديث الفرع الفردي فيأتي من
$$v=3u+1,$$
ولذلك ترتفع فئة باق واحدة modulo \(M_{k-1}\) إلى فئة باق واحدة modulo \(M_k\). وهكذا يتم استبدال أسر هائلة من المسارات العكسية بعدّ جدولي حسب البواقي.
النسخة المحسنة تجمع أيضًا الجزء الأخير من التوسع العكسي في كتل من أربع خطوات. بالنسبة للقيم غير القابلة للقسمة على \(3\)، فإن مجموعة الأحفاد المسموح بها بعد أربع خطوات تعتمد فقط على الباقي الحالي modulo \(18\).
هذا يسمح بتقليص الأعماق المتبقية الطويلة عبر انتقالات رباعية متكررة حتى تصل الحالة إلى أفق الجداول المحسوبة مسبقًا، ثم تنهي عملية العد بقراءة جدولية واحدة. البنية الرياضية نفسها لا تتغير، وإنما الذي يتغير هو طريقة تنظيم الحساب.
يعطي العمود الفقري من نوع Fibonacci القيمة
$$F_{20}=6765.$$
ثم نحسب الأطوال الأمامية حتى أول قوة للعدد \(2\):
$$\lambda(9)=15,\qquad \lambda(19)=16,\qquad \lambda(37)=17,\qquad \lambda(51)=20,$$
بينما \(\lambda(155)=81\) و\(\lambda(159)=50\)، لذلك لا تساهم البذرتان الأخيرتان عندما \(t=20\).
وبالتالي تكون الأعماق المتبقية هي \(5,4,3,0\). وبما أن \(9\) و\(51\) يقبلان القسمة على \(3\)، فإن مساهمة كل منهما تساوي \(1\) بالضبط.
بالنسبة إلى \(19\)، يكون التوسع العكسي
$$19 \to 38 \to 76 \to \{152,25\} \to \{304,50\},$$
ومن ثم \(B_4(19)=2\).
وبالنسبة إلى \(37\)، نحصل على
$$37 \to 74 \to 148 \to \{296,49\},$$
أي إن \(B_3(37)=2\).
لذلك
$$f(20)=6765+1+2+2+1=6771,$$
وهو تمامًا مقدار التحقق الذي تؤكده التطبيقات.
تبدأ تطبيقات C++ وPython وJava من نفس التحليل: أولًا يُحسب العمود الفقري \(F_t\)، ثم تُستخرج القيم الست \(\lambda(s)\)، ثم تُضاف أعداد الأحفاد العكسيين لكل بذرة تملك عمقًا متبقيًا غير سالب.
يحافظ تطبيقا Python وJava على حد التصحيح بصورته الأكثر مباشرة. فهما يحاكيان علاقة الرجوع طبقة بعد طبقة، ويستبدلان كل قيمة حالية بسلفها المضاعف، ثم يضيفان السلف الفردي عندما تسمح شروط التطابق. ولهذا تكون البنية الرياضية واضحة جدًا من القراءة المباشرة.
أما تطبيق C++ فيستخدم الرياضيات نفسها، لكنه يسرّع حد التصحيح. فهو يهيئ جداول فئات البواقي modulo \(2\cdot 3^k\)، ويرتب البذور حسب العمق المتبقي، ويختصر الذيول الطويلة بانتقالات من أربع خطوات يحكمها الباقي modulo \(18\)، ثم يجمع في النهاية الأعداد الجدولية الموافقة لكل بذرة. وتُفحَص القيم \(5\) و\(55\) و\(6771\) قبل الحساب النهائي لـ \(f(90)\).
إذا طُبِّق حد التصحيح بشكل مباشر، فإن التوسع العكسي يكون أُسّيًا في العمق المتبقي للبذرة، لأن كل طبقة قد تتشعب. وهذا مناسب فقط للنسخ القصيرة الشارحة. النسخة المحسنة تستبدل معظم ذلك التوسع بجداول للبواقي، يكون أكبر صف فيها بحجم \(2\cdot 3^k\)، حيث \(k\) هو عدد الفروع الفردية الجاري تتبعها. وإذا كتبنا \(R=\max_s \max(0,t-\lambda(s))\)، فإن عمق التهيئة المسبقة يكون تقريبًا \(R/3\)، ومن ثم تنمو الذاكرة مثل \(O(3^{R/6})\) وزمن بناء الجداول مثل \(O(R\,3^{R/6})\)، ثم يبقى قدر صغير من العمل لكل بذرة لأن عدد البذور يساوي ستًا فقط. وهذا هو ما يجعل الهدف النهائي \(t=90\) ممكنًا عمليًا.