A375347 a(n) is the number of nonnegative numbers k < n such that the congruence x^k == k (mod n) is solvable.

1, 1, 1, 2, 2, 4, 4, 4, 4, 6, 5, 7, 5, 8, 9, 8, 10, 10, 8, 11, 10, 13, 17, 13, 13, 14, 13, 15, 17, 18, 17, 16, 17, 22, 16, 17, 16, 19, 18, 21, 20, 22, 20, 22, 22, 32, 36, 25, 25, 28, 30, 23, 34, 28, 28, 25, 24, 36, 38, 33, 27, 31, 29, 32, 31, 39, 35, 36, 44, 35, 42, 31, 39, 36, 38

Offset: 1

Author

Juri-Stepan Gerasimov, Aug 12 2024

Keywords

• nonn

Examples

			a(1) = 1 because x^0 == 0 (mod 1) is solvable where x: 0, 1, 2, 3, 4,.. A001477;
a(2) = 1 because x^0 == 0 (mod 2) is unsolvable,
                 x^1 == 1 (mod 2) is solvable where x: 1, 3, 5, 7, 9,.. A005408;
a(3) = 1 because x^0 == 0 (mod 3) is unsolvable,
                 x^1 == 1 (mod 3) is solvable where x: 1, 4, 7, 10, 13,.. A016777,
                 x^2 == 2 (mod 3) is unsolvable;
a(4) = 2 because x^0 == 0 (mod 4) is unsolvable,
                 x^1 == 1 (mod 4) is solvable where x: 1, 5, 9, 13, 16,.. A016813,
                 x^2 == 2 (mod 4) is unsolvable,
                 x^3 == 3 (mod 4) is solvable where x: 3, 7, 11, 15, 19,.. A004767.
		

Crossrefs

Cf. A371811, A372771.

Cf. A001477, A004767, A005408, A016777, A016813.

Programs

PARI

is(k, n) = for (i=0, n-1, if (Mod(i, n)^k == k, return(1)));
a(n) = sum(k=0, n-1, is(k, n)); \\ Michel Marcus, Aug 13 2024

Extensions

More terms from Michel Marcus, Aug 13 2024