Pythonで指定したnに対する数列Sの最後の桁を求めるプログラム

ある値 n が与えられたとき、次の式で定義される数列 S の最後の桁(一の位)を求めることを考えます。

$$\sum_{i=0\: 2^{^{i}}\leqslant n}^{\alpha } \sum_{j=0}^{n} 2^{2^{^{i}+2j}}$$

例えば、入力が n = 2 の場合、出力は 6 になります。条件 2^i ≤ n を満たすのは i = 0 と i = 1 のみなので、計算は次のようになります。

• S₀ = 2^(2^0 + 0) + 2^(2^0 + 2) + 2^(2^0 + 4) = 42
• S₁ = 2^(2^1 + 0) + 2^(2^1 + 2) + 2^(2^1 + 4) = 84

合計は 42 + 84 = 126 となるため、答えは最後の桁の 6 です。

解法のアプローチ

巨大な冪乗をそのまま計算すると処理時間やメモリの面で不利になるため、ここでは「一の位だけを追跡する」という工夫を使います。手順は以下の通りです。

1. total を 0、temp を 1 で初期化します。
2. temp が n 以下である間、次の処理を繰り返します。
   • total に 2^temp mod 10(2 の temp 乗の一の位)を加算します。
   • temp を 2 倍します(temp は 1, 2, 4, 8, … と変化し、式の中の 2^i に対応します)。
3. ループ終了後、n が奇数なら total に 5 を掛け(1 + 4)、偶数ならそのままにして、10 で割った余りを求めます。
4. total を返します。

なぜこのアルゴリズムで正しく求まるのか

各 i について、内側の和は次のように変形できます。

2^(2^i) × (4^0 + 4^1 + … + 4^n)

ここで 4^k の一の位は「1, 4, 6, 4, 6, …」と循環するため、次のことが言えます。

• n が偶数の場合： 括弧内の和の一の位は 1 になり、内側の和の一の位は 2^(2^i) の一の位と一致します。
• n が奇数の場合： 括弧内の和の一の位は 5 になり、内側の和の一の位は 2^(2^i) × 5 の一の位になります。

したがって、「temp = 1, 2, 4, … に対する 2^temp の一の位の総和」を求め、n の偶奇に応じて 1 倍または 5 倍すれば、数列全体の一の位が得られます。計算量は O(log n) と非常に効率的です。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(n):
   total = 0
   temp = 1
   while (temp <= n):
      total += pow(2, temp, 10)
      temp *= 2
   total = total * (1 + (4 if n % 2 == 1 else 0)) % 10
   return total

n = 2
print(solve(n))

pow(2, temp, 10) は「2 の temp 乗を 10 で割った余り」を高速に計算できる Python の組み込み関数です。巨大な冪乗を実際に展開しないため、n が大きくなっても瞬時に答えを得られます。

入力

2

出力

6

まとめ

本記事では、二重シグマで定義される数列 S の最後の桁を Python で求める方法を紹介しました。冪乗の一の位が循環する性質と、n の偶奇による補正(奇数なら 5 倍)を組み合わせることで、O(log n) の計算量で効率よく答えを導けるのがポイントです。