Pillai's arithmetical function に関する予想の反例
今年MathOverflow等でとある予想の反例が示され、話題になったので紹介します。
a(n) = Sum_{k=1..n} gcd(k,n)
と定める。Thomas Ordowski 氏により、
n>1 divides a(n)+1 iff n is prime.という予想がされていました。
実際以下のコードを実行しても何も出力されないので、n<=10000までは正しいです。
a(n) = sum(k=1, n, gcd(k, n));
for(n=2, 10000, if(Mod(a(n)+1, n)==0 && !isprime(n), print1(n,", ")));
しかし、n = 3*37*43*42307*116341 (合成数) のとき
a(n)+1 がn で割り切れることがVarun Vejalla 氏により発見されました。
このことを確認してみます。
a(n) = Sum_{k=1..n} gcd(k,n)のままだと計算量が多いので、
nの約数dの個数に注目して、
a(n) = Sum_{d|n} d * phi(n/d)
を使って、確認します。
N = 3*37*43*42307*116341;
a(n) = sumdiv(n, d, d*eulerphi(n/d));
if(Mod(1+a(N), N)==0, print("a(", N, ") + 1 = ", (1+a(N))/N, " * ", N, "."));
出力結果
a(23492890653051) + 1 = 26 * 23492890653051.
