The problem asks for the sum of the decimal digits of \(2^{1000}\). The smaller example \(2^{15}=32768\) has digit sum \(3+2+7+6+8=26\), so the actual task is the same operation on a much larger power of two.
The main issue is size, not number theory. Since
$$\#\text{digits}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
the number does not fit in an ordinary fixed-width integer, so the computation must treat the decimal expansion as a multi-digit object.
Write the decimal expansion of \(2^n\) as
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9,$$
so the desired quantity is simply
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
The subtle part is that the digit sum cannot be updated from the previous digit sum alone, because carries depend on the entire decimal state. That is why the natural mathematical object is the full vector of decimal digits.
Suppose after \(t\) doublings we know the digits of \(2^t\):
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
Knowing only \(S(2^t)\) is not enough to determine \(S(2^{t+1})\). For example, the numbers 19 and 28 both have digit sum 10, but doubling gives 38 and 56, whose digit sums are 11 and 11 after different carry patterns. In general the carry behavior depends on every digit, so the state must keep the whole decimal representation.
To pass from \(2^t\) to \(2^{t+1}\), process the digits from least significant to most significant with a carry. Set \(c_0=0\), and for each position \(i\) define
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
Because \(0\le a_i^{(t)}\le 9\) and \(c_i\in\{0,1\}\), we always have \(0\le u_i\le 19\), so every new carry is again either 0 or 1. If the final carry is 1, it becomes a new most significant digit. Starting from \(2^0=1\), repeating this update \(n\) times constructs the exact decimal digits of \(2^n\).
The correctness of the schoolbook update rests on a simple invariant. After the first \(r\) digits have been processed in one doubling step, the digits already written are exactly the last \(r\) decimal digits of \(2^{t+1}\), and the carry holds the amount that must be transferred into the remaining higher-order part. In other words, the algorithm never loses information: it only postpones part of the doubled value into the carry that will be added to the next digit.
This is the same positional-value principle used in hand arithmetic. The recurrence above is therefore not an approximation; it is a digit-by-digit proof that the decimal array after \(n\) rounds is the true expansion of \(2^n\).
The number of decimal digits of \(2^n\) is determined by
$$10^{k-1}\le 2^n<10^k,$$
which gives
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
So the decimal length grows linearly with \(n\). The \(t\)-th doubling touches \(k(t)=\Theta(t)\) digits, and the total amount of single-digit work is therefore
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
For \(n=1000\), that quadratic bound is still tiny, because the final number has only 302 digits.
A concrete example shows the recurrence in action. Start from
$$2^{11}=2048.$$
Double digit by digit. From right to left in ordinary notation, or equivalently from least significant to most significant in the digit array:
$$8\mapsto 16\Rightarrow 6\text{ with carry }1,$$
$$4\mapsto 2\cdot 4+1=9\Rightarrow 9\text{ with carry }0,$$
$$0\mapsto 0,\qquad 2\mapsto 4,$$
so \(2^{12}=4096\). Repeating gives
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
Hence
$$S(2^{15})=3+2+7+6+8=26.$$
Because \(10\equiv 1\pmod 9\), every decimal number is congruent modulo 9 to the sum of its digits. Therefore
$$S(2^n)\equiv 2^n\pmod 9.$$
This does not determine the answer by itself, but it is an excellent sanity check. For the worked example, \(26\equiv 8\pmod 9\) and \(2^{15}\equiv 8\pmod 9\), so the result is consistent.
The C++, Python, and Java implementations all compute the exact power and then sum its decimal digits, but they choose different representations for the intermediate number.
The C++ implementation mirrors the mathematics directly. It stores the decimal digits in little-endian order, starts from the single digit 1, and performs one doubling step for each increase of the exponent. Every pass applies the carry recurrence above, and any leftover carry is appended as a new most significant digit. Once all doublings are complete, a final linear scan adds the digits.
This version makes the invariant explicit: at every moment the digit array is an exact decimal representation of the current power of two.
The Python implementation uses the language's native arbitrary-precision integers. It forms the exact integer \(2^n\), converts it to decimal text, and sums the characters as digits. The code is very short because the runtime handles the internal big-integer arithmetic automatically, but mathematically it is still computing the same decimal expansion and then evaluating the same digit-sum formula.
The Java implementation uses the standard arbitrary-precision integer type provided by the language library. It raises 2 to the required exponent exactly, turns the result into a decimal string, and accumulates the digits. Like the Python version, it delegates the low-level multi-precision arithmetic to a library, but the mathematical object is still the exact integer \(2^n\), not a floating-point approximation.
The implementations also include simple checkpoints based on the problem statement, such as confirming that the exponent 15 produces the digit sum 26. The C++ implementation additionally checks the base case \(2^0=1\).
For the manual decimal-doubling method, the final digit count is \(k(n)=\Theta(n)\), and the \(t\)-th doubling touches \(k(t)=\Theta(t)\) digits. That leads to
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
time and \(O(k(n))=O(n)\) memory.
For the specific target \(n=1000\), this is easily fast enough: only a few hundred thousand single-digit updates are needed. The Python and Java implementations rely on optimized arbitrary-precision libraries, but at this scale they are also effectively instantaneous for the same reason: the exact value has only 302 decimal digits.
Gesucht ist die Summe der Dezimalziffern von \(2^{1000}\). Das kleinere Beispiel \(2^{15}=32768\) hat die Ziffernsumme \(3+2+7+6+8=26\); die eigentliche Aufgabe ist also dieselbe Rechnung für eine viel größere Zweierpotenz.
Die Schwierigkeit liegt nicht in komplizierter Zahlentheorie, sondern in der Größe der Zahl. Es gilt
$$\#\text{Ziffern}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
also passt \(2^{1000}\) nicht in einen gewöhnlichen Ganzzahltyp fester Breite. Man muss die Dezimaldarstellung daher als mehrstelligen Zustand behandeln.
Schreibe die Dezimalentwicklung von \(2^n\) in der Form
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9,$$
dann ist die gesuchte Größe
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
Wichtig ist dabei: Die Ziffernsumme allein ist kein ausreichender Zustand. Beim Verdoppeln entscheiden die Überträge anhand der gesamten Dezimaldarstellung, nicht nur anhand der bisherigen Summe.
Angenommen, nach \(t\) Verdopplungen kennen wir die Ziffern von \(2^t\):
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
Aus \(S(2^t)\) allein kann man \(S(2^{t+1})\) im Allgemeinen nicht bestimmen, weil die Übertragsstruktur verloren geht. Der natürliche mathematische Zustand ist daher der gesamte Ziffernvektor \(a_0^{(t)},a_1^{(t)},\dots\).
Der Übergang von \(2^t\) zu \(2^{t+1}\) erfolgt ziffernweise mit Übertrag. Setze \(c_0=0\), und definiere für jede Stelle \(i\)
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
Wegen \(0\le a_i^{(t)}\le 9\) und \(c_i\in\{0,1\}\) gilt stets \(0\le u_i\le 19\). Der nächste Übertrag ist also wieder nur 0 oder 1. Beginnt man mit \(2^0=1\) und wiederholt diese Vorschrift \(n\)-mal, erhält man exakt die Dezimalziffern von \(2^n\).
Die Korrektheit der Schulbuchmethode beruht auf einem einfachen Invariant: Nachdem in einem Verdopplungsschritt die ersten \(r\) Stellen verarbeitet wurden, stimmen die bereits geschriebenen \(r\) Ziffern exakt mit den letzten \(r\) Dezimalziffern von \(2^{t+1}\) überein, und der aktuelle Übertrag enthält genau den Anteil, der in den noch unverarbeiteten höheren Stellen berücksichtigt werden muss.
Damit ist jeder Schritt eine exakte Stellenwertrechnung. Es geht also nicht um eine heuristische Näherung, sondern um einen direkten Beweis der Dezimaldarstellung durch systematische Übertragsfortpflanzung.
Die Anzahl der Dezimalziffern von \(2^n\) folgt aus
$$10^{k-1}\le 2^n<10^k,$$
also
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
Die Länge wächst damit linear in \(n\). Im \(t\)-ten Verdopplungsschritt werden \(k(t)=\Theta(t)\) Stellen berührt, also ist der Gesamtaufwand
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
Für \(n=1000\) ist das völlig unproblematisch, weil die Endzahl nur 302 Ziffern besitzt.
Ein konkretes Beispiel zeigt die Rekursion. Starte bei
$$2^{11}=2048.$$
Verdopple nun ziffernweise:
$$8\mapsto 16\Rightarrow 6\text{ mit Übertrag }1,$$
$$4\mapsto 2\cdot 4+1=9\Rightarrow 9\text{ mit Übertrag }0,$$
$$0\mapsto 0,\qquad 2\mapsto 4,$$
also ist \(2^{12}=4096\). Weiter erhält man
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
Somit folgt
$$S(2^{15})=3+2+7+6+8=26.$$
Weil \(10\equiv 1\pmod 9\) gilt, ist jede Dezimalzahl modulo 9 kongruent zur Summe ihrer Ziffern. Daher
$$S(2^n)\equiv 2^n\pmod 9.$$
Dieser Zusammenhang liefert nicht direkt die Antwort, aber einen sehr guten Plausibilitätstest. Im Beispiel gilt \(26\equiv 8\pmod 9\) und zugleich \(2^{15}\equiv 8\pmod 9\).
Die C++-, Python- und Java-Implementierungen berechnen alle dieselbe exakte Zahl und summieren anschließend ihre Dezimalziffern. Unterschiedlich ist nur die interne Darstellung der großen Zahl.
Die C++-Implementierung bildet die Mathematik direkt ab. Sie speichert die Dezimalziffern in Little-Endian-Reihenfolge, startet mit der einzelnen Ziffer 1 und führt für jede Erhöhung des Exponenten einen Verdopplungsschritt aus. Jeder Durchlauf benutzt genau die oben angegebene Übertragsrekursion; ein verbleibender Übertrag wird als neue höchste Ziffer angehängt. Am Ende werden alle Ziffern linear aufsummiert.
Diese Variante macht das Invariant sichtbar: Das Ziffernarray ist zu jedem Zeitpunkt die exakte Dezimaldarstellung der aktuellen Zweierpotenz.
Die Python-Implementierung verwendet die eingebaute Ganzzahlarithmetik mit beliebiger Genauigkeit. Sie berechnet \(2^n\) exakt, wandelt das Ergebnis in einen Dezimalstring um und summiert dessen Zeichen als Ziffern. Der Code ist dadurch sehr kurz, aber mathematisch ist es dieselbe Pipeline: exakte Zahl bilden, Dezimalziffern lesen, Ziffernsumme addieren.
Die Java-Implementierung benutzt den standardmäßigen Bibliothekstyp für Ganzzahlen beliebiger Präzision. Auch hier wird \(2^n\) exakt berechnet, anschließend in Dezimalschreibweise umgewandelt und ziffernweise aufsummiert. Wie bei Python wird also die Mehrpräzisionsarithmetik an die Laufzeitbibliothek delegiert, während die mathematische Idee unverändert bleibt.
Zusätzlich enthalten die Implementierungen einfache Prüfungen anhand des Beispiels \(2^{15}\mapsto 26\); die C++-Variante überprüft außerdem den Basisfall \(2^0=1\).
Für die manuelle Dezimal-Verdopplung gilt: Die Endlänge ist \(k(n)=\Theta(n)\), und der \(t\)-te Schritt verarbeitet \(k(t)=\Theta(t)\) Ziffern. Daraus folgt
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
Zeit und \(O(k(n))=O(n)\) Speicher.
Für das konkrete Ziel \(n=1000\) ist das mehr als ausreichend, weil nur einige hunderttausend Einzelziffer-Operationen anfallen. Die Python- und Java-Implementierungen stützen sich auf optimierte Mehrpräzisionsbibliotheken, sind bei dieser Eingabegröße aber aus demselben Grund ebenfalls praktisch sofort fertig: \(2^{1000}\) hat nur 302 Dezimalstellen.
Bu problem \(2^{1000}\) sayısının ondalık basamak toplamını ister. Küçük örnek olarak \(2^{15}=32768\) verilir ve bu sayının basamak toplamı \(3+2+7+6+8=26\) olur; gerçek görev aynı işlemi çok daha büyük bir iki kuvveti için yapmaktır.
Zorluk sayı kuramından çok sayının büyüklüğündedir. Çünkü
$$\#\text{basamak}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
dolayısıyla \(2^{1000}\) sıradan sabit genişlikli tamsayılara sığmaz. Bu yüzden çözüm, sayıyı tek bir makine tamsayısı olarak değil, tam ondalık gösterimi olarak ele almalıdır.
\(2^n\)'in ondalık açılımını
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9$$
şeklinde yazalım. O zaman istenen nicelik
$$S(2^n)=\sum_{i=0}^{k-1} d_i$$
olur. Buradaki önemli nokta şudur: yalnızca mevcut basamak toplamını bilmek bir sonraki adımı üretmeye yetmez, çünkü elde oluşumu bütün basamak düzenine bağlıdır. Doğru durum uzayı basamak toplamı değil, tam basamak vektörüdür.
Diyelim ki \(t\) kez ikiyle çarpmadan sonra \(2^t\)'in basamaklarını biliyoruz:
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
Buradan yalnızca \(S(2^t)\) değerini saklamak yeterli değildir. Aynı basamak toplamına sahip iki sayı farklı elde desenleri üretebilir. Dolayısıyla bir sonraki adımı tam olarak belirleyen nesne, tüm ondalık basamakların kendisidir.
\(2^t\)'den \(2^{t+1}\)'e geçerken basamakları en küçük anlamlı basamaktan en büyüğe doğru işleriz. \(c_0=0\) olsun ve her \(i\) için
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor$$
tanımlarını yapalım. \(0\le a_i^{(t)}\le 9\) ve \(c_i\in\{0,1\}\) olduğundan her zaman \(0\le u_i\le 19\) olur; yani yeni elde yine sadece 0 veya 1 olabilir. Başlangıçta \(2^0=1\) alınır ve bu dönüşüm \(n\) kez uygulanırsa \(2^n\)'in tam ondalık basamakları elde edilir.
Okul kitabı yöntemin doğruluğu basit bir değişmezden gelir. Tek bir ikileştirme adımında ilk \(r\) basamak işlendiğinde, yazılmış olan bu \(r\) basamak tam olarak \(2^{t+1}\)'in en sağdaki \(r\) ondalık basamağıdır; elde değeri ise henüz işlenmemiş daha yüksek basamaklara taşınması gereken kısmı tutar.
Yani algoritma hiçbir bilgiyi kaybetmez; yalnızca işlenmeyen kısmı bir sonraki basamağa aktarılacak elde içinde taşır. Bu nedenle basamak dizisi yöntemi yaklaşık değil, tam bir hesaplama yapar.
\(2^n\)'in basamak sayısı
$$10^{k-1}\le 2^n<10^k$$
eşitsizliğinden
$$k=\left\lfloor n\log_{10}2\right\rfloor+1$$
olarak bulunur. Böylece basamak uzunluğu \(n\) ile doğrusal büyür. \(t\). ikileştirme adımı \(k(t)=\Theta(t)\) basamağa dokunduğu için toplam tek-basamak işi
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2)$$
olur. \(n=1000\) için bu maliyet oldukça küçüktür, çünkü son sayı yalnızca 302 basamaklıdır.
Özyinelemeyi somut olarak görelim. Başlangıç noktası
$$2^{11}=2048$$
olsun. Basamak basamak ikiyle çarpalım:
$$8\mapsto 16\Rightarrow 6\text{ ve elde }1,$$
$$4\mapsto 2\cdot 4+1=9\Rightarrow 9\text{ ve elde }0,$$
$$0\mapsto 0,\qquad 2\mapsto 4,$$
böylece \(2^{12}=4096\) elde edilir. Sonra
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768$$
olur. Buradan
$$S(2^{15})=3+2+7+6+8=26$$
sonucuna ulaşırız.
\(10\equiv 1\pmod 9\) olduğundan, her ondalık sayı mod 9'da basamaklarının toplamına denktir. Dolayısıyla
$$S(2^n)\equiv 2^n\pmod 9.$$
Bu özellik cevabı tek başına vermez ama çok iyi bir kontrol sağlar. Örnekte \(26\equiv 8\pmod 9\) ve \(2^{15}\equiv 8\pmod 9\) olduğu için hesap tutarlıdır.
C++, Python ve Java uygulamaları aynı matematiksel nesneyi, yani tam olarak \(2^n\) sayısını üretir ve sonra onun ondalık basamaklarını toplar. Fark, bu büyük sayının bellekte nasıl temsil edildiğidir.
C++ uygulaması matematiği doğrudan uygular. Basamakları küçük anlamlıdan büyüğe doğru saklar, 1 ile başlar ve üs her arttığında bir ikileştirme turu yapar. Her tur yukarıdaki elde özyinelemesini kullanır; tur sonunda elde kalırsa yeni en büyük basamak olarak eklenir. Bütün turlar bittikten sonra son doğrusal tarama basamak toplamını verir.
Bu yaklaşım değişmezi çıplak biçimde gösterir: basamak dizisi her anda mevcut iki kuvvetinin tam ondalık gösterimidir.
Python uygulaması dilin yerleşik keyfi duyarlıklı tamsayılarını kullanır. Önce \(2^n\) tam olarak hesaplanır, sonra sonuç ondalık metne çevrilir ve karakterler rakam olarak toplanır. Kod çok daha kısa görünür, fakat matematiksel olarak yine aynı işlem yapılmaktadır: tam sayı elde edilir, ondalık basamaklar okunur, toplam alınır.
Java uygulaması standart kütüphanenin keyfi duyarlıklı tamsayı tipine dayanır. O da \(2^n\)'i tam olarak oluşturur, sonucu ondalık yazıya dönüştürür ve basamakları dolaşarak toplar. Böylece düşük seviyeli çok hassas aritmetik kütüphaneye bırakılır, fakat kullanılan matematik yine aynıdır.
Uygulamalar ayrıca problemdeki örneği denetim olarak kullanır; \(2^{15}\) için 26 sonucu doğrulanır. C++ sürümü buna ek olarak \(2^0=1\) taban durumunu da sınar.
Elle yapılan ondalık ikileştirme için son basamak sayısı \(k(n)=\Theta(n)\), \(t\). adımın işlediği basamak sayısı ise \(k(t)=\Theta(t)\)'dir. Bu nedenle süre
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
ve bellek kullanımı \(O(k(n))=O(n)\) olur.
Özel olarak \(n=1000\) için bu fazlasıyla yeterlidir; yalnızca birkaç yüz bin tek-basamak güncellemesi gerekir. Python ve Java tarafı optimize keyfi duyarlıklı aritmetik kullansa da bu giriş boyutunda onlar da aynı nedenle çok hızlıdır: tam değer sadece 302 ondalık basamak içerir.
La tarea consiste en hallar la suma de las cifras decimales de \(2^{1000}\). El ejemplo pequeño \(2^{15}=32768\) tiene suma de cifras \(3+2+7+6+8=26\), así que el problema real pide exactamente la misma operación sobre una potencia de dos mucho mayor.
La dificultad no está en una teoría profunda, sino en el tamaño del número. Como
$$\#\text{dígitos}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
\(2^{1000}\) no cabe en un entero ordinario de ancho fijo, y por eso la solución debe trabajar con su expansión decimal completa.
Escribamos la expansión decimal de \(2^n\) como
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9,$$
de modo que la cantidad buscada es
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
La idea clave es que la suma de cifras por sí sola no es un estado suficiente: al duplicar, los acarreos dependen de toda la escritura decimal. Por eso el objeto matemático correcto es el vector completo de cifras.
Supongamos que tras \(t\) duplicaciones conocemos las cifras de \(2^t\):
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
Guardar solo \(S(2^t)\) no permite deducir \(S(2^{t+1})\), porque el patrón de acarreos se pierde. La evolución correcta depende de todas las cifras \(a_i^{(t)}\).
Para pasar de \(2^t\) a \(2^{t+1}\), se recorren las cifras de menor a mayor peso con un acarreo. Tomamos \(c_0=0\) y definimos, para cada posición \(i\),
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
Como \(0\le a_i^{(t)}\le 9\) y \(c_i\in\{0,1\}\), siempre se cumple \(0\le u_i\le 19\), así que el siguiente acarreo vuelve a ser 0 o 1. Si se empieza en \(2^0=1\) y se repite esta transición \(n\) veces, se obtiene exactamente la representación decimal de \(2^n\).
La corrección del método escolar se apoya en un invariante sencillo. Después de procesar las primeras \(r\) cifras en un paso de duplicación, las cifras ya escritas coinciden exactamente con las últimas \(r\) cifras decimales de \(2^{t+1}\), y el acarreo contiene justo la parte que todavía debe trasladarse hacia las cifras más significativas.
Esto significa que el algoritmo no aproxima nada: solo redistribuye el valor correcto entre las cifras ya resueltas y el acarreo pendiente.
El número de cifras decimales de \(2^n\) viene dado por
$$10^{k-1}\le 2^n<10^k,$$
y por tanto
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
La longitud decimal crece linealmente con \(n\). La duplicación número \(t\) toca \(k(t)=\Theta(t)\) cifras, así que el trabajo total es
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
Para \(n=1000\), esa cota es muy pequeña en la práctica porque el resultado final solo tiene 302 cifras.
Veamos la recurrencia en un caso concreto. Partimos de
$$2^{11}=2048.$$
Al duplicar cifra a cifra obtenemos:
$$8\mapsto 16\Rightarrow 6\text{ con acarreo }1,$$
$$4\mapsto 2\cdot 4+1=9\Rightarrow 9\text{ con acarreo }0,$$
$$0\mapsto 0,\qquad 2\mapsto 4,$$
de donde \(2^{12}=4096\). Repitiendo:
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
Así,
$$S(2^{15})=3+2+7+6+8=26.$$
Como \(10\equiv 1\pmod 9\), todo número decimal es congruente módulo 9 con la suma de sus cifras. En consecuencia,
$$S(2^n)\equiv 2^n\pmod 9.$$
Esto no resuelve el problema por sí solo, pero sí da una verificación rápida. En el ejemplo, \(26\equiv 8\pmod 9\) y también \(2^{15}\equiv 8\pmod 9\).
Las implementaciones en C++, Python y Java calculan primero el valor exacto de \(2^n\) y luego suman sus cifras decimales. Lo que cambia entre ellas es la representación interna del entero grande.
La implementación en C++ sigue la derivación matemática casi línea por línea. Guarda las cifras decimales en orden little-endian, empieza con la cifra 1 y ejecuta un paso de duplicación por cada incremento del exponente. Cada recorrido aplica exactamente la recurrencia con acarreos; si al final queda un acarreo, se añade como nueva cifra más significativa. Después, un recorrido lineal suma las cifras.
Esta versión deja visible el invariante central: el arreglo de cifras es siempre la representación decimal exacta de la potencia actual de dos.
La implementación en Python aprovecha los enteros de precisión arbitraria incorporados en el lenguaje. Construye \(2^n\) exactamente, lo convierte en texto decimal y suma los caracteres como dígitos. El código es mucho más compacto, pero matemáticamente hace lo mismo: obtener el entero exacto, leer sus cifras y sumarlas.
La implementación en Java usa el tipo estándar de enteros de precisión arbitraria de la biblioteca. Calcula \(2^n\) sin pérdida de exactitud, transforma el resultado en cadena decimal y acumula las cifras. Igual que en Python, la aritmética multiprecisión se delega a la biblioteca, mientras que la idea matemática sigue siendo idéntica.
Además, las implementaciones incluyen comprobaciones sencillas basadas en el ejemplo del enunciado: verifican que el exponente 15 produce la suma 26, y la versión en C++ también confirma el caso base \(2^0=1\).
En el método manual de duplicación decimal, la longitud final es \(k(n)=\Theta(n)\), y la iteración número \(t\) procesa \(k(t)=\Theta(t)\) cifras. Por tanto, el tiempo total es
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
y la memoria necesaria es \(O(k(n))=O(n)\).
Para \(n=1000\), esto resulta sobradamente suficiente: solo hacen falta unos pocos cientos de miles de actualizaciones de una cifra. Las implementaciones de Python y Java usan bibliotecas optimizadas de precisión arbitraria, pero a esta escala también son inmediatas porque el valor exacto solo tiene 302 cifras decimales.
这道题要求计算 \(2^{1000}\) 的十进制数位和。题目先给出较小的例子 \(2^{15}=32768\)，它的数位和是 \(3+2+7+6+8=26\)；真正的任务只是把同样的操作应用到更大的二的幂上。
难点不在于幂本身，而在于十进制展开的长度。因为
$$\#\text{digits}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
所以 \(2^{1000}\) 已经远远超出普通定宽整数类型的范围，必须把它当作一个完整的多位十进制对象来处理。
把 \(2^n\) 的十进制展开写成
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9,$$
那么题目所求就是
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
真正需要解释的是怎样精确地得到这些十进制数字。这里最关键的观察是：只知道当前的数位和还不够，因为下一次乘 2 时是否产生进位，取决于完整的十进制表示，而不是取决于数位和本身。
设经过 \(t\) 次翻倍之后，我们已经知道 \(2^t\) 的所有十进制数字：
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
如果只保存 \(S(2^t)\)，一般无法推出 \(S(2^{t+1})\)，因为进位模式会丢失。决定下一步结果的真正状态，是整个数字向量 \(a_0^{(t)},a_1^{(t)},\dots\)，也就是完整的十进制展开。
从 \(2^t\) 变到 \(2^{t+1}\) 时，可以像手算那样从低位到高位逐位处理，并维护一个进位。令 \(c_0=0\)，对每个位置 \(i\) 定义
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
由于 \(0\le a_i^{(t)}\le 9\) 且 \(c_i\in\{0,1\}\)，所以总有 \(0\le u_i\le 19\)，因此新的进位仍然只能是 0 或 1。以 \(2^0=1\) 为初始状态，重复这个更新 \(n\) 次，就得到 \(2^n\) 的精确十进制表示。
这个逐位更新之所以正确，依赖于一个非常直接的不变量。一次翻倍过程中，当最低的前 \(r\) 位已经处理完成时，已经写出的这 \(r\) 位恰好就是 \(2^{t+1}\) 的最后 \(r\) 个十进制数字，而当前进位则完整保存了还没有并入更高位的那一部分数值。
也就是说，算法没有做任何近似；它只是把正确结果拆分成“已经确定的低位数字”和“等待加到更高位的进位”两部分。这个不变量正是十进制手算乘法的数学版本。
\(2^n\) 的十进制位数由不等式
$$10^{k-1}\le 2^n<10^k$$
决定，因此
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
这说明十进制长度随着 \(n\) 线性增长。第 \(t\) 次翻倍要接触 \(k(t)=\Theta(t)\) 位，因此总的单数字操作次数为
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
在本题中 \(n=1000\)，最终结果只有 302 位，所以这个看似朴素的方法实际上已经非常快。
用题目中的小例子可以直观看到递推。先从
$$2^{11}=2048$$
开始，逐位翻倍：
当个位 8 翻倍时，得到 \(16\)，所以当前位写成 \(6\)，并向下一位进 \(1\)。
接着处理下一位 \(4\)：\(2\cdot 4+1=9\)，所以这一位写成 \(9\)，进位回到 \(0\)。
$$0\mapsto 0,\qquad 2\mapsto 4,$$
于是得到 \(2^{12}=4096\)。继续重复同样的过程：
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
因此
$$S(2^{15})=3+2+7+6+8=26.$$
因为 \(10\equiv 1\pmod 9\)，任何十进制整数模 9 都与其数位和同余，所以
$$S(2^n)\equiv 2^n\pmod 9.$$
这条性质本身不足以直接给出答案，但很适合作为结果校验。对于上面的例子，\(26\equiv 8\pmod 9\)，而 \(2^{15}\equiv 8\pmod 9\)，两者完全一致。
C++、Python 和 Java 实现做的事情本质相同：先得到精确的 \(2^n\)，再把它写成十进制并求数位和。差别只在于中间大整数采用什么表示。
C++ 实现最直接地反映了上面的数学过程。它把十进制数字按低位在前的顺序存储，从单个数字 1 开始，每增加一次指数就做一轮“乘 2 加进位”的更新。每一轮都严格使用前面给出的递推；若最后还剩进位，就把它作为新的最高位追加进去。全部轮次结束后，再线性扫描一次，把所有数字相加。
这种写法把核心不变量完全暴露出来：数字数组在任意时刻都精确表示当前的二的幂，没有任何近似或截断。
Python 实现依赖语言原生的任意精度整数。它直接构造精确的 \(2^n\)，把结果转成十进制字符串，再把每个字符当成一位数字求和。代码虽然极短，但数学上并没有改变问题：仍然是先得到精确整数，再读取它的十进制数字。
Java 实现使用标准库提供的任意精度整数类型。它同样先精确求出 \(2^n\)，再转成十进制文本并累加各位数字。换句话说，Java 版本把底层多精度算术交给库来完成，而问题本身的数学结构并没有变化。
这些实现还带有简单的检查点，例如验证指数为 15 时数位和应为 26；其中 C++ 版本还额外检查了基例 \(2^0=1\)。
对于手工维护十进制数字的做法，最终位数 \(k(n)=\Theta(n)\)，第 \(t\) 次翻倍需要处理 \(k(t)=\Theta(t)\) 位，所以总时间为
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2),$$
空间为 \(O(k(n))=O(n)\)。
在本题的规模 \(n=1000\) 下，这个复杂度非常轻松，因为最终结果只有 302 位。Python 和 Java 虽然使用库中的任意精度整数实现，但在这个输入规模上同样几乎是瞬间完成，原因仍然是精确值本身并不长。
Нужно найти сумму десятичных цифр числа \(2^{1000}\). В условии дан меньший пример: \(2^{15}=32768\), и сумма его цифр равна \(3+2+7+6+8=26\). Реальная задача делает то же самое, только для гораздо большей степени двойки.
Сложность здесь связана не с глубокими теоремами, а с размером числа. Поскольку
$$\#\text{цифр}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
число \(2^{1000}\) не помещается в обычный целочисленный тип фиксированной ширины. Поэтому нужно работать с его полной десятичной записью.
Запишем десятичное представление числа \(2^n\) так:
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9.$$
Тогда искомая величина равна
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
Но вычислить эту сумму напрямую по предыдущей сумме нельзя: переносы при умножении на 2 зависят от всех цифр сразу. Поэтому правильный объект состояния — не сумма цифр, а весь десятичный вектор.
Пусть после \(t\) удвоений нам известны цифры числа \(2^t\):
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
Если хранить только \(S(2^t)\), то, вообще говоря, нельзя восстановить \(S(2^{t+1})\): информация о переносах исчезает. Следовательно, естественное состояние — это весь набор цифр \(a_i^{(t)}\).
Переход от \(2^t\) к \(2^{t+1}\) выполняется поразрядно, от младших цифр к старшим, с переносом. Положим \(c_0=0\), а затем для каждой позиции \(i\) определим
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
Так как \(0\le a_i^{(t)}\le 9\) и \(c_i\in\{0,1\}\), всегда выполняется \(0\le u_i\le 19\), а значит, следующий перенос снова равен только 0 или 1. Если начать с \(2^0=1\) и повторить этот шаг \(n\) раз, получится точная десятичная запись \(2^n\).
Корректность школьного алгоритма опирается на простой инвариант. После обработки первых \(r\) цифр в одном шаге удвоения уже записанные цифры в точности совпадают с последними \(r\) цифрами числа \(2^{t+1}\), а текущий перенос хранит именно ту часть значения, которую еще нужно добавить к старшим разрядам.
То есть алгоритм ничего не приближает и ничего не теряет: он просто переносит часть правильного значения вверх по разрядам. Это и есть формальная причина точности поразрядного метода.
Количество десятичных цифр числа \(2^n\) определяется неравенством
$$10^{k-1}\le 2^n<10^k,$$
откуда следует
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
Значит, длина десятичной записи растет линейно по \(n\). На \(t\)-м шаге удвоения приходится обрабатывать \(k(t)=\Theta(t)\) цифр, поэтому общий объем работы равен
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
Для \(n=1000\) это очень мало на практике, потому что итоговое число содержит всего 302 цифры.
Покажем работу рекурсии на конкретном примере. Возьмем
$$2^{11}=2048.$$
Удваиваем поразрядно:
Для младшей цифры \(8\) получаем \(16\), значит, на текущем месте остается \(6\), а перенос равен \(1\).
Следующая цифра \(4\) дает \(2\cdot 4+1=9\), поэтому записывается \(9\), а перенос снова становится \(0\).
$$0\mapsto 0,\qquad 2\mapsto 4,$$
и получаем \(2^{12}=4096\). Далее:
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
Следовательно,
$$S(2^{15})=3+2+7+6+8=26.$$
Поскольку \(10\equiv 1\pmod 9\), любое десятичное число сравнимо по модулю 9 с суммой своих цифр. Поэтому
$$S(2^n)\equiv 2^n\pmod 9.$$
Это не заменяет вычисление, но дает хороший тест правильности. В нашем примере \(26\equiv 8\pmod 9\), и одновременно \(2^{15}\equiv 8\pmod 9\).
Реализации на C++, Python и Java в итоге делают одно и то же: получают точное значение \(2^n\), а затем суммируют его десятичные цифры. Различается только способ хранения большого числа во время вычисления.
В версии на C++ математическая идея выражена буквально. Десятичные цифры хранятся в порядке от младшей к старшей, стартовое состояние равно 1, и для каждого увеличения показателя выполняется один поразрядный шаг удвоения. На каждом проходе используется именно описанная выше рекурсия с переносом, а оставшийся в конце перенос добавляется как новая старшая цифра. После завершения всех шагов цифры просто суммируются линейным проходом.
Эта реализация особенно наглядна: массив цифр в любой момент является точной десятичной записью текущей степени двойки.
В реализации на Python используются встроенные целые числа произвольной точности. Сначала строится точное значение \(2^n\), затем оно переводится в десятичную строку, и символы суммируются как цифры. Код получается очень коротким, но математическая схема остается той же самой.
Реализация на Java опирается на стандартный библиотечный тип целых чисел произвольной точности. Он позволяет точно возвести 2 в нужную степень, после чего результат превращается в десятичный текст и цифры суммируются. Низкоуровневая многоточечная арифметика делегируется библиотеке, но сама математическая постановка не меняется.
Кроме того, реализации содержат простые контрольные проверки: пример \(2^{15}\mapsto 26\) подтверждается явно, а версия на C++ отдельно проверяет и базовый случай \(2^0=1\).
Для ручного метода с десятичным массивом итоговая длина равна \(k(n)=\Theta(n)\), а \(t\)-е удвоение затрагивает \(k(t)=\Theta(t)\) цифр. Отсюда получаем
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
по времени и \(O(k(n))=O(n)\) по памяти.
При \(n=1000\) этого более чем достаточно: требуется лишь несколько сотен тысяч одноразрядных операций. В Python и Java используются оптимизированные библиотеки длинной арифметики, но на таком размере входа они тоже работают практически мгновенно, поскольку точное число имеет только 302 десятичные цифры.
المطلوب هو إيجاد مجموع الأرقام العشرية للعدد \(2^{1000}\). يعرض السؤال مثالًا أصغر هو \(2^{15}=32768\)، ومجموع أرقامه \(3+2+7+6+8=26\)، ثم يطلب تنفيذ الفكرة نفسها على قوة أكبر بكثير للعدد 2.
الصعوبة هنا ليست في نظرية الأعداد بقدر ما هي في حجم العدد نفسه. إذ إن
$$\#\text{digits}(2^{1000})=\left\lfloor 1000\log_{10}2\right\rfloor+1=302,$$
ولذلك فإن \(2^{1000}\) لا يمكن تخزينه في نوع صحيح عادي ذي عرض ثابت، ويجب التعامل معه بوصفه تمثيلًا عشريًا كاملًا متعدد الخانات.
لنكتب التمثيل العشري لـ \(2^n\) على الصورة
$$2^n=\sum_{i=0}^{k-1} d_i 10^i,\qquad 0\le d_i\le 9,$$
وعندئذ تكون الكمية المطلوبة هي
$$S(2^n)=\sum_{i=0}^{k-1} d_i.$$
لكن المهم هو كيفية الوصول إلى هذه الخانات بدقة. فمجموع الأرقام وحده لا يكفي لوصف الحالة، لأن المضاعفة تولد حمولًا تعتمد على كامل التمثيل العشري، لا على المجموع وحده.
افترض أننا بعد \(t\) عمليات مضاعفة نعرف خانات \(2^t\):
$$2^t=\sum_{i=0}^{m_t-1} a_i^{(t)}10^i.$$
إذا احتفظنا فقط بالقيمة \(S(2^t)\)، فلن نستطيع عمومًا تحديد \(S(2^{t+1})\)، لأن نمط الحمول يضيع. ولهذا فإن الكائن الرياضي الطبيعي هنا هو متجه الخانات العشرية كله.
للانتقال من \(2^t\) إلى \(2^{t+1}\)، نعالج الخانات من الأقل وزنًا إلى الأعلى مع حمل. نضع \(c_0=0\)، ثم نعرّف لكل موضع \(i\):
$$u_i=2a_i^{(t)}+c_i,\qquad a_i^{(t+1)}=u_i\bmod 10,\qquad c_{i+1}=\left\lfloor\frac{u_i}{10}\right\rfloor.$$
وبما أن \(0\le a_i^{(t)}\le 9\) و\(c_i\in\{0,1\}\)، فنحصل دائمًا على \(0\le u_i\le 19\)، أي إن الحمل التالي لا يكون إلا 0 أو 1. وإذا بدأنا من \(2^0=1\) وكررنا هذه العملية \(n\) مرة، حصلنا على التمثيل العشري الدقيق للعدد \(2^n\).
صحة هذه الطريقة تقوم على ثابت بسيط. بعد معالجة أول \(r\) خانات في خطوة مضاعفة واحدة، تكون الخانات المكتوبة بالفعل هي تمامًا آخر \(r\) خانات عشرية للعدد \(2^{t+1}\)، بينما يحمل المتغير الخاص بالحمل الجزء الذي يجب نقله إلى الخانات الأعلى التي لم تُعالج بعد.
بمعنى آخر، الخوارزمية لا تقرّب شيئًا ولا تهمل شيئًا؛ إنها فقط تؤجل جزءًا من القيمة الصحيحة في الحمل حتى يصل إلى الموضع المناسب. وهذا هو الأساس الرياضي لطريقة الضرب المدرسية خانةً بخانة.
عدد الخانات العشرية للعدد \(2^n\) يتحدد من
$$10^{k-1}\le 2^n<10^k,$$
ومنها
$$k=\left\lfloor n\log_{10}2\right\rfloor+1.$$
إذًا يزداد طول التمثيل العشري خطيًا مع \(n\). وفي الخطوة رقم \(t\) نلمس \(k(t)=\Theta(t)\) خانات، لذا يكون مجموع العمل
$$\sum_{t=1}^n \Theta(k(t))=\Theta\!\left(\sum_{t=1}^n t\right)=\Theta(n^2).$$
وعند \(n=1000\) يكون هذا صغيرًا جدًا عمليًا، لأن النتيجة النهائية لا تتجاوز 302 خانة عشرية.
لنر العلاقة الرجوعية في مثال ملموس. نبدأ من
$$2^{11}=2048.$$
ثم نضاعف خانة بخانة:
عند مضاعفة الخانة \(8\) نحصل على \(16\)، لذلك تبقى \(6\) في هذا الموضع ويكون الحمل \(1\).
ثم نعالج الخانة التالية \(4\): لدينا \(2\cdot 4+1=9\)، فنكتب \(9\) ويعود الحمل إلى \(0\).
$$0\mapsto 0,\qquad 2\mapsto 4,$$
فنحصل على \(2^{12}=4096\). وبالتكرار:
$$2^{13}=8192,\qquad 2^{14}=16384,\qquad 2^{15}=32768.$$
وعليه
$$S(2^{15})=3+2+7+6+8=26.$$
بما أن \(10\equiv 1\pmod 9\)، فإن أي عدد عشري يطابق مجموع أرقامه بترديد 9. لذلك
$$S(2^n)\equiv 2^n\pmod 9.$$
هذه الحقيقة لا تعطي الجواب وحدها، لكنها فحص ممتاز للصحة. ففي المثال السابق لدينا \(26\equiv 8\pmod 9\)، وكذلك \(2^{15}\equiv 8\pmod 9\).
تنفذ تطبيقات C++ وPython وJava الفكرة الرياضية نفسها: تحسب القيمة الدقيقة لـ \(2^n\)، ثم تجمع خاناتها العشرية. الاختلاف بينها هو فقط في طريقة تمثيل العدد الكبير أثناء الحساب.
تنفيذ C++ يعكس الاشتقاق الرياضي مباشرة. فهو يخزن الخانات العشرية بترتيب يبدأ من الخانة الأقل أهمية، ويبدأ من الرقم 1، ثم يجري خطوة مضاعفة واحدة لكل زيادة في الأس. كل خطوة تطبق علاقة الحمل المذكورة أعلاه بدقة، وإذا بقي حمل في النهاية أضيف بوصفه خانةً أعلى جديدة. وبعد اكتمال جميع الخطوات تُجمع الخانات بمسح خطي واحد.
هذه النسخة تُظهر الثابت الأساسي بوضوح: مصفوفة الخانات تمثل دائمًا القوة الحالية للعدد 2 تمثيلًا عشريًا صحيحًا تمامًا.
تنفيذ Python يعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة المدمجة في اللغة. فهو يبني \(2^n\) بدقة كاملة، ثم يحول النتيجة إلى نص عشري ويجمع الرموز بوصفها أرقامًا. الكود أقصر كثيرًا، لكن البنية الرياضية هي نفسها تمامًا.
تنفيذ Java يستخدم نوع الأعداد الصحيحة ذات الدقة غير المحدودة الموجود في المكتبة القياسية. يحسب \(2^n\) دون أي فقدان في الدقة، ثم يحول الناتج إلى سلسلة عشرية ويجمع خاناتها. وهكذا تُفوَّض التفاصيل منخفضة المستوى للحساب متعدّد الدقة إلى المكتبة، بينما تبقى الفكرة الرياضية نفسها بلا تغيير.
وتحتوي هذه التطبيقات أيضًا على نقاط تحقق بسيطة مأخوذة من نص المسألة، مثل التأكد من أن الأس 15 يعطي المجموع 26، بينما تضيف نسخة C++ تحققًا إضافيًا للحالة الأساسية \(2^0=1\).
في طريقة المضاعفة العشرية اليدوية يكون عدد الخانات النهائي \(k(n)=\Theta(n)\)، وتتعامل الخطوة رقم \(t\) مع \(k(t)=\Theta(t)\) خانات. لذلك يكون الزمن الكلي
$$O\!\left(\sum_{t=1}^n k(t)\right)=O(n^2)$$
ويكون استهلاك الذاكرة \(O(k(n))=O(n)\).
وبالنسبة إلى \(n=1000\) فهذا أكثر من كافٍ، إذ لا نحتاج إلا إلى بضع مئات الآلاف من تحديثات خانة واحدة. أما نسختا Python وJava فتعتمدان على مكتبات محسنة للأعداد كبيرة الدقة، لكنهما تكونان سريعتين جدًا هنا للسبب نفسه: القيمة الدقيقة نفسها لا تتجاوز 302 خانة عشرية.