A371729 The number of pseudoprimes to base n that are smaller than n.
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
Examples
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.
Links
- Amiram Eldar, Table of n, a(n) for n = 2..10001
- Wikipedia, Pseudoprime.
- Index entries for sequences related to pseudoprimes.
Programs
-
Mathematica
a[n_] := Count[Range[4, n-1], _?(CompositeQ[#] && PowerMod[n, # - 1, #] == 1 &)]; Array[a, 100, 2]
-
PARI
a(n) = {my(c = 0); forcomposite(k = 4, n-1, if(Mod(n, k)^(k-1) == 1, c++)); c;}