1. はじめに
本記事では、Project Euler の問題番号16の Power Digit Sum の解説を行う。
2. 問題概要
$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = 26.$
What is the sum of digits of the number $2^{1000}$?
この問題では、$2^{1000}$ の各桁の合計を求めるものである。
3. 計算の課題と扱い方
$2^{1000}$ は $302$ 桁の非常に大きな整数であり、固定長整数（32 bit / 64 bit）では表現しきれない。
そのため、大きな整数を配列で表現し、繰り上がり処理を行う必要がある。
Python の場合は、任意精度整数であるため、オーバーフローが発生しないが、ここでは任意精度を持たない言語の解法を示す。
4. 桁数の見積もり
配列を使うために、桁数を求める。
10進法で
$$
N > 0
$$
の桁数は、
$$
\text{digits}(N) = \lfloor \log_{10}{N} \rfloor + 1
$$
である。
今回知りたいのは、
$$
N = 2^{1000}
$$
なので、
$$
digits(2^{1000}) = \lfloor 1000 \log_{10}{2} \rfloor + 1
$$
ここで、$log_{10}{2} \approx 0.3010$ なので、
$$
1000 \log_{10}{2} \approx 1000 \times 0.3010 = 301.0
$$
これを使うと桁数は $302$ であると求めることができる。
5. 配列を用いた具体的な解法
任意精度整数を持たない言語では、大きな整数を配列で表現することで、$2^{1000}$ を求めることができる。
5.1. 数の表現方法
- 各桁の $10$ 進数の $1$ 桁として配列に保持する
- 例えば $32768$ なら
$$
[8, 6, 7, 2, 3]
$$
のように、下の桁から順に格納する
初期状態は、$2^{0} = 1$ なので、
$$
digits = [1]
$$
から始める。
5.2. 2倍演算（1回分）
ある配列 digits に対して、2倍算を行うときは、次の手順に従う。
- 繰り上がりを 0 に初期化
- 各桁
digits[i]について、
$$
\text{temp} = 2 \times digits[i] + \text{carry}
$$
を計算し、- 新しい桁 = $\text{temp} % 10$
- 新しい $\text{carry} = \lfloor \dfrac{\text{temp}}{10} \rfloor$ （整数除算）
とする。
- すべての桁を処理し終えた後、carry が 0 でない場合追加の桁として末尾に
pushする
これを 1000 回繰り返すことで、配列に $2^{1000}$ の全桁が格納される。
5.3. 各桁の和の計算
最終的な配列 digits が $2^{1000}$ の各桁を保持しているので、
$$
\text{answer} = \sum_{i=0}^{301} \text{digits}[i]
$$
となる。
5.4. Pythonによる解法
Python で実装したコードを次に示す。
digits = [1]
for i in range(1000):
carry = 0
for j in range(len(digits)):
cal = digits[j] * 2 + carry
digits[j] = cal % 10
carry = cal // 10
if carry > 0:
digits.append(carry)
answer = sum(digits)
print(answer)
6. 参考サイト
[1]. Project Euler.net