Pythonで数がトロイ数（Trojan Number）かどうかを判定する方法

ある数 n が与えられたとき、それが「トロイ数（Trojan Number）」であるかどうかを判定します。トロイ数とは、「強い数（Strong Number）」であるにもかかわらず、累乗数（perfect power）ではない数のことを指します。

ここで、数 n が強い数であるとは、n のすべての素因数 p に対して p² もまた n の約数となることを意味します。言い換えると、すべての素因数が少なくとも2回現れる数です。トロイ数は必ず強い数ですが、その逆は成り立ちません。つまり、すべての強い数がトロイ数というわけではなく、a^b の形で表せないものだけがトロイ数となります。

たとえば入力が 72 の場合、出力は True になります。72 は (6×6×2) = (6² × 2) と表せるため、素因数がすべて2回以上現れる強い数でありながら、累乗数ではないからです。

解法のアプローチ

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

• 関数 check_perfect_pow() を定義する。引数として n を受け取る
• n が 1 と等しい場合は True を返す
• x を 2 から √n の整数部分 + 1 まで繰り返す：
  • y := 2
  • p = x^y
  • p ≤ n かつ p > 0 の間、以下を繰り返す：
    • p が n と等しければ True を返す
    • y := y + 1
    • p = x^y
• False を返す
• 関数 check_strong_num() を定義する。引数として n を受け取る
• count := 各数値の出現回数を保持する辞書（初期値はすべて 0）
• n を 2 で割り切れる間、以下を繰り返す：
  • n := n // 2（整数除算）
  • count[2] := count[2] + 1
• i を 3 から √n の整数部分 + 1 まで 2 ずつ増やしながら繰り返す：
  • n が i で割り切れる間、以下を繰り返す：
    • n := n // i（整数除算）
    • count[i] := count[i] + 1
• n > 2 の場合は count[n] := count[n] + 1
• flag := 0
• count の各キーと値について：
  • 値が 1 であれば flag := 1 としてループを抜ける
• flag が 1 なら False を返す
• True を返す
• メイン処理では、check_perfect_pow(n) が False かつ check_strong_num(n) が True のときに true を返し、それ以外は false を返す

実装例

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

from math import sqrt, pow
def check_perfect_pow(n):
   if n == 1:
      return True
   for x in range(2, int(sqrt(n)) + 1):
      y = 2
      p = x**y
      while p <= n and p > 0:
         if p == n:
            return True
         y += 1
         p = x**y
   return False
def check_strong_num(n):
   count = {i:0 for i in range(n)}
   while n % 2 == 0:
      n = n // 2
      count[2] += 1
   for i in range(3,int(sqrt(n)) + 1, 2):
      while n % i == 0:
         n = n // i
         count[i] += 1
   if n > 2:
      count[n] += 1
   flag = 0
   for key,value in count.items():
      if value == 1:
         flag = 1
         break
   if flag == 1:
      return False
   return True
def isTrojan(n):
   return check_perfect_pow(n) == False and check_strong_num(n)
n = 72
print(isTrojan(n))

入力

72

出力

True