cp's OEIS Frontend

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

%I A317058 #51 Aug 15 2018 22:35:28
%S A317058 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 A317058 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 A317058 85,4,4,9,9,4,4,551,1711,4,4,713,21,4,4,55,77,4,4,35,35,4
%N A317058 a(n) is the smallest composite k such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).
%C A317058 According to the Agoh-Giuga conjecture, a(n) <> n+1.
%C A317058 a(n) = 4 if and only if n == {0, 1} (mod 4).
%H A317058 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 A317058 Wikipedia, <a href="https://en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture">Agoh-Giuga conjecture</a>
%t A317058 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 A317058 (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 A317058 (Python)
%o A317058 from sympy import isprime
%o A317058 def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
%o A317058     c = (-n) % q
%o A317058     for k in range(1,n+1):
%o A317058         c = (c+pow(k,p,q)) % q
%o A317058     return c
%o A317058 def A317058(n):
%o A317058     k = 2
%o A317058     while isprime(k) or g(n,k-1,k):
%o A317058         k += 1
%o A317058     return k # _Chai Wah Wu_, Jul 30 2018
%Y A317058 Cf. A000790, A133906, A133907, A317357, A317358.
%K A317058 nonn
%O A317058 1,1
%A A317058 _Thomas Ordowski_, Jul 26 2018
%E A317058 More terms from _Giovanni Resta_, Jul 26 2018