Pythonで数値がアキレス数かどうかを判定する方法

ある整数 n が与えられたとき、その数がアキレス数（Achilles number）であるかどうかを判定しましょう。

アキレス数とは、「べき乗数（powerful number）」であるにもかかわらず「完全累乗数」ではない数のことです。
べき乗数とは、すべての素因数 p に対して p² もその数を割り切るような数 N を指します。一方、完全累乗数とは、m^k（k ≥ 2）の形で表される数（例：平方数、立方数など）です。
なお、アキレス数という名前はギリシャ神話の英雄アキレスにちなんだもので、「強力でありながら完全ではない」という「アキレスのかかと」の故事に由来しています。

アキレス数の例としては、72、108、200、288、392、432、500、648、675、800、864、968、972、1125 などが挙げられます。

たとえば入力が 108 の場合、出力は True になります。108 = 2² × 3³ と素因数分解でき、各素因数の指数がどれも 2 以上であるためべき乗数であり、同時に完全累乗数ではないためです。

解決のためのアプローチ

この問題を解くには、次の手順に従います。

• 関数 check_powerful() を定義する（引数：n）
  • n が偶数である間、以下を繰り返します。
    • カウンター p を 0 で初期化します。
    • n が偶数である限り、n を 2 で割りながら p を増やし続けます。
    • p が 1 になった場合（素因数 2 が 1 回しか現れない場合）、False を返します。
  • p を int(√n) + 1 とします。
  • factor を 3 から p まで 2 ずつ増加させながら、以下を繰り返します。
    • カウンター p を 0 で初期化します。
    • n が factor で割り切れる間、n を factor で割りながら p を増やし続けます。
    • p が 1 になった場合、False を返します。
  • 最後に、n が 1 と等しければ True を返します。
• 関数 check_power() を定義する（引数：a）
  • a が 1 の場合は True を返します。
  • i を 2 から a まで 1 ずつ増やしながら、以下を繰り返します。
    • val = log(a) / log(i)（自然対数ベース）を計算します。
    • (val − int(val)) < 0.00000001 が成立すれば、True を返します。
  • ループが終わったら False を返します。
• メイン処理では、以下を行います。
  • check_powerful(n) が True かつ check_power(n) が False の場合、True を返します。
  • それ以外の場合は False を返します。

アルゴリズムのポイント

check_powerful() は、各素因数の出現回数（指数）を数え、1 回しか現れない素因数が存在した時点で「べき乗数ではない」と判定します。一方、check_power() は対数を利用して、a が m^k の形で表せるかどうか（完全累乗数かどうか）を確認します。この 2 つの関数を組み合わせることで、アキレス数の条件を正確に判定できます。

実装例

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

from math import sqrt, log

def check_powerful(n):
    while (n % 2 == 0):
        p = 0
        while (n % 2 == 0):
            n /= 2
            p += 1
        if (p == 1):
            return False
    p = int(sqrt(n)) + 1
    for factor in range(3, p, 2):
        p = 0
        while (n % factor == 0):
            n = n / factor
            p += 1
        if (p == 1):
            return False
    return (n == 1)

def check_power(a):
    if (a == 1):
        return True
    p = int(sqrt(a)) + 1
    for i in range(2, a, 1):
        val = log(a) / log(i)
        if ((val - int(val)) < 0.00000001):
            return True
    return False

def isAchilles(n):
    if (check_powerful(n) == True and check_power(n) == False):
        return True
    else:
        return False

n = 108
print(isAchilles(n))

入力

108

出力

True