251220

RARI


Pillai's arithmetical function に関する予想の反例

この記事は
日曜数学 Advent Calendar 2025
の12/20 分として書いております。

今年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.