Pythonで数値が『異なる3の累乗の和』として表せるか判定するプログラム

問題の概要

ある整数 n が与えられたとき、その数を互いに異なる3の累乗の和として表すことができるかどうかを判定するのが、この記事のテーマです。

ここでいう「3の累乗」とは、y = 3ⁿ(x は整数)と書ける数のことです。具体的には 1(3⁰)、3(3¹)、9(3²)、27(3³)、81(3⁴)… といった数値が該当します。

入力例と出力例

たとえば n = 117 の場合を見てみましょう。

117 = 3⁴ + 3³ + 3² = 81 + 27 + 9

このように異なる3の累乗だけで表せるため、答えは True となります。

解き方：大きい累乗から順に引いていく貪欲法

この問題は、大きな累乗から順番に引き算していく貪欲法(グリーディ法)でシンプルに解けます。手順は次のとおりです。

• i を 16 から 0 まで 1 ずつ減らしながらループする
• n が 3ⁱ 以上であれば、n から 3ⁱ を引く
• ループ終了後、n が 0 より大きければ False を返す
• それ以外は True を返す

なぜこの方法で正しく判定できるのか？

ポイントは、各累乗を高々1回しか使わないことです。3⁰ から 3ⁱ⁻¹ までの合計は (3ⁱ − 1) ÷ 2 となり、必ず 3ⁱ より小さくなります。そのため、もし途中で同じ累乗が2回必要になる状況(3進法である桁が2になるケース)が発生すると、残りの小さい累乗では埋めきれず、最後に n が 0 より大きい状態で残ります。

言い換えると、「n が異なる3の累乗の和で表せる」ということは「n を3進法で表したときに各桁が 0 か 1 のみで構成される」ことと同じです。この貪欲法は3進法への変換と等価な処理を行っているため、正しく判定できます。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(n):
   for i in range(16, -1, -1):
      if n >= pow(3, i):
         n -= pow(3, i)

   if n > 0:
      return False

   return True

n = 117
print(solve(n))

コードのポイント

• range(16, -1, -1):3¹⁶ は約4,300万なので、この範囲を調べれば十分です。扱う数値がさらに大きい場合は上限を増やしてください。
• pow(3, i):3のi乗を計算します。
• 各 i に対して処理は1回しか行われないため、同じ累乗が複数回使われることはありません。

実行結果

入力：

117

出力：

True

計算量は累乗の個数分のループのみのため、O(log₃ n) と非常に効率的です。

まとめ

整数 n が異なる3の累乗の和で表せるかどうかは、大きい累乗から順に引いていく貪欲法で簡単に判定できます。「3進法の各桁が 0 か 1 だけで構成されているか」を確認する問題と捉えると、仕組みがより理解しやすくなります。