cp's OEIS Frontend

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

%I A317358 #77 Jan 06 2019 11:23:24
%S A317358 2,3,5,2,2,7,11,2,2,3,3,2,2,17,17,2,2,3,3,2,2,23,29,2,2,5,3,2,2,31,37,
%T A317358 2,2,37,35,2,2,3,41,2,2,43,47,2,2,3,3,2,2,5,5,2,2,3,3,2,2,59,61,2,2,
%U A317358 67,3,2,2,55,71,2,2,35,35,2,2,3,5,2,2,5,5,2,2
%N A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).
%C A317358 a(n) = 2 if and only if n == {0, 1} (mod 4).
%C A317358 a(n) <= A151800(n).
%C A317358 A133906(n) <= a(n) <= A133907(n).
%C A317358 The sequence is unbounded.
%C A317358 Numbers n such that a(n-1) = n are 2, 3, 7, 23, 31, 43, 59, 139, 283, ...
%C A317358 By the Agoh-Giuga conjecture, if a(n-1) = n, then n is a prime.
%C A317358 It seems that if a(n) > n, then a(n) is a prime (the next prime after n).
%C A317358 If a(n) = n, then n is in A121707. These numbers are 35, 143, 187, 215, ...
%C A317358 Conjecture: all composite terms of the sequence are A121707.
%H A317358 Chai Wah Wu, <a href="/A317358/b317358.txt">Table of n, a(n) for n = 1..10000</a> (n = 1..1000 from Seiichi Manyama)
%H A317358 Wikipedia, <a href="https://en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture">Agoh-Giuga conjecture</a>
%t A317358 a[n_] := Block[{k=2}, While[Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 81] (* _Giovanni Resta_, Jul 29 2018 *)
%o A317358 (PARI) a(n) = for(k=2,oo, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ _Michel Marcus_, Jul 26 2018
%o A317358 (Python)
%o A317358 def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
%o A317358     c = (-n) % q
%o A317358     for k in range(1,n+1):
%o A317358         c = (c+pow(k,p,q)) % q
%o A317358     return c
%o A317358 def A317358(n):
%o A317358     k = 2
%o A317358     while g(n,k-1,k):
%o A317358         k += 1
%o A317358     return k # _Chai Wah Wu_, Jul 30 2018
%Y A317358 Cf. A133906, A133907, A151800, A121707, A317058, A317357.
%K A317358 nonn
%O A317358 1,1
%A A317358 _Thomas Ordowski_, Jul 26 2018
%E A317358 More terms from _Michel Marcus_, Jul 26 2018