Pythonで最小の「良い基数（グッドベース）」を二分探索で求める方法

問題の概要

整数 n が与えられたとき、n を k 進法で表した際にすべての桁が 1 になるような k（k ≥ 2）を「良い基数（グッドベース）」と呼びます。数値 n が文字列として与えられるので、最小の良い基数を文字列として返します。

例えば n = 121 の場合、答えは 3 です。121 を 3 進法で表すと 11111 となり、すべての桁が 1 になるためです（実際に 1 + 3 + 9 + 27 + 81 = 121 が成り立ちます）。

解法のアプローチ

この問題は二分探索を用いることで効率的に解けます。考え方のポイントは次の通りです。

• 基数 k・桁長 length のときの「全桁が 1 の数」は、等比級数の和 1 + k + k² + … + k^(length−1) として表せる。
• この和が n と一致するような k を、桁長ごとに二分探索で求める。
• 桁長が長いほど対応する基数は小さくなるため、桁長を大きい方（64）から小さい方へ順に調べれば、最初に見つかったものが最小の良い基数となる。
• どの桁長でも見つからない場合は n − 1 を返せばよい。n を (n − 1) 進法で表すと必ず 11 になるため、これが常に解となるからである。

具体的な手順

1. getSum(x, length) メソッドを定義する
   • mainSum := 0、temp := 1 と初期化する
   • i を 0 から length − 1 まで繰り返す：mainSum += temp のあとに temp *= x
   • mainSum を返す
2. check(n, length) メソッドを定義する
   • low := 2、high := n とする
   • high ≥ low の間、以下を繰り返す：
     • mid := low + (high − low) // 2
     • mainSum := getSum(mid, length)
     • mainSum == n なら mid を返す
     • mainSum > n なら high := mid − 1
     • それ以外は low := mid + 1
   • 見つからなければ -1 を返す
3. メイン処理（smallestGoodBase）
   • 入力文字列 n を整数に変換する
   • i を 64 から 2 まで降順にループし、x = check(n, i) を計算する。x ≥ 2 であれば文字列に変換して返す
   • ループが終了しても見つからなければ、str(n − 1) を返す

以下の実装例を見ると、より理解が深まるでしょう。

実装例

class Solution(object):
    def getSum(self, x, length):
        # 1 + x + x^2 + ... + x^(length-1) を計算する
        mainSum = 0
        temp = 1
        for _ in range(length):
            mainSum += temp
            temp *= x
        return mainSum

    def check(self, n, length):
        # 二分探索で n に一致する基数を探す
        low, high = 2, n
        while high >= low:
            mid = low + (high - low) // 2
            mainSum = self.getSum(mid, length)
            if mainSum == n:
                return mid
            elif mainSum > n:
                high = mid - 1
            else:
                low = mid + 1
        return -1

    def smallestGoodBase(self, n):
        n = int(n)
        # 桁長が長いほど基数は小さくなるため、大きい桁長から順に調べる
        for i in range(64, 1, -1):
            x = self.check(n, i)
            if x >= 2:
                return str(x)
        return str(n - 1)

ob = Solution()
print(ob.smallestGoodBase("121"))

入力

"121"

出力

3

補足：なぜ 3 が最小なのか

2 進法で全桁が 1 になる数は 2^m − 1 の形に限られます。2^6 − 1 = 63、2^7 − 1 = 127 であり、121 には該当しないため、基数 2 は使えません。したがって、全桁が 1 になる最小の基数は 3 となります。

計算量について

想定される入力は 64 ビット整数（最大 10^18 程度）であるため、必要な桁長は最大でも 64 程度です。各桁長に対する二分探索は O(log n) ステップ程度で収まるため、アルゴリズム全体としても非常に高速に動作します。