A354689 Smallest Euler pseudoprime to base n.

9, 341, 121, 341, 217, 185, 25, 9, 91, 9, 133, 65, 21, 15, 341, 15, 9, 25, 9, 21, 65, 21, 33, 25, 217, 9, 65, 9, 15, 49, 15, 25, 545, 21, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 133, 9, 65, 49, 25, 21, 25, 51, 9, 55, 9, 33, 25, 57, 15, 341, 15, 9, 341, 9, 33, 65

Offset: 1

Author

Jinyuan Wang, Jun 03 2022

Keywords

• nonn

Comments

An Euler pseudoprime to the base b is a composite number k which satisfies b^((k-1)/2) == +-1 (mod k).

Links

• Eric Weisstein's World of Mathematics, Euler Pseudoprime.

Crossrefs

Cf. A006970, A090086, A298756, A326614.

Programs

PARI

a(n) = my(m); forcomposite(k=3, oo, if(k%2 && ((m=Mod(n, k)^(k\2))==1 || m==k-1), return(k)));

Python

from sympy import isprime
from itertools import count
def a(n): return next(k for k in count(3, 2) if not isprime(k) and ((r:=pow(n, (k-1)//2, k)) == 1 or r == k-1))
print([a(n) for n in range(1, 67)]) # Michael S. Branicky, Jun 03 2022

Formula

a(n) = 9 for n == 1 or 8 (mod 9).