A317058 - OEIS

%I #51 Aug 15 2018 22:35:28

%S 4,341,473,4,4,133,497,4,4,15,9,4,4,143,35,4,4,51,57,4,4,77,253,4,4,

%T 65,9,4,4,115,155,4,4,187,35,4,4,9,247,4,4,287,2051,4,4,15,33,4,4,35,

%U 85,4,4,9,9,4,4,551,1711,4,4,713,21,4,4,55,77,4,4,35,35,4

%N a(n) is the smallest composite k such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

%C According to the Agoh-Giuga conjecture, a(n) <> n+1.

%C a(n) = 4 if and only if n == {0, 1} (mod 4).

%H Chai Wah Wu, <a href="/A317058/b317058.txt">Table of n, a(n) for n = 1..9661</a> (n = 1..500 from Seiichi Manyama)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture">Agoh-Giuga conjecture</a>

%t a[n_] := Block[{k = 4}, While[PrimeQ[k] || Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 72] (* _Giovanni Resta_, Jul 26 2018 *)

%o (PARI) a(n) = forcomposite(k=1,, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ _Michel Marcus_, Jul 26 2018

%o (Python)

%o from sympy import isprime

%o def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q

%o     c = (-n) % q

%o     for k in range(1,n+1):

%o         c = (c+pow(k,p,q)) % q

%o     return c

%o def A317058(n):

%o     k = 2

%o     while isprime(k) or g(n,k-1,k):

%o         k += 1

%o     return k # _Chai Wah Wu_, Jul 30 2018

%Y Cf. A000790, A133906, A133907, A317357, A317358.

%K nonn

%O 1,1

%A _Thomas Ordowski_, Jul 26 2018

%E More terms from _Giovanni Resta_, Jul 26 2018