login
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, 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,4
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Michel Marcus, Aug 13 2024
STATUS
approved