A303978 - OEIS

A303978

a(n) is the smallest prime p that does not divide n-1 such that (n^p-1)/(n-1) is composite, for n > 1.

11, 5, 5, 5, 11, 7, 2, 3, 5, 3, 7, 11, 2, 5, 7, 13, 3, 5, 2, 7, 11, 3, 2, 5, 2, 5, 7, 3, 3, 11, 2, 5, 2, 3, 3, 5, 2, 3, 11, 7, 3, 11, 2, 3, 11, 3, 2, 5, 2, 3, 5, 3, 2, 5, 2, 5, 5, 5, 3, 11, 2, 3, 2, 3, 11, 5, 2, 5, 5, 11, 3, 11, 2, 5, 2, 7, 5, 7, 2, 3, 5, 3, 2, 11, 2, 3, 5, 5, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,1

COMMENTS

Smallest prime p such that (n^p-1)/(n-1) is a pseudoprime to base n > 1.

If Schinzel's hypothesis H is true, then the sequence is unbounded.

b(n) = (n^a(n)-1)/(n-1) is a strong pseudoprime to base n > 1, but not necessarily the smallest, cf. A298756.

b(n): 2047, 121, 341, 781, 72559411, 137257, 9, 91, 11111, 133, ...

Indices n of records a(n) = 11, 13, 17, 19, 23, 29 are n = 2, 17, 4291, 32319, 128701, 2668576. - Robert Israel, May 04 2018

LINKS

Table of n, a(n) for n=2..90.

EXAMPLE

The repunit (10^5-1)/9 = 11111 = 41*271 is composite, so a(10) = 5, because (10^2-1)/9 = 11 is prime and 3 divides 9.

MAPLE

f:= proc(n) local p;

p:= 2;

while n-1 mod p = 0 or isprime((n^p-1)/(n-1)) do p:= nextprime(p) od:

end proc:

map(p, [$2..100]); # Robert Israel, May 04 2018

MATHEMATICA

Array[Block[{p = 2}, While[Nand[CoprimeQ[# - 1, p], CompositeQ[(#^p - 1)/(# - 1)]], p = NextPrime@ p]; p] &, 89, 2] (* Michael De Vlieger, May 06 2018 *)

PROG

(PARI) a(n) = {forprime(p=2, , if (((n-1) % p) && !isprime((n^p-1)/(n-1)), return (p)); ); } \\ Michel Marcus, May 04 2018

CROSSREFS

Cf. A298756.

Sequence in context: A131029 A033331 A229192 * A085716 A127820 A168206

Adjacent sequences: A303975 A303976 A303977 * A303979 A303980 A303981

KEYWORD

nonn

AUTHOR

Thomas Ordowski, May 03 2018

EXTENSIONS

More terms from Michel Marcus, May 04 2018

STATUS

approved