cp's OEIS Frontend

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

%I A113516 #15 Nov 20 2021 11:33:24
%S A113516 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 A113516 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 A113516 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 A113516 Least k such that n^k-n+1 is prime.
%C A113516 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 A113516 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 A113516 Table[k=1; While[ !PrimeQ[n^k-n+1], k++ ]; k, {n, 2, 92}]
%o A113516 (PARI) a(n) = my(k=1); while (!isprime(n^k-n+1), k++); k; \\ _Michel Marcus_, Nov 20 2021
%o A113516 (Python)
%o A113516 from sympy import isprime
%o A113516 def a(n):
%o A113516     k = 2
%o A113516     while not isprime(n**k - n + 1): k += 1
%o A113516     return k
%o A113516 print([a(n) for n in range(2, 71)]) # _Michael S. Branicky_, Nov 20 2021
%Y A113516 A343589 gives the primes.
%Y A113516 Cf. A113517 (smallest k such that k^n-k+1 is prime).
%K A113516 nonn
%O A113516 2,1
%A A113516 _T. D. Noe_, Jan 12 2006