A307864 a(n) is the number of natural bases b < 2n+1 such that b^n == 1 (mod 2n+1).

0, 1, 2, 3, 2, 5, 6, 1, 8, 9, 4, 11, 4, 1, 14, 15, 4, 1, 18, 1, 20, 21, 4, 23, 6, 1, 26, 1, 4, 29, 30, 1, 16, 33, 4, 35, 36, 1, 4, 39, 2, 41, 4, 1, 44, 9, 4, 1, 48, 1, 50, 51, 16, 53, 54, 1, 56, 1, 4, 1, 10, 1, 2, 63, 4, 65, 36, 1, 68, 69, 4, 1, 16, 1, 74, 75, 8, 1, 78, 1, 4, 81, 8, 83, 12, 1, 86

Offset

0,3

Comments

For n > 0, a(n) = n if and only if 2n+1 is prime.

If a(n) < n, then 2n+1 is composite.

Theorem: a(n) > n if and only if 2n+1 is an absolute Euler pseudoprime.

Conjecture: if 2n+1 is an absolute Euler pseudoprime, then a(n) = phi(2n+1).

Links

Table of n, a(n) for n=0..86.

Mathematica

a[n_] := Length[Select[Range[2n], PowerMod[#, n, 2n+1] == 1 &]]; Array[a, 100] (* Amiram Eldar, May 02 2019 *)

Prog

(PARI) a(n) = sum(b=1, 2*n, Mod(b, 2*n+1)^n == 1); \\ Michel Marcus, May 02 2019

Crossrefs

Cf. A000010, A033181, A306530, A307865.

Sequence in context: A021047 A249492 A113649 * A066119 A003970 A094443

Adjacent sequences: A307861 A307862 A307863 * A307865 A307866 A307867

Keyword

nonn

Author

Thomas Ordowski, May 02 2019

Extensions

More terms from Amiram Eldar, May 02 2019

Status

approved