The sequence is defined by
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
where \(\sigma(x)\) is the decimal digit sum of \(x\). The target index is so large that simulating every update one by one is infeasible, so the implementations accelerate the process by grouping many ordinary updates into exact carry-to-carry transitions.
The key observation is that decimal digit sums behave well across powers of \(10\). By isolating the lowest six digits, the recurrence splits into a rapidly changing low part and a slowly changing high part. That split makes it possible to precompute exact jumps to the next carry and then compose those jumps over long intervals.
Set
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
Let \(\sigma_6(r)\) denote the digit sum of the six-digit decimal block of \(r\), allowing leading zeros. Because \(B\) is a power of \(10\), the decimal digits of \(q_n\) and \(r_n\) do not interfere, so
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
Therefore one elementary update becomes
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
If the low part stays below \(B\), then
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
If the low part reaches or exceeds \(B\), one carry occurs:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
For the target computation, the high part never needs more than \(12\) decimal digits, so \(\sigma(q_n)\le 108\). Since \(\sigma_6(r_n)\le 54\), every elementary update increases the low part by at most \(162\). In particular, a single update can create at most one carry.
While \(q_n\) is fixed, its digit sum is a constant. For a fixed value \(c\), define
$$F_c(x)=x+\sigma_6(x)+c.$$
Starting from a low part \(x\), the next carry happens after
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
elementary updates, and the low part immediately after that carry is
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
These quantities are exact: \(\tau_c(x)\) counts how many ordinary recurrence steps are consumed before the boundary \(B\) is crossed, and \(\rho_c(x)\) is the true remainder after subtracting \(B\).
At the moment of crossing we have
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
so the post-carry remainder always satisfies
$$0\le \rho_c(x)\le 162.$$
This is the main compression step. Although the low part can wander through all values below \(10^6\) before the next carry, the state immediately after a carry lies in the tiny set
$$S=\{0,1,2,\dots,162\}.$$
So a carry event can be viewed as a macro-step that starts from some remainder in \(S\), spends a known number of elementary updates, and returns to another remainder in \(S\).
For each current high part \(h\), let \(c=\sigma(h)\). One carry event then induces a transition \(M_h\) on the small remainder set \(S\): for each \(x\in S\), the transition returns the new remainder \(\rho_c(x)\) and the exact cost \(\tau_c(x)\).
If we want to process several carries in a row, starting from high part \(h\), we must compose the transitions
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots.$$
For adjacent intervals of high-part values, composition is exact:
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
This means that long runs of carry events can be handled by composing reusable transition blocks instead of replaying each event separately.
Consider an aligned interval of length \(10^d\), such as all high-part values from \(2300\) to \(2399\). Every number in that interval shares the same prefix and only the last \(d\) digits vary. Because digit sums split over decimal concatenation, the digit sum of each high part is
$$\sigma(\text{prefix}\cdot 10^d+\text{suffix})=\sigma(\text{prefix})+\sigma(\text{suffix}).$$
Therefore the full transition of such a block depends only on two pieces of information: the block length \(10^d\) and the digit sum of the fixed prefix. The implementations precompute all these aligned decimal blocks up to \(d=12\). An arbitrary interval \([u,v)\) is then decomposed greedily into aligned blocks, so a long interval can be evaluated with only a small number of transition compositions.
Suppose \(R\) elementary updates are still available. Let \(C(m)\) be the number of elementary updates consumed by the next \(m\) carry events from the current state. Since each carry event costs at least one ordinary update, \(C(m)\) is strictly increasing.
So the algorithm finds
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
by first doubling \(m\) until the budget is exceeded and then applying binary search. After those \(m^*\) carry events are executed in one shot, the remaining budget is too small to reach the next carry. The last few elementary updates are therefore performed directly with the high part fixed.
Take
$$a=17\cdot 10^6+999995.$$
Then \(\sigma(17)=8\) and \(\sigma_6(999995)=50\). One elementary update gives
$$999995+50+8=1000053,$$
so the next term is
$$a'=18\cdot 10^6+53.$$
This single carry event has consumed one ordinary recurrence step and moved the low part back into the small set \(S\). Now the high part is \(18\), so its digit sum is \(9\). If two more elementary updates are taken before the next carry, the low part evolves as
$$53\to 70\to 86,$$
because \(53+\sigma_6(53)+9=53+8+9=70\) and \(70+\sigma_6(70)+9=70+7+9=86\). This is exactly the kind of short leftover tail that the algorithm finishes directly after the carry-jump phase.
The C++, Python, and Java implementations begin by precomputing the digit sum of every six-digit value from \(0\) to \(999999\). This makes the low-part update \(x\mapsto x+\sigma_6(x)+c\) constant-time for every possible state.
Next, for each possible digit sum \(c\) of the high part, the implementation scans the full low-part range backward and determines the exact number of ordinary updates needed to hit the next carry, together with the post-carry remainder. Only the carry-to-carry states \(0\) through \(162\) need to be retained for later composition, because every carry lands inside that range.
After that, the implementation builds transition blocks for aligned decimal intervals of lengths \(1,10,100,\dots,10^{12}\). Each block stores, for every small remainder, both the new remainder and the number of ordinary updates consumed across that whole interval of consecutive high-part values.
During the actual solve phase, the current value starts at \(1\). The implementation repeatedly asks how many carry events can be afforded under the remaining step budget, answers that question with doubling and binary search, applies the resulting interval transition, and finally performs the tiny leftover suffix directly. The method is exact throughout; nothing is approximated.
Let \(B=10^6\), let \(C=108\) be the maximum possible digit sum of the high part used by the implementations, let \(R=162\) be the post-carry remainder bound, and let \(D=12\) be the maximum decimal block depth. Precomputing all six-digit digit sums costs \(O(B)\) time. Building the next-carry information for every \(c\in[0,C]\) costs \(O(BC)\) time and dominates the preprocessing.
The aligned block tables operate only on the tiny state space of size \(R+1=163\), so their cost is much smaller than the carry-table construction. For the single final query, doubling and binary search use a logarithmic number of interval evaluations, and each interval evaluation touches only a small number of decimal blocks. Memory usage is dominated by the carry tables and is \(O(BC)\).
Die Folge ist definiert durch
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
wobei \(\sigma(x)\) die Summe der Dezimalziffern von \(x\) ist. Der Zielindex ist so groß, dass eine schrittweise Simulation unmöglich wäre. Deshalb beschleunigen die Implementierungen den Ablauf, indem sie viele gewöhnliche Updates zu exakten Übergängen von einem Übertrag zum nächsten zusammenfassen.
Die entscheidende Beobachtung ist, dass sich Dezimalziffernsummen an Zehnerpotenzen sauber trennen lassen. Wenn man die unteren sechs Ziffern isoliert, zerfällt die Rekurrenz in einen schnell wechselnden unteren Teil und einen langsam wechselnden oberen Teil. Dadurch kann man exakte Sprünge bis zum nächsten Übertrag vorberechnen und diese Sprünge anschließend über lange Intervalle zusammensetzen.
Setze
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
Sei \(\sigma_6(r)\) die Ziffernsumme des sechsstelligen Dezimalblocks von \(r\), führende Nullen eingeschlossen. Weil \(B\) eine Zehnerpotenz ist, beeinflussen sich die Dezimalziffern von \(q_n\) und \(r_n\) nicht, also gilt
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
Damit wird ein elementares Update zu
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
Falls der untere Teil unter \(B\) bleibt, erhält man
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
Erreicht oder überschreitet der untere Teil \(B\), entsteht genau ein Übertrag:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
Für die Zielrechnung benötigt der obere Teil höchstens \(12\) Dezimalziffern, also \(\sigma(q_n)\le 108\). Da außerdem \(\sigma_6(r_n)\le 54\) gilt, wächst der untere Teil pro elementarem Update um höchstens \(162\). Deshalb kann in einem einzelnen Update höchstens ein Übertrag auftreten.
Solange \(q_n\) fest bleibt, ist auch seine Ziffernsumme konstant. Für einen festen Wert \(c\) definieren wir
$$F_c(x)=x+\sigma_6(x)+c.$$
Ausgehend von einem unteren Teil \(x\) tritt der nächste Übertrag nach
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
elementaren Updates ein, und der neue untere Teil direkt nach dem Übertrag ist
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
Diese Größen sind exakt: \(\tau_c(x)\) zählt die wirklichen Rekurrenzschritte bis zum Überschreiten der Grenze \(B\), und \(\rho_c(x)\) ist genau der Rest nach dem Subtrahieren von \(B\).
Im Moment des Überschreitens gilt
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
daher erfüllt der Rest nach dem Übertrag stets
$$0\le \rho_c(x)\le 162.$$
Das ist die eigentliche Kompression. Vor dem nächsten Übertrag kann der untere Teil zwar beliebige Werte unterhalb von \(10^6\) durchlaufen, aber unmittelbar nach einem Übertrag liegt er immer in der kleinen Menge
$$S=\{0,1,2,\dots,162\}.$$
Ein Übertrag kann also als Makroschritt aufgefasst werden: Er startet bei einem Rest aus \(S\), verbraucht eine exakt bekannte Zahl elementarer Updates und landet wieder bei einem Rest aus \(S\).
Für jeden aktuellen oberen Teil \(h\) setzen wir \(c=\sigma(h)\). Ein Übertrag erzeugt dann einen Übergang \(M_h\) auf der kleinen Restmenge \(S\): Für jedes \(x\in S\) liefert er den neuen Rest \(\rho_c(x)\) und die exakten Kosten \(\tau_c(x)\).
Will man mehrere Überträge hintereinander ausführen und startet beim oberen Teil \(h\), so müssen die Übergänge
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
zusammengesetzt werden. Für benachbarte Intervalle von oberen Teilen gilt exakt
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
Dadurch lassen sich lange Folgen von Überträgen durch Komposition wiederverwendbarer Blöcke behandeln, statt jeden einzelnen Übertrag separat auszuspielen.
Betrachte ein ausgerichtetes Intervall der Länge \(10^d\), zum Beispiel alle oberen Teile von \(2300\) bis \(2399\). Alle Zahlen in diesem Intervall besitzen denselben Präfix; nur die letzten \(d\) Stellen variieren. Weil sich Ziffernsummen über Dezimalkonkatenation additiv verhalten, gilt
$$\sigma(\text{Präfix}\cdot 10^d+\text{Suffix})=\sigma(\text{Präfix})+\sigma(\text{Suffix}).$$
Somit hängt der gesamte Übergang eines solchen Blocks nur von zwei Größen ab: von der Blocklänge \(10^d\) und von der Ziffernsumme des festen Präfixes. Die Implementierungen berechnen alle diese ausgerichteten Dezimalblöcke bis \(d=12\) vor. Ein beliebiges Intervall \([u,v)\) wird dann gierig in ausgerichtete Blöcke zerlegt, sodass ein langer Bereich mit nur wenigen Übergangskompositionen ausgewertet werden kann.
Angenommen, es stehen noch \(R\) elementare Updates zur Verfügung. Sei \(C(m)\) die Anzahl elementarer Updates, die durch die nächsten \(m\) Überträge vom aktuellen Zustand aus verbraucht werden. Da jeder Übertrag mindestens einen gewöhnlichen Update-Schritt kostet, ist \(C(m)\) streng monoton wachsend.
Gesucht wird also
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
zuerst per Verdopplung und danach per binärer Suche. Sind diese \(m^*\) Überträge in einem Schritt ausgeführt, dann reicht das verbleibende Budget nicht mehr für den nächsten Übertrag. Die letzten wenigen elementaren Updates werden deshalb direkt mit festem oberen Teil simuliert.
Nehmen wir
$$a=17\cdot 10^6+999995.$$
Dann sind \(\sigma(17)=8\) und \(\sigma_6(999995)=50\). Ein elementares Update ergibt
$$999995+50+8=1000053,$$
also wird der nächste Term zu
$$a'=18\cdot 10^6+53.$$
Dieser einzelne Übertrag hat genau einen Rekurrenzschritt verbraucht und den unteren Teil wieder in die kleine Menge \(S\) zurückgeführt. Nun ist der obere Teil \(18\), also seine Ziffernsumme \(9\). Wenn danach noch zwei elementare Updates vor dem nächsten Übertrag ausgeführt werden, entwickelt sich der untere Teil als
$$53\to 70\to 86,$$
denn \(53+\sigma_6(53)+9=53+8+9=70\) und \(70+\sigma_6(70)+9=70+7+9=86\). Genau diesen kurzen Restlauf behandelt der Algorithmus am Ende direkt.
Die C++-, Python- und Java-Implementierungen berechnen zunächst die Ziffernsumme für jeden sechsstelligen Wert von \(0\) bis \(999999\) vor. Dadurch ist das Update des unteren Teils \(x\mapsto x+\sigma_6(x)+c\) für jeden möglichen Zustand in konstanter Zeit verfügbar.
Danach wird für jede mögliche Ziffernsumme \(c\) des oberen Teils der gesamte Bereich des unteren Teils rückwärts durchlaufen, um die exakte Zahl gewöhnlicher Updates bis zum nächsten Übertrag sowie den Rest nach diesem Übertrag zu bestimmen. Für die spätere Komposition müssen nur die Zustände \(0\) bis \(162\) erhalten bleiben, weil jeder Übertrag in genau diesem Bereich landet.
Anschließend baut die Implementierung Übergangsblöcke für ausgerichtete Dezimalintervalle der Längen \(1,10,100,\dots,10^{12}\) auf. Jeder Block speichert für jeden kleinen Rest sowohl den neuen Rest als auch die Zahl gewöhnlicher Updates, die über das gesamte Intervall aufeinanderfolgender oberer Teile verbraucht werden.
In der eigentlichen Lösungsphase startet der aktuelle Wert bei \(1\). Die Implementierung fragt wiederholt, wie viele Überträge unter dem verbleibenden Schrittbudget möglich sind, beantwortet diese Frage mit Verdopplung und binärer Suche, wendet den resultierenden Intervallübergang an und simuliert schließlich nur noch den winzigen Rest direkt. Das Verfahren ist vollständig exakt; es gibt keinerlei Näherung.
Seien \(B=10^6\), \(C=108\) die maximale Ziffernsumme des oberen Teils in den Implementierungen, \(R=162\) die Schranke für den Rest nach einem Übertrag und \(D=12\) die maximale Dezimaltiefe der Blocktabellen. Die Vorberechnung aller sechsstelligen Ziffernsummen kostet \(O(B)\) Zeit. Der Aufbau der Übertragsinformationen für jedes \(c\in[0,C]\) kostet \(O(BC)\) Zeit und dominiert die Vorbereitung.
Die ausgerichteten Blocktabellen arbeiten nur auf dem winzigen Zustandsraum der Größe \(R+1=163\), daher sind ihre Kosten deutlich kleiner als die Konstruktion der Übertragstabellen. Für die eine finale Anfrage benutzen Verdopplung und binäre Suche nur logarithmisch viele Intervallauswertungen, und jede solche Auswertung berührt nur wenige Dezimalblöcke. Der Speicherbedarf wird von den Übertragstabellen dominiert und ist \(O(BC)\).
Dizi şu şekilde tanımlanır:
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
burada \(\sigma(x)\), \(x\)'in ondalık basamakları toplamıdır. Hedef indeks o kadar büyüktür ki her güncellemeyi tek tek simüle etmek mümkün değildir. Bu yüzden uygulamalar, birçok sıradan güncellemeyi bir sonraki taşımaya kadar giden tam geçişler halinde gruplayarak hız kazanır.
Ana gözlem, ondalık basamak toplamının \(10\) kuvvetleri üzerinde temiz biçimde ayrışmasıdır. En alttaki altı basamak ayrı tutulursa yineleme, hızlı değişen bir alt parça ile yavaş değişen bir üst parçaya bölünür. Böylece bir sonraki taşımaya kadar olan tam sıçramalar önceden hesaplanabilir ve bu sıçramalar uzun aralıklarda bileştirilebilir.
Şöyle yazalım:
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
\(\sigma_6(r)\), \(r\)'nin gerekirse başına sıfır eklenmiş altı basamaklı gösteriminin basamak toplamı olsun. \(B\) bir \(10\) kuvveti olduğu için \(q_n\) ile \(r_n\)'nin basamakları birbirine karışmaz; dolayısıyla
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
Böylece tek bir temel güncelleme
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n)$$
biçimine gelir. Alt parça \(B\)'nin altında kalırsa
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)$$
olur. Alt parça \(B\)'ye ulaşır ya da onu geçerse bir taşıma oluşur:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
Hedef hesaplamada üst parça en fazla \(12\) ondalık basamak gerektirdiğinden \(\sigma(q_n)\le 108\) olur. Ayrıca \(\sigma_6(r_n)\le 54\) olduğundan, alt parça bir temel adımda en fazla \(162\) artar. Bu da tek adımda en fazla bir taşıma olabileceği anlamına gelir.
\(q_n\) sabit kaldığı sürece onun basamak toplamı da sabittir. Sabit bir \(c\) için
$$F_c(x)=x+\sigma_6(x)+c$$
fonksiyonunu tanımlayalım. Alt parça \(x\) ile başlarsa, bir sonraki taşıma
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
adet temel güncellemeden sonra gelir; taşıma olduktan hemen sonraki yeni alt parça ise
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B$$
olur. Bunlar yaklaşık değil, tam değerlerdir: \(\tau_c(x)\) gerçekten kaç yineleme adımı geçtiğini sayar, \(\rho_c(x)\) da \(B\) çıkarıldıktan sonraki gerçek kalandır.
Sınırın aşıldığı anda
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108$$
olduğundan, taşıma sonrası kalan her zaman
$$0\le \rho_c(x)\le 162$$
şartını sağlar. Sıkıştırmanın özü budur. Bir sonraki taşımadan önce alt parça \(10^6\)'nın altındaki birçok değeri dolaşabilir; fakat taşımadan hemen sonra her zaman
$$S=\{0,1,2,\dots,162\}$$
küçük kümesinin içine döner. Böylece bir taşıma olayı, \(S\) içindeki bir artıkla başlayıp bilinen sayıda temel adım harcayan ve yine \(S\) içindeki bir artıkta biten makro-adım olarak görülebilir.
Her mevcut üst parça \(h\) için \(c=\sigma(h)\) alalım. O zaman bir taşıma olayı, küçük artık kümesi \(S\) üzerinde \(M_h\) geçişini tanımlar: her \(x\in S\) için yeni artık \(\rho_c(x)\) ve tam maliyet \(\tau_c(x)\) elde edilir.
Eğer üst parça \(h\) ile başlayıp arka arkaya birkaç taşıma yapmak istiyorsak, şu geçişleri bileştirmemiz gerekir:
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
Komşu üst-parça aralıkları için bileşim tam olarak
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w)$$
şeklindedir. Bu yüzden uzun taşıma dizileri, her olayı ayrı ayrı oynamak yerine tekrar kullanılabilir blokların bileşimiyle işlenebilir.
Uzunluğu \(10^d\) olan hizalı bir aralığı düşünelim; örneğin \(2300\) ile \(2399\) arasındaki tüm üst parçalar. Bu aralıktaki bütün sayılar aynı öneki paylaşır, sadece son \(d\) basamak değişir. Basamak toplamı ondalık birleştirme üzerinde ayrıştığı için
$$\sigma(\text{önek}\cdot 10^d+\text{son ek})=\sigma(\text{önek})+\sigma(\text{son ek})$$
olur. Dolayısıyla böyle bir bloğun tüm geçişi yalnızca iki bilgiye bağlıdır: blok uzunluğu \(10^d\) ve sabit önekin basamak toplamı. Uygulamalar bu hizalı ondalık blokların hepsini \(d=12\)'ye kadar önceden kurar. Daha sonra herhangi bir \([u,v)\) aralığı açgözlü biçimde hizalı bloklara ayrılır; böylece uzun bir aralık az sayıda geçiş bileşimiyle değerlendirilebilir.
Elde \(R\) tane temel güncelleme bütçesi kalsın. \(C(m)\), mevcut durumdan başlayarak sonraki \(m\) taşımanın tükettiği temel adım sayısı olsun. Her taşıma en az bir sıradan adım harcadığı için \(C(m)\) sıkı biçimde artandır.
Bu yüzden algoritma
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
değerini önce ikiye katlama, sonra ikili arama ile bulur. Bu \(m^*\) taşıma tek hamlede uygulandıktan sonra kalan bütçe bir sonraki taşımaya yetmez. Böylece son birkaç temel adım, üst parça sabit tutularak doğrudan yürütülür.
Şunu alalım:
$$a=17\cdot 10^6+999995.$$
Burada \(\sigma(17)=8\) ve \(\sigma_6(999995)=50\)'dir. Bir temel güncelleme
$$999995+50+8=1000053$$
verir; dolayısıyla sonraki terim
$$a'=18\cdot 10^6+53$$
olur. Bu tek taşıma olayı yalnızca bir yineleme adımı harcamış ve alt parçayı yeniden küçük \(S\) kümesinin içine getirmiştir. Artık üst parça \(18\) olduğundan basamak toplamı \(9\)'dur. Sonraki taşımadan önce iki temel adım daha atılırsa alt parça
$$53\to 70\to 86$$
şeklinde ilerler; çünkü \(53+\sigma_6(53)+9=53+8+9=70\) ve \(70+\sigma_6(70)+9=70+7+9=86\). İkili aramadan sonra doğrudan tamamlanan kısa kuyruk tam olarak budur.
C++, Python ve Java uygulamaları önce \(0\) ile \(999999\) arasındaki her altı basamaklı değerin basamak toplamını önceden hesaplar. Böylece alt parçadaki güncelleme \(x\mapsto x+\sigma_6(x)+c\), mümkün olan her durum için sabit zamanda yapılabilir.
Daha sonra üst parçanın her olası basamak toplamı \(c\) için, alt parçanın tüm aralığı geriye doğru taranarak bir sonraki taşımaya ulaşmak için gereken kesin sıradan adım sayısı ve taşıma sonrası kalan değer belirlenir. Sonraki bileşim aşaması için yalnızca \(0\) ile \(162\) arasındaki taşıma-sonrası durumlar saklanır; çünkü her taşıma mutlaka bu aralığa döner.
Bunun ardından uygulama, uzunlukları \(1,10,100,\dots,10^{12}\) olan hizalı ondalık aralıklar için geçiş blokları kurar. Her blok, her küçük artık için hem yeni artığı hem de bu aralıktaki ardışık üst parçalar boyunca tüketilen sıradan adım sayısını tutar.
Asıl çözüm aşamasında mevcut değer \(1\)'den başlar. Uygulama kalan adım bütçesi altında kaç taşımanın yapılabileceğini tekrar tekrar sorar, bu soruyu ikiye katlama ve ikili arama ile cevaplar, bulunan aralık geçişini uygular ve sonunda yalnızca çok küçük kalan kuyruğu doğrudan simüle eder. Yöntem baştan sona tamdır; hiçbir yaklaşık hesap yoktur.
\(B=10^6\), uygulamaların kullandığı üst parça basamak toplamı üst sınırı \(C=108\), taşıma sonrası artık sınırı \(R=162\) ve ondalık blok derinliği \(D=12\) olsun. Tüm altı basamaklı basamak toplamlarını önceden hesaplamak \(O(B)\) zaman alır. Her \(c\in[0,C]\) için bir sonraki taşıma bilgisini kurmak \(O(BC)\) zamana mal olur ve ön işleme maliyetine bu kısım hakimdir.
Hizalı blok tabloları yalnızca \(R+1=163\) boyutlu çok küçük bir durum uzayında çalıştığı için bunların maliyeti taşıma tablolarından çok daha düşüktür. Son tek sorgu için ikiye katlama ve ikili arama logaritmik sayıda aralık değerlendirmesi yapar; her değerlendirme de yalnızca az sayıda ondalık bloğa dokunur. Bellek kullanımı taşıma tabloları tarafından belirlenir ve \(O(BC)\) mertebesindedir.
La sucesión está definida por
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
donde \(\sigma(x)\) es la suma de dígitos decimales de \(x\). El índice objetivo es tan grande que no sirve simular todas las actualizaciones una por una. Por eso las implementaciones aceleran el proceso agrupando muchos pasos ordinarios en transiciones exactas de un acarreo al siguiente.
La observación central es que la suma de dígitos decimal se separa limpiamente en potencias de \(10\). Si se aíslan los seis últimos dígitos, la recurrencia se divide en una parte baja que cambia rápido y una parte alta que cambia lentamente. Esa separación permite precomputar saltos exactos hasta el siguiente acarreo y después componer esos saltos en intervalos largos.
Escribimos
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
Sea \(\sigma_6(r)\) la suma de dígitos del bloque decimal de seis cifras de \(r\), permitiendo ceros a la izquierda. Como \(B\) es una potencia de \(10\), los dígitos de \(q_n\) y \(r_n\) no interfieren entre sí, de modo que
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
Por tanto, una actualización elemental toma la forma
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
Si la parte baja permanece por debajo de \(B\), entonces
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
Si la parte baja alcanza o supera \(B\), aparece exactamente un acarreo:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
Para el cálculo objetivo, la parte alta nunca necesita más de \(12\) cifras decimales, así que \(\sigma(q_n)\le 108\). Además, \(\sigma_6(r_n)\le 54\), de modo que una actualización elemental aumenta la parte baja en como mucho \(162\). En consecuencia, un solo paso no puede producir más de un acarreo.
Mientras \(q_n\) no cambie, su suma de dígitos permanece constante. Para un valor fijo \(c\), definimos
$$F_c(x)=x+\sigma_6(x)+c.$$
Si la parte baja empieza en \(x\), el siguiente acarreo ocurre tras
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
actualizaciones elementales, y la nueva parte baja justo después de ese acarreo es
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
Estas cantidades son exactas: \(\tau_c(x)\) cuenta cuántos pasos reales de la recurrencia se consumen antes de cruzar el umbral \(B\), y \(\rho_c(x)\) es el resto verdadero después de restar \(B\).
En el instante del cruce tenemos
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
así que el resto posterior al acarreo siempre satisface
$$0\le \rho_c(x)\le 162.$$
Aquí está la compresión esencial. Antes del siguiente acarreo, la parte baja puede recorrer muchos valores por debajo de \(10^6\), pero inmediatamente después de un acarreo siempre cae dentro del conjunto pequeño
$$S=\{0,1,2,\dots,162\}.$$
Así, un evento de acarreo puede verse como un macro-paso que arranca en un resto de \(S\), consume un número conocido de actualizaciones elementales y termina otra vez en un resto de \(S\).
Para cada parte alta actual \(h\), tomamos \(c=\sigma(h)\). Entonces un evento de acarreo induce una transición \(M_h\) sobre el conjunto pequeño \(S\): para cada \(x\in S\), la transición devuelve el nuevo resto \(\rho_c(x)\) y el coste exacto \(\tau_c(x)\).
Si queremos procesar varios acarreos seguidos a partir de la parte alta \(h\), debemos componer las transiciones
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
Para intervalos adyacentes de valores altos, la composición es exacta:
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
Eso permite tratar rachas largas de acarreos componiendo bloques reutilizables, en lugar de reproducir cada evento por separado.
Consideremos un intervalo alineado de longitud \(10^d\), por ejemplo todos los valores altos entre \(2300\) y \(2399\). Todos comparten el mismo prefijo y solo cambian los últimos \(d\) dígitos. Como la suma de dígitos se separa sobre la concatenación decimal, se cumple
$$\sigma(\text{prefijo}\cdot 10^d+\text{sufijo})=\sigma(\text{prefijo})+\sigma(\text{sufijo}).$$
Por tanto, la transición completa de uno de estos bloques depende solo de dos datos: la longitud \(10^d\) y la suma de dígitos del prefijo fijo. Las implementaciones precomputan todos esos bloques alineados hasta \(d=12\). Luego cualquier intervalo \([u,v)\) se descompone de forma voraz en bloques alineados, de modo que un tramo largo se evalúa con muy pocas composiciones.
Supongamos que quedan \(R\) actualizaciones elementales disponibles. Sea \(C(m)\) el número de actualizaciones elementales consumidas por los siguientes \(m\) acarreos a partir del estado actual. Como cada acarreo cuesta al menos un paso ordinario, \(C(m)\) es estrictamente creciente.
Entonces el algoritmo busca
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
primero duplicando el valor de prueba y luego aplicando búsqueda binaria. Una vez ejecutados esos \(m^*\) acarreos de golpe, el presupuesto restante ya no alcanza para el siguiente acarreo. Los últimos pocos pasos elementales se hacen entonces de manera directa con la parte alta fija.
Tomemos
$$a=17\cdot 10^6+999995.$$
Entonces \(\sigma(17)=8\) y \(\sigma_6(999995)=50\). Una actualización elemental da
$$999995+50+8=1000053,$$
de modo que el siguiente término es
$$a'=18\cdot 10^6+53.$$
Ese único evento de acarreo ha consumido un paso ordinario de la recurrencia y ha devuelto la parte baja al pequeño conjunto \(S\). Ahora la parte alta es \(18\), así que su suma de dígitos vale \(9\). Si se realizan dos actualizaciones elementales más antes del siguiente acarreo, la parte baja evoluciona como
$$53\to 70\to 86,$$
porque \(53+\sigma_6(53)+9=53+8+9=70\) y \(70+\sigma_6(70)+9=70+7+9=86\). Esa es exactamente la clase de cola corta que el algoritmo remata de forma directa tras la fase de saltos entre acarreos.
Las implementaciones en C++, Python y Java empiezan precomputando la suma de dígitos de cada valor de seis cifras entre \(0\) y \(999999\). Así, la actualización de la parte baja \(x\mapsto x+\sigma_6(x)+c\) queda disponible en tiempo constante para cualquier estado posible.
Después, para cada suma de dígitos posible \(c\) de la parte alta, la implementación recorre hacia atrás todo el rango de la parte baja y determina el número exacto de pasos ordinarios necesarios para alcanzar el siguiente acarreo, junto con el resto posterior a ese acarreo. Para la fase posterior de composición solo hace falta conservar los estados de \(0\) a \(162\), porque todo acarreo termina dentro de ese intervalo.
A continuación, la implementación construye bloques de transición para intervalos decimales alineados de longitudes \(1,10,100,\dots,10^{12}\). Cada bloque almacena, para cada resto pequeño, tanto el nuevo resto como el número de pasos ordinarios consumidos a lo largo de todo ese intervalo de valores altos consecutivos.
En la fase final de resolución, el valor actual empieza en \(1\). La implementación pregunta repetidamente cuántos acarreos caben en el presupuesto de pasos restante, responde con duplicación y búsqueda binaria, aplica la transición del intervalo correspondiente y termina la pequeña cola restante de forma directa. El método es exacto de principio a fin; no hay ninguna aproximación.
Sean \(B=10^6\), \(C=108\) la suma máxima de dígitos de la parte alta usada por las implementaciones, \(R=162\) la cota del resto tras un acarreo y \(D=12\) la profundidad máxima de los bloques decimales. Precomputar todas las sumas de dígitos de seis cifras cuesta \(O(B)\) tiempo. Construir la información del siguiente acarreo para cada \(c\in[0,C]\) cuesta \(O(BC)\) y domina el preprocesamiento.
Las tablas de bloques alineados trabajan solo sobre el espacio de estados diminuto de tamaño \(R+1=163\), por lo que su coste es mucho menor que el de las tablas de acarreo. Para la consulta final, la duplicación y la búsqueda binaria usan un número logarítmico de evaluaciones de intervalos, y cada evaluación toca solo unos pocos bloques decimales. La memoria está dominada por las tablas de acarreo y es \(O(BC)\).
这个数列定义为
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
其中 \(\sigma(x)\) 表示 \(x\) 的十进制数位和。目标下标极大，无法把所有递推步骤逐项模拟完，因此实现采用的是“精确跳跃”思路：把很多普通更新合并成一次从当前进位跳到下一次进位的宏观转移。
核心观察是：在 \(10\) 的幂处分块后，十进制数位和可以自然拆开。如果把最低六位单独拿出来，递推就会分解成一个变化很快的低位部分和一个变化很慢的高位部分。这样既可以预处理“到下一次进位还需要多少步”，也可以把这些精确的进位跳跃在很长的区间上进行函数复合。
记
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
设 \(\sigma_6(r)\) 表示 \(r\) 按六位十进制写出时的数位和，允许前导零。由于 \(B\) 是 \(10\) 的幂，高位 \(q_n\) 的数字和低位 \(r_n\) 的数字互不干扰，因此
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
于是一次基础递推可写成
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
如果低位仍然小于 \(B\)，那么
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
如果低位达到或超过 \(B\)，就发生一次进位：
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
对目标计算而言，高位部分最多只需要 \(12\) 位十进制数字，所以 \(\sigma(q_n)\le 108\)。而六位数位和最多为 \(54\)，因此一次基础更新对低位的增量最多只有 \(162\)。这保证了单次更新至多发生一次进位，不会跨过多个 \(10^6\) 区间。
只要 \(q_n\) 不变，它的数位和就是常数。对固定的 \(c\)，定义
$$F_c(x)=x+\sigma_6(x)+c.$$
若当前低位为 \(x\)，那么到下一次进位所需的基础步数是
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\},$$
而进位完成后的新低位是
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
这里没有任何近似。\(\tau_c(x)\) 就是实际递推中从 \(x\) 出发到第一次越过边界 \(B\) 需要的更新次数；\(\rho_c(x)\) 则是越界后减去 \(B\) 得到的真实余数。也就是说，在高位数位和固定的阶段里，可以把很多细小的递推步骤压缩成一次精确的“下一进位跳跃”。
越过边界的那一刻有
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
因此进位后的余数一定满足
$$0\le \rho_c(x)\le 162.$$
这一步是整个算法的压缩关键。虽然下一次进位发生之前，低位可能在 \(0\) 到 \(999999\) 之间走过大量不同的值，但每次进位刚结束时，它一定重新落入很小的集合
$$S=\{0,1,2,\dots,162\}.$$
所以从“一个进位结束”到“下一个进位结束”的过程，可以视为一个宏步骤：它从 \(S\) 中某个状态开始，消耗一个精确已知的基础步数，然后又回到 \(S\) 中另一个状态。这样，真正需要在宏观层面记录的低位状态只有 \(163\) 种。
对当前高位 \(h\)，令 \(c=\sigma(h)\)。那么一次进位事件就在小状态集合 \(S\) 上定义了一个转移 \(M_h\)：对每个 \(x\in S\)，这个转移给出新的低位余数 \(\rho_c(x)\)，以及为了触发这次进位所消耗的基础递推步数 \(\tau_c(x)\)。
如果从高位 \(h\) 开始连续处理多个进位，那么要依次复合
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
这些转移。对相邻区间，复合关系是完全精确的：
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
因此，只要把若干连续的高位值打包成可复用的区间转移块，就可以把很长的一串进位事件一次性处理，而不必逐个展开。
考虑一个长度为 \(10^d\) 的对齐区间，例如高位从 \(2300\) 到 \(2399\)。这个区间中的所有数都有相同的前缀，只是最后 \(d\) 位不同。由于十进制拼接下数位和满足
$$\sigma(\text{前缀}\cdot 10^d+\text{后缀})=\sigma(\text{前缀})+\sigma(\text{后缀}),$$
整个区间的转移就只依赖两件事：块长度 \(10^d\) 和固定前缀的数位和。实现会把所有这样的对齐十进制块一直预处理到 \(d=12\)。这样，对于任意区间 \([u,v)\)，只需要把它贪心地拆成少量对齐块，再把这些块对应的转移按顺序复合起来，就能得到整段区间的总效果。
设还剩下 \(R\) 次基础递推更新的预算。记 \(C(m)\) 为从当前状态出发，连续执行接下来 \(m\) 次进位事件所消耗的基础步数。由于每次进位至少要消耗一步普通递推，所以 \(C(m)\) 是严格递增的。
于是算法寻找
$$m^*=\max\{m\ge 0:C(m)\le R\}.$$
做法是先不断倍增试探上界，再在最后的区间内进行二分搜索。找到 \(m^*\) 后，就把这 \(m^*\) 次进位整体应用掉。此时剩余预算已经不足以再到达下一次进位，因此最后只需要在高位保持不变的前提下，直接执行很少几个基础更新即可。
取
$$a=17\cdot 10^6+999995.$$
这时 \(\sigma(17)=8\)，而 \(\sigma_6(999995)=50\)。进行一次基础更新后，低位变化为
$$999995+50+8=1000053,$$
所以新的一项变成
$$a'=18\cdot 10^6+53.$$
也就是说，一次进位事件消耗了一个普通递推步骤，并把低位重新压回小集合 \(S\) 中。现在高位是 \(18\)，它的数位和等于 \(9\)。如果之后在下一次进位前再直接执行两个基础更新，那么低位依次变成
$$53\to 70\to 86,$$
因为 \(53+\sigma_6(53)+9=53+8+9=70\)，而 \(70+\sigma_6(70)+9=70+7+9=86\)。这正是算法在完成大块跳跃以后最后直接处理的那种短尾巴。
C++、Python 和 Java 实现首先预处理 \(0\) 到 \(999999\) 所有六位数的数位和。这样一来，低位更新 \(x\mapsto x+\sigma_6(x)+c\) 对任何可能状态都能在常数时间内完成。
接着，对高位数位和的每个可能取值 \(c\)，实现都会从大到小扫描整个低位范围，求出“离下一次进位还需要多少个普通更新”以及“进位后余数是多少”。虽然这个扫描覆盖了完整的六位区间，但真正保留下来用于后续宏观复合的，只是 \(0\) 到 \(162\) 这 \(163\) 个进位后状态，因为每次进位都会回到这里。
然后，实现会构造长度为 \(1,10,100,\dots,10^{12}\) 的十进制对齐块转移。每个块都记录：如果从某个小余数出发，穿过这一整段连续高位值以后，会落到哪个新余数，并且总共消耗多少次基础递推更新。
真正求解时，当前值从 \(1\) 开始。实现不断询问“剩余预算下最多还能整体跳过多少次进位”，通过倍增和二分搜索回答这个问题，应用相应的大块转移，然后再把最后那一小段无法再触发下一次进位的尾部更新直接跑完。整个过程始终是精确的，不存在任何近似。
设 \(B=10^6\)，设实现中使用的高位数位和上界为 \(C=108\)，进位后余数上界为 \(R=162\)，十进制块深度上界为 \(D=12\)。预处理全部六位数数位和需要 \(O(B)\) 时间。对每个 \(c\in[0,C]\) 构造“下一次进位”信息需要 \(O(BC)\) 时间，这是预处理阶段的主导部分。
十进制对齐块只在大小为 \(R+1=163\) 的小状态空间上工作，因此这部分的代价远小于进位表本身。对于最终单次查询，倍增和二分只需要对区间做对数次评估，而每次区间评估又只会触及少量对齐块。内存消耗主要由进位表决定，因此为 \(O(BC)\)。
Последовательность задаётся формулой
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
где \(\sigma(x)\) означает сумму десятичных цифр числа \(x\). Искомый индекс настолько велик, что прямое моделирование всех шагов недопустимо. Поэтому реализации ускоряют вычисление, объединяя множество обычных обновлений в точные переходы от одного переноса к следующему.
Главная идея состоит в том, что сумма десятичных цифр хорошо раскладывается по степеням \(10\). Если отделить последние шесть цифр, рекурсия распадается на быстро меняющуюся младшую часть и медленно меняющуюся старшую часть. После этого можно заранее вычислять точные прыжки до следующего переноса и затем компонировать такие прыжки на длинных интервалах.
Положим
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
Пусть \(\sigma_6(r)\) обозначает сумму цифр шестизначной десятичной записи числа \(r\) с разрешёнными ведущими нулями. Поскольку \(B\) является степенью \(10\), цифры \(q_n\) и \(r_n\) не смешиваются, поэтому
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
Отсюда одно элементарное обновление имеет вид
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
Если младшая часть остаётся меньше \(B\), то
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
Если же младшая часть достигает \(B\) или превосходит его, происходит ровно один перенос:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
Для целевого вычисления старшая часть не требует более \(12\) десятичных цифр, значит \(\sigma(q_n)\le 108\). Кроме того, \(\sigma_6(r_n)\le 54\), так что младшая часть за один элементарный шаг увеличивается не более чем на \(162\). Следовательно, за один шаг может возникнуть не более одного переноса.
Пока \(q_n\) не меняется, его сумма цифр постоянна. Для фиксированного значения \(c\) определим
$$F_c(x)=x+\sigma_6(x)+c.$$
Если младшая часть начинается с \(x\), то следующий перенос произойдёт через
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
элементарных обновлений, а младшая часть сразу после переноса будет равна
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
Это точные величины: \(\tau_c(x)\) считает реальное число шагов рекурсии до первого пересечения границы \(B\), а \(\rho_c(x)\) является истинным остатком после вычитания \(B\).
В момент пересечения границы имеем
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
поэтому остаток после переноса всегда удовлетворяет неравенству
$$0\le \rho_c(x)\le 162.$$
Именно здесь происходит ключевое сжатие состояния. До следующего переноса младшая часть может проходить через большое количество значений ниже \(10^6\), но сразу после переноса она всегда лежит в малом множестве
$$S=\{0,1,2,\dots,162\}.$$
Значит, событие переноса можно рассматривать как макро-шаг: он стартует из некоторого остатка в \(S\), тратит точно известное число элементарных шагов и снова попадает в некоторый остаток из \(S\).
Для каждого текущего значения старшей части \(h\) положим \(c=\sigma(h)\). Тогда один перенос задаёт переход \(M_h\) на малом множестве остатков \(S\): для каждого \(x\in S\) этот переход возвращает новый остаток \(\rho_c(x)\) и точную стоимость \(\tau_c(x)\).
Если нужно обработать подряд несколько переносов, начиная со старшей части \(h\), то требуется композиция переходов
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
Для соседних интервалов значений старшей части композиция точна:
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
Это позволяет обрабатывать длинные последовательности переносов через композицию переиспользуемых блоков, а не проигрывать каждый перенос отдельно.
Рассмотрим выровненный интервал длины \(10^d\), например все значения старшей части от \(2300\) до \(2399\). У всех таких чисел одинаковый префикс, а меняются только последние \(d\) цифр. Поскольку сумма цифр раскладывается по десятичной склейке, имеем
$$\sigma(\text{префикс}\cdot 10^d+\text{суффикс})=\sigma(\text{префикс})+\sigma(\text{суффикс}).$$
Следовательно, полный переход для такого блока зависит только от двух параметров: длины блока \(10^d\) и суммы цифр фиксированного префикса. Реализации заранее строят все такие выровненные десятичные блоки вплоть до \(d=12\). После этого любой интервал \([u,v)\) жадно раскладывается на небольшое число выровненных блоков, и длинный диапазон вычисляется через малое число композиций переходов.
Пусть осталось \(R\) элементарных обновлений. Обозначим через \(C(m)\) число элементарных шагов, которое требуется для следующих \(m\) переносов из текущего состояния. Поскольку каждый перенос требует как минимум одного обычного шага, функция \(C(m)\) строго возрастает.
Поэтому алгоритм ищет
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
сначала удвоением верхней границы, а затем двоичным поиском. После того как эти \(m^*\) переносов применены одним действием, оставшегося бюджета уже недостаточно для следующего переноса. Последние несколько элементарных шагов выполняются напрямую при фиксированной старшей части.
Возьмём
$$a=17\cdot 10^6+999995.$$
Тогда \(\sigma(17)=8\), а \(\sigma_6(999995)=50\). Одно элементарное обновление даёт
$$999995+50+8=1000053,$$
поэтому следующий член равен
$$a'=18\cdot 10^6+53.$$
Это событие переноса потратило ровно один шаг рекурсии и вернуло младшую часть в малое множество \(S\). Теперь старшая часть равна \(18\), значит её сумма цифр равна \(9\). Если до следующего переноса выполнить ещё два элементарных шага, младшая часть изменится так:
$$53\to 70\to 86,$$
потому что \(53+\sigma_6(53)+9=53+8+9=70\) и \(70+\sigma_6(70)+9=70+7+9=86\). Именно такие короткие хвосты алгоритм досчитывает напрямую после фазы крупных прыжков.
Реализации на C++, Python и Java сначала заранее вычисляют сумму цифр для каждого шестизначного значения от \(0\) до \(999999\). Благодаря этому обновление младшей части \(x\mapsto x+\sigma_6(x)+c\) выполняется за константное время для любого допустимого состояния.
Затем для каждого возможного значения \(c\), равного сумме цифр старшей части, реализация проходит весь диапазон младшей части в обратном порядке и определяет точное число обычных шагов до следующего переноса, а также остаток после этого переноса. Для последующей композиции нужно сохранить только состояния от \(0\) до \(162\), потому что каждый перенос обязательно заканчивается в этом интервале.
После этого строятся блоки переходов для выровненных десятичных интервалов длины \(1,10,100,\dots,10^{12}\). Каждый блок хранит для каждого малого остатка и новый остаток, и число обычных шагов, потраченных на прохождение всего интервала последовательных значений старшей части.
В фазе окончательного вычисления текущее значение начинается с \(1\). Реализация многократно спрашивает, сколько переносов можно ещё позволить при оставшемся бюджете шагов, отвечает на этот вопрос с помощью удвоения и двоичного поиска, применяет найденный интервальный переход и затем досчитывает очень маленький оставшийся хвост напрямую. Метод остаётся точным на каждом этапе; никаких приближений нет.
Пусть \(B=10^6\), \(C=108\) — максимальная сумма цифр старшей части, используемая реализациями, \(R=162\) — верхняя граница остатка после переноса, а \(D=12\) — максимальная глубина десятичных блоков. Предвычисление всех шестизначных сумм цифр требует \(O(B)\) времени. Построение информации о следующем переносе для всех \(c\in[0,C]\) требует \(O(BC)\) времени и доминирует в подготовительном этапе.
Выровненные блоки работают только на маленьком пространстве состояний размера \(R+1=163\), поэтому их стоимость намного меньше стоимости самих таблиц переносов. Для единственного итогового запроса удвоение и двоичный поиск используют логарифмическое число оценок интервалов, а каждая такая оценка затрагивает лишь небольшое число десятичных блоков. Память определяется таблицами переносов и имеет порядок \(O(BC)\).
تُعرَّف المتتالية بالعلاقة
$$a_1=1,\qquad a_{n+1}=a_n+\sigma(a_n),$$
حيث تمثل \(\sigma(x)\) مجموع الأرقام العشرية للعدد \(x\). الفهرس المطلوب ضخم جدًا، ولذلك فإن تنفيذ جميع الخطوات واحدةً تلو الأخرى غير عملي. لهذا تعتمد التطبيقات على تجميع عدد كبير من التحديثات العادية في انتقالات دقيقة من حملٍ إلى الحمل الذي يليه.
الفكرة الأساسية هي أن مجموع الأرقام في النظام العشري ينفصل بصورة طبيعية عند قوى العدد \(10\). فإذا عزلنا آخر ست خانات، تنقسم العلاقة التكرارية إلى جزء منخفض سريع التغيّر وجزء مرتفع بطيء التغيّر. وعندها يمكن حساب قفزات دقيقة حتى الحمل التالي مسبقًا، ثم تركيب هذه القفزات على فترات طويلة.
لنكتب
$$B=10^6,\qquad a_n=Bq_n+r_n,\qquad 0\le r_n \lt B.$$
ولتكن \(\sigma_6(r)\) مجموع أرقام التمثيل العشري ذي الست خانات للعدد \(r\) مع السماح بالأصفار البادئة. بما أن \(B\) قوة للعدد \(10\)، فإن أرقام \(q_n\) وأرقام \(r_n\) لا تتداخل، ومن ثم
$$\sigma(a_n)=\sigma(q_n)+\sigma_6(r_n).$$
وبالتالي تصبح خطوة التحديث الأساسية
$$a_{n+1}=Bq_n+r_n+\sigma(q_n)+\sigma_6(r_n).$$
إذا بقي الجزء المنخفض أصغر من \(B\)، فلدينا
$$q_{n+1}=q_n,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n).$$
أما إذا بلغ الجزء المنخفض \(B\) أو تجاوزه، فيحدث حمل واحد بالضبط:
$$q_{n+1}=q_n+1,\qquad r_{n+1}=r_n+\sigma_6(r_n)+\sigma(q_n)-B.$$
في الحساب المستهدف لا يحتاج الجزء المرتفع إلى أكثر من \(12\) خانة عشرية، ولذلك \(\sigma(q_n)\le 108\). كذلك لدينا \(\sigma_6(r_n)\le 54\)، وهذا يعني أن الجزء المنخفض يزداد في خطوة أساسية واحدة بمقدار لا يتجاوز \(162\). وبالتالي لا يمكن لخطوة واحدة أن تُنتج أكثر من حمل واحد.
طالما أن \(q_n\) ثابت، فإن مجموع أرقامه ثابت أيضًا. لقيمة ثابتة \(c\)، نعرّف
$$F_c(x)=x+\sigma_6(x)+c.$$
إذا بدأ الجزء المنخفض من القيمة \(x\)، فإن الحمل التالي يحدث بعد
$$\tau_c(x)=\min\{t\ge 1:F_c^{(t)}(x)\ge B\}$$
من التحديثات الأساسية، ويكون الجزء المنخفض الجديد مباشرةً بعد ذلك الحمل هو
$$\rho_c(x)=F_c^{(\tau_c(x))}(x)-B.$$
هذه مقادير دقيقة تمامًا: فالقيمة \(\tau_c(x)\) تعدّ عدد خطوات التكرار الحقيقية اللازمة لتجاوز الحد \(B\)، أما \(\rho_c(x)\) فهي الباقي الفعلي بعد طرح \(B\).
في لحظة التجاوز يكون لدينا
$$B\le F_c^{(\tau_c(x))}(x)\le B+54+108,$$
ومن ثم فإن الباقي بعد الحمل يحقق دائمًا
$$0\le \rho_c(x)\le 162.$$
هذه هي خطوة الضغط الأساسية في الخوارزمية. صحيح أن الجزء المنخفض قد يمر قبل الحمل التالي عبر عدد كبير من القيم الأصغر من \(10^6\)، لكنه بعد كل حمل يعود فورًا إلى المجموعة الصغيرة
$$S=\{0,1,2,\dots,162\}.$$
ولهذا يمكن النظر إلى حدث الحمل بوصفه خطوة كبرى تبدأ من باقٍ داخل \(S\)، وتستهلك عددًا معلومًا بدقة من الخطوات الأساسية، ثم تنتهي من جديد عند باقٍ داخل \(S\).
لكل قيمة حالية للجزء المرتفع \(h\)، نضع \(c=\sigma(h)\). عندئذٍ يحدد حدث الحمل انتقالًا \(M_h\) على مجموعة البواقي الصغيرة \(S\): لكل \(x\in S\) يعطي هذا الانتقال الباقي الجديد \(\rho_c(x)\) والكلفة الدقيقة \(\tau_c(x)\).
إذا أردنا معالجة عدة أحمال متتالية بدءًا من الجزء المرتفع \(h\)، فعلينا تركيب الانتقالات
$$M_h,\ M_{h+1},\ M_{h+2},\ \dots$$
وبالنسبة إلى الفترات المتجاورة من قيم الجزء المرتفع، يكون التركيب دقيقًا تمامًا:
$$\mathcal{T}_{[u,w)}=\mathcal{T}_{[v,w)}\circ \mathcal{T}_{[u,v)}\qquad (u\le v\le w).$$
وهذا يسمح بالتعامل مع سلاسل طويلة من الأحمال عن طريق تركيب كتل قابلة لإعادة الاستخدام، بدلًا من تتبع كل حمل على حدة.
لننظر إلى فترة مصطفّة طولها \(10^d\)، مثل جميع قيم الجزء المرتفع من \(2300\) إلى \(2399\). كل الأعداد في هذه الفترة تشترك في بادئة ثابتة، ولا تختلف إلا في آخر \(d\) خانات. وإذا رمزنا إلى البادئة بالرمز \(p\) وإلى اللاحقة بالرمز \(s\)، فإن مجموع الأرقام ينفصل كما يلي:
$$\sigma(p\cdot 10^d+s)=\sigma(p)+\sigma(s).$$
لذلك فإن انتقال مثل هذه الكتلة يعتمد فقط على معلومتين: طول الكتلة \(10^d\) ومجموع أرقام البادئة الثابتة. تقوم التطبيقات ببناء جميع هذه الكتل العشرية المصطفّة حتى \(d=12\). وبعد ذلك تُجزَّأ أي فترة \([u,v)\) بطريقة جشعة إلى عدد صغير من الكتل المصطفّة، وبذلك يمكن تقييم فترة طويلة عبر عدد قليل من عمليات التركيب.
لنفرض أن لدينا \(R\) من التحديثات الأساسية المتبقية. ولتكن \(C(m)\) هي عدد التحديثات الأساسية التي تستهلكها الأحمال \(m\) التالية انطلاقًا من الحالة الحالية. بما أن كل حمل يستهلك على الأقل خطوةً عادية واحدة، فإن \(C(m)\) دالة متزايدة بدقة.
لذلك تبحث الخوارزمية عن
$$m^*=\max\{m\ge 0:C(m)\le R\}$$
أولًا بالمضاعفة للعثور على حد علوي مناسب، ثم بالبحث الثنائي داخل ذلك النطاق. بعد تنفيذ هذه الأحمال \(m^*\) دفعةً واحدة، لا يعود ما تبقى من الميزانية كافيًا للوصول إلى الحمل التالي. وعندها تُنفَّذ الخطوات الأساسية القليلة الأخيرة مباشرةً مع بقاء الجزء المرتفع ثابتًا.
لنأخذ
$$a=17\cdot 10^6+999995.$$
عندئذٍ \(\sigma(17)=8\) و\(\sigma_6(999995)=50\). تعطي خطوة أساسية واحدة
$$999995+50+8=1000053,$$
ومن ثم يصبح الحد التالي
$$a'=18\cdot 10^6+53.$$
لقد استهلك هذا الحمل خطوة تكرارية عادية واحدة فقط، وأعاد الجزء المنخفض إلى المجموعة الصغيرة \(S\). والآن صار الجزء المرتفع \(18\)، وبالتالي فإن مجموع أرقامه يساوي \(9\). إذا نُفِّذت بعد ذلك خطوتان أساسيتان إضافيتان قبل الحمل التالي، فإن الجزء المنخفض يتطور هكذا
$$53\to 70\to 86,$$
لأن \(53+\sigma_6(53)+9=53+8+9=70\)، و\(70+\sigma_6(70)+9=70+7+9=86\). وهذا هو النوع نفسه من الذيل القصير الذي تُكمله الخوارزمية مباشرةً بعد مرحلة القفزات الكبيرة.
تبدأ تطبيقات C++ وPython وJava بحساب مجموع الأرقام مسبقًا لكل قيمة سداسية الخانات من \(0\) إلى \(999999\). وهكذا تصبح عملية تحديث الجزء المنخفض \(x\mapsto x+\sigma_6(x)+c\) متاحة بزمن ثابت لأي حالة ممكنة.
بعد ذلك، ولكل قيمة محتملة \(c\) تمثل مجموع أرقام الجزء المرتفع، تقوم الشيفرة بالمرور على المجال الكامل للجزء المنخفض من الأعلى إلى الأدنى، وتحدد العدد الدقيق من الخطوات العادية اللازمة للوصول إلى الحمل التالي، وكذلك الباقي بعد ذلك الحمل. ولأجل التركيب اللاحق لا حاجة إلى الاحتفاظ إلا بالحالات من \(0\) إلى \(162\)، لأن كل حمل ينتهي داخل هذا المجال.
ثم تُبنى كتل انتقال لفترات عشرية مصطفّة بأطوال \(1,10,100,\dots,10^{12}\). تخزّن كل كتلة، لكل باقٍ صغير، الباقي الجديد وعدد الخطوات العادية المستهلكة على امتداد تلك الفترة الكاملة من قيم الجزء المرتفع المتتالية.
في مرحلة الحل الفعلية تبدأ القيمة الحالية من \(1\). وتكرر الشيفرة السؤال التالي: كم عدد الأحمال التي يمكن تنفيذها ضمن الميزانية المتبقية؟ ثم تجيب عن ذلك بالمضاعفة والبحث الثنائي، وتطبّق انتقال الفترة الناتجة، وأخيرًا تنفذ الذيل الصغير المتبقي مباشرةً. المنهج دقيق بالكامل في جميع مراحله، ولا يعتمد على أي تقريب.
لنكتب \(B=10^6\)، و\(C=108\) حدًا أعلى لمجموع أرقام الجزء المرتفع المستخدم في التطبيقات، و\(R=162\) حدًا أعلى للباقي بعد الحمل، و\(D=12\) عمق الكتل العشرية. حساب جميع مجاميع الأرقام للأعداد ذات الست خانات يحتاج إلى زمن \(O(B)\). أما بناء معلومات الحمل التالي لكل \(c\in[0,C]\) فيكلف \(O(BC)\) زمنًا، وهو الجزء المسيطر من التهيئة المسبقة.
كتل الفترات المصطفّة تعمل فقط على فضاء حالات صغير جدًا حجمه \(R+1=163\)، لذلك تكون كلفتها أصغر بكثير من كلفة جداول الحمل نفسها. وفي الاستعلام النهائي الواحد، تستخدم المضاعفة والبحث الثنائي عددًا لوغاريتميًا من تقييمات الفترات، وكل تقييم لا يلمس إلا عددًا صغيرًا من الكتل العشرية. أمّا استهلاك الذاكرة فتسيطر عليه جداول الحمل، ولذلك يكون من المرتبة \(O(BC)\).