login
A371729
The number of pseudoprimes to base n that are smaller than n.
2
0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 3, 0, 1, 1, 4, 0, 4, 0, 3, 1, 1, 0, 5, 3, 1, 2, 5, 0, 4, 1, 4, 3, 2, 1, 7, 0, 1, 1, 8, 0, 6, 2, 3, 3, 1, 0, 9, 2, 3, 1, 8, 0, 6, 3, 6, 1, 2, 0, 9, 3, 1, 7, 7, 1, 6, 2, 4, 1, 9, 0, 11, 2, 1, 7, 6, 1, 7, 3, 10, 5, 3, 0, 8, 4, 1, 1
OFFSET
2,8
FORMULA
a(n) = 0 if and only if A090086(n) > n, or equivalently, n-1 is in A316504.
EXAMPLE
a(2) = 0 since the smallest pseudoprime to base 2 (A001567) is 341 which is larger than 2.
a(5) = 1 since there is one pseudoprime to base 5 (A005936) that is smaller than 5: 4.
a(9) = 2 since there are 2 pseudoprimes to base 9 (A020138) that are smaller than 9: 4 and 8.
MATHEMATICA
a[n_] := Count[Range[4, n-1], _?(CompositeQ[#] && PowerMod[n, # - 1, #] == 1 &)]; Array[a, 100, 2]
PROG
(PARI) a(n) = {my(c = 0); forcomposite(k = 4, n-1, if(Mod(n, k)^(k-1) == 1, c++)); c; }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Amiram Eldar, Apr 05 2024
STATUS
approved