A113516 - OEIS

%I #15 Nov 20 2021 11:33:24

%S 2,2,2,5,2,2,13,2,3,3,5,2,3,2,2,11,2,3,17,2,2,17,4,2,3,9,2,33,7,3,7,4,

%T 2,3,5,67,5,2,9,3,2,4,25,3,4,5,5,24,3,2,3,21,3,2,9,3,2,11,2,5,3,2,4,

%U 19,31,2,29,4,2,3019,2,21,51,3,2,3,2,2,9,2,169,965,3,3,29,3,2848,9,2,2,3

%N Least k such that n^k-n+1 is prime.

%C k can never be 8,14,20,... (k=2 mod 6) because, for those k, n^k-n+1 has the factor n^2-n+1, which is >1 for n>1. Using a result of Selmer, it can be shown that the polynomial x^k-x+1 is irreducible for all other k. The term a(93) is greater than 60000. Does a(n) exist for all n>1?

%H Ernst S. Selmer, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002344718">On the irreducibility of certain trinomials</a>, Mathematica Scandinavica (1956), Volume: 4, page 287-302.

%t Table[k=1; While[ !PrimeQ[n^k-n+1], k++ ]; k, {n, 2, 92}]

%o (PARI) a(n) = my(k=1); while (!isprime(n^k-n+1), k++); k; \\ _Michel Marcus_, Nov 20 2021

%o (Python)

%o from sympy import isprime

%o def a(n):

%o     k = 2

%o     while not isprime(n**k - n + 1): k += 1

%o     return k

%o print([a(n) for n in range(2, 71)]) # _Michael S. Branicky_, Nov 20 2021

%Y A343589 gives the primes.

%Y Cf. A113517 (smallest k such that k^n-k+1 is prime).

%K nonn

%O 2,1

%A _T. D. Noe_, Jan 12 2006