OFFSET
1,5
COMMENTS
This is a count of Fermat Pseudoprimes.
Numbers not in the sequence: 13, 25, 33, 37, 43, 49, 53, 61, 67, 73, 75, 83, 85, 89, 91, 93, 97, ..., .
First occurrence of k=0..: 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, -1, 286, 17, 1854, ..., .
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..20000
FORMULA
a(n) = A063994(n)-1.
a(2n) must be even. Those that exceed 0 are A039772.
a(p) = p-2 iff p is a prime (A000040).
a(2n-1) < 2n-3 iff 2n-1 is composite and a(2n-1) is odd.
a(n) = (Product_{primes p|n} gcd(p-1, n-1)) - 1. - Jianing Song, Nov 20 2021
EXAMPLE
a(3) = 1 since 2^3 = 8 == 2 (mod 3);
a(5) = 2 since {2, 3, 4}^5 = {32, 243, 1024} == {2, 3, 4} (mod 5);
a(9) = 1 since 8^9 = 134217728 == 8;
a(15) = 3 since {4, 11, 14}^15 = {1073741824, 4177248169415651, 155568095557812224} == {4, 11, 14} (mod 15); etc.
MATHEMATICA
a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]
PROG
(PARI) a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ Michel Marcus, Oct 09 2021
CROSSREFS
KEYWORD
base,nonn
AUTHOR
Robert G. Wilson v, Oct 08 2021
STATUS
approved