150706

Ruby

Carmichael number

オンライン整数列大辞典の
A002997（http://oeis.org/A002997/list）
と比較し、答え合わせしてみる。

require 'prime'

def pow(a, m, mod)
  return 1 % mod if m == 0
  k = pow(a, m >> 1, mod)
  k *= k
  return k % mod if m & 1 == 0
  return k * a % mod
end

def is_carmichael?(n)
  return false if n.prime?
  i = 2
  while pow(i, n, n) == i && i < n
    i += 1
  end
  return true if i == n # nはカーマイケル数
  return false
end

def A002997(n)
  (2..n).select{|i| is_carmichael?(i)}
end
ary = A002997(512461)

# OEIS A002997のデータ
ary0 =
[561,1105,1729,2465,2821,6601,8911,10585,15841,
 29341,41041,46657,52633,62745,63973,75361,101101,
 115921,126217,162401,172081,188461,252601,278545,
 294409,314821,334153,340561,399001,410041,449065,
 488881,512461]
# 一致の確認
p ary == ary0