cp's OEIS Frontend

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

%I A375347 #11 Aug 17 2024 13:58:46
%S A375347 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,
%T A375347 17,18,17,16,17,22,16,17,16,19,18,21,20,22,20,22,22,32,36,25,25,28,30,
%U A375347 23,34,28,28,25,24,36,38,33,27,31,29,32,31,39,35,36,44,35,42,31,39,36,38
%N A375347 a(n) is the number of nonnegative numbers k < n such that the congruence x^k == k (mod n) is solvable.
%e A375347 a(1) = 1 because x^0 == 0 (mod 1) is solvable where x: 0, 1, 2, 3, 4,.. A001477;
%e A375347 a(2) = 1 because x^0 == 0 (mod 2) is unsolvable,
%e A375347                  x^1 == 1 (mod 2) is solvable where x: 1, 3, 5, 7, 9,.. A005408;
%e A375347 a(3) = 1 because x^0 == 0 (mod 3) is unsolvable,
%e A375347                  x^1 == 1 (mod 3) is solvable where x: 1, 4, 7, 10, 13,.. A016777,
%e A375347                  x^2 == 2 (mod 3) is unsolvable;
%e A375347 a(4) = 2 because x^0 == 0 (mod 4) is unsolvable,
%e A375347                  x^1 == 1 (mod 4) is solvable where x: 1, 5, 9, 13, 16,.. A016813,
%e A375347                  x^2 == 2 (mod 4) is unsolvable,
%e A375347                  x^3 == 3 (mod 4) is solvable where x: 3, 7, 11, 15, 19,.. A004767.
%o A375347 (PARI) is(k, n) = for (i=0, n-1, if (Mod(i, n)^k == k, return(1)));
%o A375347 a(n) = sum(k=0, n-1, is(k, n)); \\ _Michel Marcus_, Aug 13 2024
%Y A375347 Cf. A371811, A372771.
%Y A375347 Cf. A001477, A004767, A005408, A016777, A016813.
%K A375347 nonn
%O A375347 1,4
%A A375347 _Juri-Stepan Gerasimov_, Aug 12 2024
%E A375347 More terms from _Michel Marcus_, Aug 13 2024