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