A348259 Number of bases 1

0, 0, 1, 0, 3, 0, 5, 0, 1, 0, 9, 0, 11, 0, 3, 0, 15, 0, 17, 0, 3, 0, 21, 0, 3, 0, 1, 2, 27, 0, 29, 0, 3, 0, 3, 0, 35, 0, 3, 0, 39, 0, 41, 0, 7, 0, 45, 0, 5, 0, 3, 2, 51, 0, 3, 0, 3, 0, 57, 0, 59, 0, 3, 0, 15, 4, 65, 0, 3, 2, 69, 0, 71, 0, 3

Offset: 1

Author

Robert G. Wilson v, Oct 08 2021

Keywords

• base
• nonn

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, ..., .

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A000040, A039772, A063994.

Programs

Mathematica

a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]

PARI

a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ Michel Marcus, Oct 09 2021

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