The number in this problem is the Stoneham number
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
We need the 10 consecutive decimal digits that start at position \(n=10^{16}\). If we define
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
then \(A(n)\) is exactly that 10-digit block, with leading zeros allowed. The whole task is therefore a digit-extraction problem: compute \(A(10^{16})\) without expanding the decimal expansion out to the \(10^{16}\)-th place.
The implementations turn the infinite Stoneham series into a short exact computation. The key facts are that only finitely many terms can affect the integer part after shifting by \(10^{n+9}\), and that each surviving term can be recovered from one modular exponentiation.
Multiplying by \(10^{n+9}\) moves the digits at positions \(n\) through \(n+9\) into the last 10 digits of an integer:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
Taking the floor removes everything strictly after the \((n+9)\)-th decimal place, and reducing modulo \(10^{10}\) keeps exactly the block we want.
Let \(L\) be the largest integer satisfying
$$3^L\le n+9.$$
For every \(k>L\), we have \(3^k\ge n+10\), hence
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
Therefore the omitted tail obeys
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
Since the discarded part is strictly less than \(1\), it cannot affect the floor. So
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
For the actual input \(n=10^{16}\), this means only \(L=33\) terms survive.
For each \(1\le k\le L\), write
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
Then
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$$
and summing over all \(k\) gives
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
The quotient part contributes directly to the answer modulo \(10^{10}\). The remainder part produces a carry, because several fractional pieces can add up to at least \(1\).
All denominators are powers of \(3\), so they merge naturally:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
If we define
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
then
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
This is exact: the implementations store every remainder, build the numerator \(\sum r_k 3^{L-k}\), and divide once by \(3^L\).
Computing \(10^{n+9-3^k}\) itself would be impossible, but we do not need the full integer. Define the residue
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
Because
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
for some integer \(t_k\), dividing by \(3^k\) yields
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
So the only data we actually need are obtained from \(s_k\):
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
That is why one modular exponentiation per term is enough.
Here \(n+9=109\), so \(L=4\) because \(3^4=81\le 109\lt 243=3^5\). Therefore
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
For these four denominators, the residue modulo \(3^k 10^{10}\) is \(10^{10}\), so the quotient contributions are
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
The corresponding remainders are
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
Hence the carry numerator is
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
so \(c=\lfloor 76/81\rfloor=0\). Summing the quotient parts gives
$$3333333333+1111111111+370370370+123456790=4938271604.$$
Thus the 10-digit block beginning at position \(100\) is \(4938271604\), which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations follow the same structure. First they generate the powers \(3,9,27,\dots\) up to \(n+9\), which determines the last relevant index \(L\). Then, for each surviving term, they compute \(10^{n+9-3^k}\bmod(3^k 10^{10})\) with fast modular exponentiation.
From that residue they extract two values: the last 10 digits of the quotient contribution \(\left\lfloor s_k/3^k\right\rfloor\), and the exact remainder \(s_k\bmod 3^k\). The quotient pieces are accumulated modulo \(10^{10}\), while the remainders are stored. After the loop, the implementation forms the single numerator \(\sum r_k 3^{L-k}\), divides by \(3^L\) to obtain the exact carry \(c\), adds that carry to the accumulated quotient sum, and formats the result as a zero-padded 10-digit block.
Let \(L=\lfloor\log_3(n+9)\rfloor\). There are exactly \(L\) relevant terms, and each one requires one modular exponentiation by repeated squaring. That costs \(O(\log n)\) modular multiplications on integers of bit length \(O(\log n)\), so the total running time is \(O(L\log n\,M(\log n))\), where \(M\) is the cost of big-integer multiplication. The memory usage is \(O(L)\), coming from the stored powers of \(3\) and the remainder list.
Die Zahl in dieser Aufgabe ist die Stoneham-Zahl
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
Gesucht sind die 10 aufeinanderfolgenden Dezimalstellen ab Position \(n=10^{16}\). Definiert man
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
dann ist \(A(n)\) genau dieser 10-stellige Block, gegebenenfalls mit führenden Nullen. Das Problem ist also ein Ziffernextraktionsproblem: Berechne \(A(10^{16})\), ohne die Dezimalentwicklung bis zur Stelle \(10^{16}\) wirklich auszuschreiben.
Die Implementierungen verwandeln die unendliche Stoneham-Reihe in eine kurze exakte Rechnung. Entscheidend ist, dass nach der Verschiebung mit \(10^{n+9}\) nur endlich viele Summanden den ganzzahligen Teil beeinflussen, und dass jeder dieser Summanden durch genau eine modulare Potenzierung behandelt werden kann.
Durch Multiplikation mit \(10^{n+9}\) wandern die Stellen \(n\) bis \(n+9\) in die letzten 10 Stellen einer ganzen Zahl:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
Die Abrundung entfernt alles strikt hinter der \((n+9)\)-ten Nachkommastelle, und die Reduktion modulo \(10^{10}\) isoliert genau den gesuchten Block.
Sei \(L\) die größte ganze Zahl mit
$$3^L\le n+9.$$
Für jedes \(k>L\) gilt dann \(3^k\ge n+10\), also
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
Damit erfüllt der weggelassene Schwanz
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
Weil dieser Rest strikt kleiner als \(1\) ist, kann er die Abrundung nicht verändern. Also
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
Für die eigentliche Eingabe \(n=10^{16}\) bleiben damit nur \(L=33\) Summanden übrig.
Für jedes \(1\le k\le L\) schreibe
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
Dann ist
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$$
und nach Summation folgt
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
Der Quotiententeil liefert direkt den Beitrag zur Antwort modulo \(10^{10}\). Der Restteil erzeugt einen Carry, weil mehrere Bruchteile zusammen mindestens \(1\) ergeben können.
Alle Nenner sind Potenzen von \(3\), also lassen sie sich sauber zusammenfassen:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
Definiert man
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
dann gilt
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
Das ist exakt: Die Implementierungen speichern alle Reste, bilden den Zähler \(\sum r_k 3^{L-k}\) und führen genau eine Division durch \(3^L\) aus.
Die Zahl \(10^{n+9-3^k}\) vollständig auszurechnen wäre unmöglich, aber das ist nicht nötig. Definiere den Rest
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
Da
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
für ein ganzzahliges \(t_k\) gilt, liefert Division durch \(3^k\)
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Damit erhält man genau die benötigten Daten aus \(s_k\):
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Darum genügt pro Summand eine modulare Potenzierung.
Hier ist \(n+9=109\), also \(L=4\), denn \(3^4=81\le 109\lt 243=3^5\). Damit
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
Für diese vier Nenner ist der Rest modulo \(3^k 10^{10}\) jeweils \(10^{10}\), daher sind die Quotientenbeiträge
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
Die zugehörigen Reste lauten
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
Damit ist der Carry-Zähler
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
also \(c=\lfloor 76/81\rfloor=0\). Die Summe der Quotientenbeiträge ist
$$3333333333+1111111111+370370370+123456790=4938271604.$$
Der 10-stellige Block ab Position \(100\) ist somit \(4938271604\). Genau dieser Kontrollwert wird von der Implementierung verwendet.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst erzeugen sie die Potenzen \(3,9,27,\dots\) bis \(n+9\) und bestimmen damit den letzten relevanten Index \(L\). Danach berechnen sie für jeden verbleibenden Summanden \(10^{n+9-3^k}\bmod(3^k 10^{10})\) mittels schneller modularer Potenzierung.
Aus diesem Rest werden zwei Werte gewonnen: die letzten 10 Stellen des Quotientenbeitrags \(\left\lfloor s_k/3^k\right\rfloor\) und der exakte Rest \(s_k\bmod 3^k\). Die Quotiententeile werden modulo \(10^{10}\) aufsummiert, während die Reste gespeichert werden. Nach der Schleife bildet die Implementierung den einzelnen Zähler \(\sum r_k 3^{L-k}\), dividiert durch \(3^L\) für den exakten Carry \(c\), addiert diesen Carry zur akkumulierten Quotientensumme und formatiert das Ergebnis als 10-stelligen Dezimalblock mit führenden Nullen.
Mit \(L=\lfloor\log_3(n+9)\rfloor\) gibt es genau \(L\) relevante Summanden, und jeder davon benötigt eine modulare Potenzierung per Repeated Squaring. Das sind \(O(\log n)\) modulare Multiplikationen auf Zahlen mit Bitlänge \(O(\log n)\). Insgesamt ergibt sich damit eine Laufzeit von \(O(L\log n\,M(\log n))\), wobei \(M\) die Kosten der Big-Integer-Multiplikation bezeichnet. Der Speicherbedarf ist \(O(L)\) für die gespeicherten Dreierpotenzen und Reste.
Bu problemdeki sayı şu Stoneham sayısıdır:
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
İstenen şey, \(n=10^{16}\) konumundan başlayan art arda 10 ondalık basamaktır. Şunu tanımlarsak
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
\(A(n)\) tam olarak bu 10 basamaklı blok olur; baştaki sıfırlar da korunur. Dolayısıyla görev aslında bir basamak çıkarma problemidir: ondalık açılımı \(10^{16}\). basamağa kadar üretmeden \(A(10^{16})\) hesaplanmalıdır.
Uygulamalar sonsuz Stoneham toplamını kısa ve tam bir hesaba dönüştürüyor. Temel fikir şudur: \(10^{n+9}\) ile çarpınca yalnızca sonlu sayıda terim tamsayı kısmını etkiler ve bu terimlerin her biri tek bir modüler üs alma işlemiyle işlenebilir.
\(10^{n+9}\) ile çarpmak, \(n\) ile \(n+9\) arasındaki basamakları bir tamsayının son 10 basamağına taşır:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
Taban almak, \((n+9)\). basamaktan sonrasını siler. Sonra modulo \(10^{10}\) almak da tam olarak aradığımız 10 basamaklı parçayı bırakır.
\(3^L\le n+9\) koşulunu sağlayan en büyük tamsayı \(L\) olsun:
$$3^L\le n+9.$$
\(k>L\) için \(3^k\ge n+10\) olur ve dolayısıyla
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
Böylece atılan kuyruk için
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1$$
elde edilir. Atılan toplam \(1\)'den küçük olduğu için taban değerini değiştiremez. Demek ki
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
Gerçek girdi \(n=10^{16}\) için bu, yalnızca \(L=33\) terimin kaldığı anlamına gelir.
Her \(1\le k\le L\) için
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k$$
yazalım. O zaman
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k}$$
olur ve tüm terimleri toplayınca
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor$$
elde edilir. Bölüm kısmı doğrudan cevaba modulo \(10^{10}\) katkı yapar. Kalan kısmı ise birkaç kesir parçası birleşip \(1\)'i aşabildiği için bir taşıma üretir.
Tüm paydalar \(3\)'ün kuvvetleri olduğundan kolayca birleştirilir:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
Şimdi
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor$$
tanımını yaparsak
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}$$
olur. Bu ifade tamdır; uygulama tüm kalanları saklar, \(\sum r_k 3^{L-k}\) sayacını oluşturur ve bir kez \(3^L\)'ye böler.
\(10^{n+9-3^k}\) sayısını açıkça üretmek imkansızdır, ama buna gerek yoktur. Şu kalanı tanımlayalım:
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
Çünkü
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
şeklinde bir tamsayı \(t_k\) vardır. \(3^k\)'ye bölünce
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k$$
elde edilir. Böylece gereken bilgiler doğrudan gelir:
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Bu yüzden her terim için tek bir modüler üs alma yeterlidir.
Burada \(n+9=109\) olduğundan \(L=4\), çünkü \(3^4=81\le 109\lt 243=3^5\). Dolayısıyla
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
Bu dört payda için \(3^k 10^{10}\) modundaki kalıntı \(10^{10}\) olur. O halde bölüm katkıları
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790$$
şeklindedir. İlgili kalanlar ise
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
Buna göre taşıma payı
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76$$
olur; yani \(c=\lfloor 76/81\rfloor=0\). Bölüm katkılarının toplamı
$$3333333333+1111111111+370370370+123456790=4938271604$$
verir. Böylece \(100\). konumdan başlayan 10 basamaklı blok \(4938271604\) olur. Bu değer uygulamanın kullandığı kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı yapıyı izler. Önce \(3,9,27,\dots\) kuvvetleri \(n+9\)'a kadar üretilir ve son ilgili indeks \(L\) bulunur. Sonra her kalan terim için hızlı modüler üs alma ile \(10^{n+9-3^k}\bmod(3^k 10^{10})\) hesaplanır.
Bu kalıntıdan iki bilgi çıkarılır: bölüm katkısının son 10 basamağı \(\left\lfloor s_k/3^k\right\rfloor\) ve tam kalan \(s_k\bmod 3^k\). Bölüm parçaları modulo \(10^{10}\) toplanır, kalanlar ise saklanır. Döngü bittikten sonra uygulama tek bir \(\sum r_k 3^{L-k}\) sayacı kurar, \(3^L\)'ye bölerek tam taşımayı \(c\) elde eder, bu taşımayı bölüm toplamına ekler ve sonucu baştaki sıfırlarla birlikte 10 basamaklı biçimde yazar.
\(L=\lfloor\log_3(n+9)\rfloor\) olsun. Tam olarak \(L\) ilgili terim vardır ve her biri repeated squaring kullanan bir modüler üs alma gerektirir. Bu da bit uzunluğu \(O(\log n)\) olan sayılar üzerinde \(O(\log n)\) adet modüler çarpım demektir. Toplam çalışma süresi \(O(L\log n\,M(\log n))\), burada \(M\) büyük tamsayı çarpım maliyetidir. Bellek kullanımı ise saklanan \(3\) kuvvetleri ve kalanlar nedeniyle \(O(L)\)'dir.
El número de este problema es el número de Stoneham
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
Se piden los 10 dígitos decimales consecutivos que comienzan en la posición \(n=10^{16}\). Si definimos
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
entonces \(A(n)\) es exactamente ese bloque de 10 cifras, permitiendo ceros iniciales. El problema completo consiste en extraer \(A(10^{16})\) sin expandir la representación decimal hasta la posición \(10^{16}\).
Las implementaciones convierten la serie infinita de Stoneham en un cálculo corto y exacto. La idea central es que, después de multiplicar por \(10^{n+9}\), solo un número finito de términos puede afectar la parte entera, y cada uno de esos términos se puede resolver con una sola potenciación modular.
Multiplicar por \(10^{n+9}\) desplaza las cifras desde la posición \(n\) hasta la \(n+9\) a las últimas 10 cifras de un entero:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
Tomar la parte entera elimina todo lo que queda estrictamente después de la cifra \((n+9)\), y reducir módulo \(10^{10}\) deja exactamente el bloque pedido.
Sea \(L\) el mayor entero que satisface
$$3^L\le n+9.$$
Para todo \(k>L\), se cumple \(3^k\ge n+10\), así que
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
Por tanto, la cola descartada satisface
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
Como la cola es estrictamente menor que \(1\), no puede modificar la parte entera. Luego
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
Para la entrada real \(n=10^{16}\), esto deja solo \(L=33\) términos relevantes.
Para cada \(1\le k\le L\), escribimos
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
Entonces
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$$
y al sumar obtenemos
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
La parte de los cocientes aporta directamente al resultado módulo \(10^{10}\). La parte de los restos genera un acarreo, porque varios fragmentos fraccionarios pueden sumar al menos \(1\).
Todos los denominadores son potencias de \(3\), así que se combinan sin dificultad:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
Si definimos
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
entonces
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
Esto es exacto: las implementaciones guardan todos los restos, forman el numerador \(\sum r_k 3^{L-k}\) y realizan una sola división por \(3^L\).
Calcular explícitamente \(10^{n+9-3^k}\) sería absurdo, pero no hace falta. Definimos el residuo
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
Como
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
para cierto entero \(t_k\), al dividir entre \(3^k\) se obtiene
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Por lo tanto, a partir de \(s_k\) recuperamos exactamente los datos necesarios:
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Eso explica por qué basta una potenciación modular por término.
Aquí \(n+9=109\), así que \(L=4\), porque \(3^4=81\le 109\lt 243=3^5\). Entonces
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
Para estos cuatro denominadores, el residuo módulo \(3^k 10^{10}\) es \(10^{10}\), de modo que las contribuciones de cociente son
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
Los restos correspondientes son
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
Por tanto, el numerador del acarreo es
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
y así \(c=\lfloor 76/81\rfloor=0\). La suma de las partes de cociente es
$$3333333333+1111111111+370370370+123456790=4938271604.$$
Luego el bloque de 10 cifras que empieza en la posición \(100\) es \(4938271604\), exactamente el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero generan las potencias \(3,9,27,\dots\) hasta \(n+9\), lo que fija el último índice relevante \(L\). Después, para cada término superviviente, calculan \(10^{n+9-3^k}\bmod(3^k 10^{10})\) mediante potenciación modular rápida.
A partir de ese residuo extraen dos piezas: las últimas 10 cifras de la contribución del cociente \(\left\lfloor s_k/3^k\right\rfloor\) y el resto exacto \(s_k\bmod 3^k\). Las partes de cociente se acumulan módulo \(10^{10}\), mientras que los restos se guardan. Al final, la implementación forma el numerador único \(\sum r_k 3^{L-k}\), divide por \(3^L\) para obtener el acarreo exacto \(c\), suma ese acarreo al total acumulado y da formato al resultado como un bloque decimal de 10 cifras con ceros iniciales cuando hace falta.
Sea \(L=\lfloor\log_3(n+9)\rfloor\). Hay exactamente \(L\) términos relevantes, y cada uno requiere una potenciación modular por exponenciación binaria. Eso implica \(O(\log n)\) multiplicaciones modulares sobre enteros de \(O(\log n)\) bits, así que el tiempo total es \(O(L\log n\,M(\log n))\), donde \(M\) representa el costo de multiplicar enteros grandes. La memoria usada es \(O(L)\), debido a la lista de potencias de \(3\) y a los restos almacenados.
本题中的数是 Stoneham 数
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
要求的是从第 \(n=10^{16}\) 位开始的连续 10 个十进制数字。如果定义
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
那么 \(A(n)\) 恰好就是这 10 位数字，允许前导零。于是问题可以表述为一个数位提取问题：不去真正展开到第 \(10^{16}\) 位，而是直接求出 \(A(10^{16})\)。
实现的核心是把这个无限级数变成一个很短但完全精确的计算。关键事实有两个：第一，乘上 \(10^{n+9}\) 以后，只有有限个项可能影响整数部分；第二，每一个保留下来的项都可以通过一次模幂运算恢复出所需的信息。
将 \(\alpha_{10,3}\) 乘以 \(10^{n+9}\)，第 \(n\) 位到第 \(n+9\) 位就会进入某个整数的最后 10 位：
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
对这个量取下整，会去掉 \((n+9)\) 位之后的所有小数部分；再对 \(10^{10}\) 取模，就正好留下我们想要的 10 位数字块。
设 \(L\) 为满足
$$3^L\le n+9$$
的最大整数。若 \(k>L\)，则 \(3^k\ge n+10\)，因此
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
于是被舍弃的尾项满足
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
由于尾项严格小于 \(1\)，它不可能改变整数部分。所以
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
对实际输入 \(n=10^{16}\) 而言，只剩下 \(L=33\) 个有效项，这就是算法能非常快的原因之一。
对每个 \(1\le k\le L\)，写成
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
于是
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k}.$$
把这些项加起来，就得到
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
其中 \(\sum q_k\) 是直接贡献到答案中的整数部分，而余数对应的分数和可能会跨过整数边界，因此会形成一个额外进位。
所有分母都是 \(3\) 的幂，所以可以统一到分母 \(3^L\)：
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
定义
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
那么就有
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
这里没有任何近似。实现会把每个余数都保存下来，构造分子 \(\sum r_k 3^{L-k}\)，最后只做一次整数除法就能得到精确进位 \(c\)。
真正去计算 \(10^{n+9-3^k}\) 是完全不现实的，但我们其实不需要这个完整整数。定义残值
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
因为存在某个整数 \(t_k\)，使得
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k,$$
两边除以 \(3^k\) 便得到
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
因此我们所需的两类信息恰好都能从 \(s_k\) 中读出：
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
这说明每个项只需要一次快速模幂运算即可，不需要处理巨大的十进制整数。
此时 \(n+9=109\)，所以 \(L=4\)，因为 \(3^4=81\le 109\lt 243=3^5\)。于是
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
对这四个分母来说，模 \(3^k 10^{10}\) 的残值都是 \(10^{10}\)，因此商的贡献分别为
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
对应的余数为
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
所以进位分子是
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
从而 \(c=\lfloor 76/81\rfloor=0\)。把商的各部分相加得到
$$3333333333+1111111111+370370370+123456790=4938271604.$$
因此从第 \(100\) 位开始的 10 位数字块就是 \(4938271604\)。这也正是实现中使用的校验值。
C++、Python 和 Java 实现都遵循同一条思路。首先生成所有不超过 \(n+9\) 的 \(3\) 的幂，即 \(3,9,27,\dots\)，从而确定最后一个有效指标 \(L\)。然后对每一个有效项，使用快速模幂计算 \(10^{n+9-3^k}\bmod(3^k 10^{10})\)。
从这个残值中可以直接提取两部分信息：商贡献的最后 10 位 \(\left\lfloor s_k/3^k\right\rfloor\)，以及精确余数 \(s_k\bmod 3^k\)。所有商贡献按模 \(10^{10}\) 累加，所有余数则被保存下来。循环结束后，实现构造单个分子 \(\sum r_k 3^{L-k}\)，再除以 \(3^L\) 得到精确进位 \(c\)，最后把这个进位加回累积和，并按 10 位十进制格式输出，必要时补前导零。
令 \(L=\lfloor\log_3(n+9)\rfloor\)。算法只处理这 \(L\) 个有效项，而每个项需要一次二分幂风格的模幂运算，因此需要 \(O(\log n)\) 次模乘，参与运算的整数位数为 \(O(\log n)\)。总时间复杂度为 \(O(L\log n\,M(\log n))\)，其中 \(M\) 表示大整数乘法代价；空间复杂度为 \(O(L)\)，用于保存 \(3\) 的幂和各项余数。
В этой задаче рассматривается число Стоунхэма
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
Нужно найти 10 последовательных десятичных цифр, начиная с позиции \(n=10^{16}\). Если определить
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
то \(A(n)\) и есть нужный 10-значный блок, включая возможные ведущие нули. Значит, задача сводится к извлечению цифр: нужно вычислить \(A(10^{16})\), не строя десятичную запись до позиции \(10^{16}\).
Реализации превращают бесконечный ряд Стоунхэма в короткое и точное вычисление. Главные наблюдения таковы: после умножения на \(10^{n+9}\) только конечное число слагаемых может повлиять на целую часть, и каждое такое слагаемое восстанавливается одной модульной степенью.
Умножение на \(10^{n+9}\) переносит цифры с позиций от \(n\) до \(n+9\) в последние 10 цифр некоторого целого числа:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
Взятие пола отбрасывает всё, что стоит строго после \((n+9)\)-й десятичной цифры, а редукция по модулю \(10^{10}\) оставляет ровно тот блок, который требуется.
Пусть \(L\) — наибольшее целое число, для которого
$$3^L\le n+9.$$
Если \(k>L\), то \(3^k\ge n+10\), а значит
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
Следовательно, отброшенный хвост удовлетворяет оценке
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
Так как хвост строго меньше \(1\), он не способен изменить целую часть. Поэтому
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
Для реального входа \(n=10^{16}\) это означает, что остаётся всего \(L=33\) значимых слагаемых.
Для каждого \(1\le k\le L\) запишем
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
Тогда
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$$
и после суммирования получаем
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
Сумма частных сразу даёт вклад в ответ по модулю \(10^{10}\). Сумма дробных остатков создаёт перенос, потому что несколько дробей могут вместе дать как минимум \(1\).
Все знаменатели являются степенями \(3\), поэтому они легко сводятся к общему знаменателю:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
Если ввести
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
то
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
Здесь нет приближений: реализации сохраняют все остатки, строят числитель \(\sum r_k 3^{L-k}\) и выполняют одно целочисленное деление на \(3^L\).
Явно вычислять \(10^{n+9-3^k}\) невозможно, но это и не требуется. Определим остаток
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
Поскольку
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
для некоторого целого \(t_k\), деление на \(3^k\) даёт
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Значит, из \(s_k\) сразу восстанавливаются нужные данные:
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
Именно поэтому на одно слагаемое достаточно одной быстрой модульной степени.
Здесь \(n+9=109\), поэтому \(L=4\), так как \(3^4=81\le 109\lt 243=3^5\). Следовательно,
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
Для этих четырёх знаменателей остаток по модулю \(3^k 10^{10}\) равен \(10^{10}\), поэтому вклады частных равны
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
Соответствующие остатки таковы:
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
Числитель переноса равен
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
поэтому \(c=\lfloor 76/81\rfloor=0\). Сумма вкладов частных равна
$$3333333333+1111111111+370370370+123456790=4938271604.$$
Следовательно, 10-значный блок, начинающийся с позиции \(100\), равен \(4938271604\). Это совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала строятся степени \(3,9,27,\dots\) до \(n+9\), что определяет последний значимый индекс \(L\). Затем для каждого оставшегося слагаемого вычисляется \(10^{n+9-3^k}\bmod(3^k 10^{10})\) с помощью быстрого модульного возведения в степень.
Из этого остатка извлекаются две величины: последние 10 цифр вклада частного \(\left\lfloor s_k/3^k\right\rfloor\) и точный остаток \(s_k\bmod 3^k\). Частные накапливаются по модулю \(10^{10}\), а остатки сохраняются. После цикла реализация формирует единый числитель \(\sum r_k 3^{L-k}\), делит его на \(3^L\), получает точный перенос \(c\), прибавляет этот перенос к накопленной сумме и форматирует результат как 10-значный десятичный блок с ведущими нулями при необходимости.
Пусть \(L=\lfloor\log_3(n+9)\rfloor\). Обрабатываются ровно \(L\) значимых слагаемых, и для каждого требуется одно модульное возведение в степень методом двоичного разложения. Это даёт \(O(\log n)\) модульных умножений над числами длины \(O(\log n)\) бит, поэтому полное время работы равно \(O(L\log n\,M(\log n))\), где \(M\) — стоимость умножения больших целых чисел. Память равна \(O(L)\), поскольку нужно хранить степени \(3\) и список остатков.
العدد في هذه المسألة هو عدد ستونهم
$$\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{1}{3^k 10^{3^k}}.$$
المطلوب هو الكتلة المكونة من 10 خانات عشرية المتتالية التي تبدأ عند الموضع \(n=10^{16}\). إذا عرّفنا
$$A(n)\equiv \left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor \pmod{10^{10}},\qquad 0\le A(n)\lt 10^{10},$$
فإن \(A(n)\) تمثل هذه الكتلة ذات العشر خانات تماما، مع السماح بوجود أصفار في البداية. لذلك فالمسألة هي مسألة استخراج أرقام: نريد حساب \(A(10^{16})\) من دون توليد التوسع العشري حتى الخانة \(10^{16}\).
التنفيذ يحول سلسلة ستونهم اللانهائية إلى حساب قصير ودقيق. الفكرة الأساسية أن الضرب في \(10^{n+9}\) يجعل عددا محدودا فقط من الحدود قادرا على التأثير في الجزء الصحيح، وأن كل حد باق يمكن التعامل معه بواسطة قوة معيارية واحدة فقط.
عند الضرب في \(10^{n+9}\) تنتقل الخانات من الموضع \(n\) إلى الموضع \(n+9\) لتصبح آخر 10 خانات في عدد صحيح:
$$10^{n+9}\alpha_{10,3}=\sum_{k=1}^{\infty}\frac{10^{n+9-3^k}}{3^k}.$$
أخذ الجزء الصحيح يحذف كل ما يقع بعد الخانة \((n+9)\) مباشرة، ثم الاختزال modulo \(10^{10}\) يترك بالضبط الكتلة التي نبحث عنها.
ليكن \(L\) أكبر عدد صحيح يحقق
$$3^L\le n+9.$$
إذا كان \(k>L\) فإن \(3^k\ge n+10\)، وبالتالي
$$0\lt \frac{10^{n+9-3^k}}{3^k}\le \frac{1}{10\cdot 3^k}.$$
ومن ثم فإن الذيل المهمل يحقق
$$0\lt \sum_{k=L+1}^{\infty}\frac{10^{n+9-3^k}}{3^k}\lt \frac{1}{10}\sum_{k=L+1}^{\infty}\frac{1}{3^k}\lt \frac{1}{20}\lt 1.$$
وبما أن هذا الذيل أصغر تماما من \(1\)، فلا يمكنه تغيير الجزء الصحيح. إذن
$$\left\lfloor 10^{n+9}\alpha_{10,3}\right\rfloor=\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor.$$
بالنسبة إلى الإدخال الفعلي \(n=10^{16}\)، فهذا يعني أن عدد الحدود المؤثرة هو فقط \(L=33\).
لكل \(1\le k\le L\) نكتب
$$10^{n+9-3^k}=q_k 3^k+r_k,\qquad 0\le r_k\lt 3^k.$$
وعندها
$$\frac{10^{n+9-3^k}}{3^k}=q_k+\frac{r_k}{3^k},$$
وبجمع الحدود نحصل على
$$\left\lfloor\sum_{k=1}^{L}\frac{10^{n+9-3^k}}{3^k}\right\rfloor=\sum_{k=1}^{L}q_k+\left\lfloor\sum_{k=1}^{L}\frac{r_k}{3^k}\right\rfloor.$$
جزء خارج القسمة يضيف مباشرة إلى الجواب modulo \(10^{10}\)، أما جزء البواقي فينتج حملا لأن عدة كسور صغيرة قد تتجاوز \(1\) عند جمعها.
بما أن جميع المقامات هي قوى للعدد \(3\)، فيمكن جمعها بسهولة تحت مقام واحد:
$$\sum_{k=1}^{L}\frac{r_k}{3^k}=\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}.$$
إذا عرفنا
$$c=\left\lfloor\frac{\sum_{k=1}^{L}r_k 3^{L-k}}{3^L}\right\rfloor,$$
فإن
$$A(n)\equiv \sum_{k=1}^{L}q_k+c \pmod{10^{10}}.$$
هذا التعبير دقيق تماما. التنفيذ يحفظ كل باق، ويكون البسط \(\sum r_k 3^{L-k}\)، ثم يجري قسمة صحيحة واحدة على \(3^L\).
من غير المعقول حساب \(10^{n+9-3^k}\) بالكامل، لكن ذلك غير مطلوب. نعرّف الباقي
$$s_k\equiv 10^{n+9-3^k}\pmod{3^k 10^{10}},\qquad 0\le s_k\lt 3^k 10^{10}.$$
وبما أن
$$10^{n+9-3^k}=t_k 3^k 10^{10}+s_k$$
لبعض العدد الصحيح \(t_k\)، فإن القسمة على \(3^k\) تعطي
$$q_k=t_k 10^{10}+\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
وهكذا نحصل مباشرة من \(s_k\) على البيانات اللازمة:
$$q_k\bmod 10^{10}=\left\lfloor\frac{s_k}{3^k}\right\rfloor,\qquad r_k=s_k\bmod 3^k.$$
ولهذا يكفي تنفيذ قوة معيارية واحدة لكل حد.
لدينا هنا \(n+9=109\)، ولذلك \(L=4\) لأن \(3^4=81\le 109\lt 243=3^5\). ومن ثم
$$A(100)\equiv \left\lfloor\frac{10^{106}}{3}+\frac{10^{100}}{9}+\frac{10^{82}}{27}+\frac{10^{28}}{81}\right\rfloor \pmod{10^{10}}.$$
في هذه الحدود الأربعة يكون الباقي modulo \(3^k 10^{10}\) مساويا لـ \(10^{10}\)، ولذلك تكون مساهمات خارج القسمة
$$q_1\bmod 10^{10}=3333333333,\qquad q_2\bmod 10^{10}=1111111111,$$
$$q_3\bmod 10^{10}=0370370370,\qquad q_4\bmod 10^{10}=0123456790.$$
أما البواقي المقابلة فهي
$$r_1=1,\qquad r_2=1,\qquad r_3=10,\qquad r_4=10.$$
إذن بسط الحمل يساوي
$$1\cdot 27+1\cdot 9+10\cdot 3+10\cdot 1=76,$$
ومن ثم \(c=\lfloor 76/81\rfloor=0\). وبجمع أجزاء خارج القسمة نحصل على
$$3333333333+1111111111+370370370+123456790=4938271604.$$
إذن الكتلة العشرية ذات الخانات العشر التي تبدأ من الموضع \(100\) هي \(4938271604\)، وهي نفس قيمة التحقق التي يعتمدها التنفيذ.
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولا تولد جميع قوى \(3\) حتى \(n+9\)، أي \(3,9,27,\dots\)، وبهذا تحدد آخر فهرس مؤثر \(L\). بعد ذلك تحسب لكل حد باقيا من الشكل \(10^{n+9-3^k}\bmod(3^k 10^{10})\) باستخدام الرفع السريع للأسس modulo عدد كبير.
ومن هذا الباقي تستخرج قيمتين: آخر 10 خانات من مساهمة خارج القسمة \(\left\lfloor s_k/3^k\right\rfloor\)، والباقي الدقيق \(s_k\bmod 3^k\). تجمع أجزاء خارج القسمة modulo \(10^{10}\)، بينما تحفظ البواقي لاستخدامها لاحقا. بعد انتهاء الحلقة، يكون التنفيذ البسط الواحد \(\sum r_k 3^{L-k}\)، ويقسمه على \(3^L\) للحصول على الحمل الدقيق \(c\)، ثم يضيف هذا الحمل إلى المجموع المتراكم ويعرض النتيجة على شكل كتلة من 10 خانات مع أصفار بادئة عند الحاجة.
إذا كان \(L=\lfloor\log_3(n+9)\rfloor\)، فهناك بالضبط \(L\) حدود مؤثرة، وكل واحد منها يحتاج إلى قوة معيارية واحدة بطريقة التربيع المتكرر. هذا يعني \(O(\log n)\) ضربات معيارية على أعداد طولها البتّي \(O(\log n)\)، ولذلك يكون الزمن الكلي \(O(L\log n\,M(\log n))\)، حيث تمثل \(M\) كلفة ضرب الأعداد الكبيرة. أما الذاكرة فهي \(O(L)\) بسبب تخزين قوى \(3\) وقائمة البواقي.