A331810 - OEIS

%I #17 Feb 23 2020 16:14:15

%S 2,4,2,3,3,16,7,2,7,2,10,10,4,2,10,3,9,9,20,8,8,3,2,35,36,8,3,45,16,2,

%T 39,16,6,5,8,14,58,2,6,3,42,5,84,36,18,58,2,3,16,2,6,87,20,256,2,5,10,

%U 16,59,4,16,9,7,27,10,74,8,3,31,22,2,7,12,86,2,5

%N Smallest integer x such that prime(n) divides 1 + x + x^2 + ... + x^(q-1) where q = A023503(n), or 0 if no such x exists.

%C Conjecture: every integer > 1 is in the sequence.

%C Theorem: Let p and q be prime numbers for which there exists an integer x such that p divides 1 + x + x^2 + ... + x^(q-1). Then p == 1 (mod q) or p = q.

%e a(8) = 7 because prime(8) = 19 divides 1 + 7^1 + 7^2 = 57 = 3*19, where q = 3 = A023503(8).

%e a(9) = 2 because prime(9) = 23 divides 1 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10  = 2047 = 23*89, where q = 11 = A023503(9).

%p with(numtheory):nn:=100:

%p for n from 2 to nn do:

%p p:=ithprime(n):d:=factorset(p-1):n0:=nops(d):q:=d[n0]:ii:=0:

%p    for x from 1 to 10^5 while(ii=0) do:

%p     s:=sum('x^(i-1)', 'i'=1..q):

%p      if irem(s,p)=0 then

%p       ii:=1:printf(`%d, `,x):

%p      else fi:

%p      od:

%p     od:

%t Array[Block[{k = 2}, While[Mod[Total[k^#2 ], #1] != 0, k++]; k ] & @@ {Prime@ #, Range[0, FactorInteger[Prime@ # - 1][[-1, 1]] - 1 ]} &, 76, 2] (* _Michael De Vlieger_, Jan 27 2020 *)

%o (PARI) a(n) = {my(p=prime(n), q=vecmax(factor(p-1)[,1]), x=1); while (sum(k=0, q-1, x^k) % p, x++); x;} \\ _Michel Marcus_, Jan 30 2020

%Y Cf. A023503 (greatest prime divisor of prime(n) - 1).

%K nonn

%O 2,1

%A _Michel Lagneau_, Jan 27 2020