問題の理解
素因子が3、5、7のみである数列のk番目の数を求めるアルゴリズムを設計する必要があります。この数列の最初のいくつかの数は1, 3, 5, 7, 9, 15, 21, 25, 27, 35...となります。
この問題を理解するために、まず条件を明確にしましょう。対象となる数は、素因数分解したときに素因子として3、5、7しか持たない数です。例えば：
- 1：素因子を持たない（特別ケースとして含まれる）
- 3：素因子は3
- 5：素因子は5
- 7：素因子は7
- 9：素因子は3×3
- 15：素因子は3×5
- 21：素因子は3×7
- 25：素因子は5×5
- 27：素因子は3×3×3
- 35：素因子は5×7
基本的なアプローチ
最も直接的なアプローチは、1から順に各数が条件を満たすかチェックし、k個の条件を満たす数が見つかるまで続ける方法です。
ある数が条件を満たすかどうかを確認するには、その数を3、5、7で割り続け、最終的に1になれば条件を満たします。例えば：
- 15 ÷ 3 = 5、5 ÷ 5 = 1 → 条件を満たす
- 11 ÷ 3で割り切れない、11 ÷ 5で割り切れない、11 ÷ 7で割り切れない → 1にならないので条件を満たさない
以下はこのアプローチを実装したコードです：
class PrimeFactorChecker:
def has_only_allowed_primes(self, num):
# 3, 5, 7で割り続ける
for prime in [3, 5, 7]:
while num % prime == 0:
num = num // prime
return num == 1
class KthMagicNumberFinder:
def find_kth_number(self, k):
count = 0
current_num = 1
checker = PrimeFactorChecker()
while True:
if checker.has_only_allowed_primes(current_num):
count += 1
if count == k:
return current_num
current_num += 1
# 使用例
finder = KthMagicNumberFinder()
result = finder.find_kth_number(5)
print(result) # 出力: 7
このアプローチはシンプルですが、kが大きくなると計算時間が非常に長くなります。より効率的な方法が必要です。
三ポインタ法による効率的な解決
より効率的な解決策として、三ポインタ法（three pointers）を使用できます。これは「醜数問題」（ugly number problem）の変形として知られています。
このアプローチの基本的な考え方は、数列を生成しながら、既に生成された数に3、5、7を乗じて次の数を生成することです。三つのポインタを使って、各基数（3、5、7）に対して次に生成すべき数を追跡します。
アルゴリズムのステップ
- 初期化：結果リストを[1]で開始し、三つのポインタi3, i5, i7を0に設定
- 反復処理：
- 各ポインタが指す数に対応する基数（3、5、7）を乗じて次の候補数を生成
- これらの候補数の中から最小値を選択
- 重複を避けるため、最小値が直前に追加した数と異なる場合のみ結果リストに追加
- 最小値がどの基数で生成されたかに応じて対応するポインタを進める
- 結果リストの長さがkになるまで繰り返す
以下は三ポインタ法を実装したコードです：
def find_kth_magic_number(k):
# 最初の数は1
sequence = [1]
# 3つの基数に対するポインタ
ptr3 = ptr5 = ptr7 = 0
while len(sequence) < k:
# 次の候補数を生成
next3 = sequence[ptr3] * 3
next5 = sequence[ptr5] * 5
next7 = sequence[ptr7] * 7
# 最小値を選択
next_value = min(next3, next5, next7)
# 重複を避ける
if next_value != sequence[-1]:
sequence.append(next_value)
# 対応するポインタを進める
if next_value == next3:
ptr3 += 1
if next_value == next5:
ptr5 += 1
if next_value == next7:
ptr7 += 1
return sequence[-1]
# 使用例
result = find_kth_magic_number(5)
print(result) # 出力: 7
アルゴリズムの例
このアルゴリズムがどのように動作するか、k=7の場合を見てみましょう：
- 初期状態: sequence = [1], ptr3=ptr5=ptr7=0
- 1回目: next3=3, next5=5, next7=7 → min=3 → sequence=[1,3], ptr3=1
- 2回目: next3=9, next5=5, next7=7 → min=5 → sequence=[1,3,5], ptr5=1
- 3回目: next3=9, next5=15, next7=7 → min=7 → sequence=[1,3,5,7], ptr7=1
- 4回目: next3=9, next5=15, next7=21 → min=9 → sequence=[1,3,5,7,9], ptr3=2
- 5回目: next3=15, next5=15, next7=21 → min=15 → sequence=[1,3,5,7,9,15], ptr3=3, ptr5=2
- 6回目: next3=21, next5=25, next7=21 → min=21 → sequence=[1,3,5,7,9,15,21], ptr3=4, ptr7=2
このようにして、7番目の数として21が得られます。
複雑度分析
三ポインタ法の時間計算量はO(k)です。各ステップで定数時間の操作を行い、k個の数を生成する必要があるためです。空間計算量もO(k)で、結果リストを保持する必要があるためです。
このアプローチは、kが大きくなっても効率的に動作し、基本的な逐次チェック法よりもはるかに高速です。