cp's OEIS Frontend

A371883 a(n) is the number of divisors d of n such that d^n mod n = d.

%I A371883 #57 May 13 2024 11:20:13
%S A371883 0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,1,1,2,1,2,1,4,1,1,2,2,
%T A371883 1,2,1,2,2,1,1,3,1,1,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,1,1,2,1,1,3,4,1,2,
%U A371883 2,2,1,2,1,2,2,1,1,3,1,2,1,2,1,3,2,2,2,1,1,3,2,1,2,2,2,1,1,2,1,2
%N A371883 a(n) is the number of divisors d of n such that d^n mod n = d.
%C A371883 1 <= a(n) < A000005(n) for n >= 2.
%H A371883 Antti Karttunen, <a href="/A371883/b371883.txt">Table of n, a(n) for n = 1..16384</a>
%e A371883 a(1) = 0: 1 divides 1, but 1^1 mod 1 = 0 (not 1).
%e A371883 a(2) = 1: 1 divides 2, and 1^2 mod 2 = 1;
%e A371883           2 divides 2, but 2^2 mod 2 = 0 (not 2).
%e A371883 a(6) = 2: 1 divides 6, and 1^6 mod 6 = 1;
%e A371883           2 divides 6, but 2^6 mod 6 = 4 (not 2);
%e A371883           3 divides 6, and 3^6 mod 6 = 3;
%e A371883           6 divides 6, but 6^6 mod 6 = 0 (not 6).
%t A371883 a[n_] := DivisorSum[n, 1 &, PowerMod[#, n, n] == # &]; Array[a, 100] (* _Amiram Eldar_, Apr 11 2024 *)
%o A371883 (Magma) [#[d: d in Divisors(n) | d^n mod n eq d]: n in [1..100]];
%o A371883 (Python)
%o A371883 from sympy import divisors
%o A371883 def a(n): return sum(1 for d in divisors(n)[:-1] if pow(d, n, n) == d)
%o A371883 print([a(n) for n in range(1, 101)]) # _Michael S. Branicky_, Apr 10 2024
%o A371883 (PARI) a(n) = sumdiv(n, d, d^n % n == d); \\ _Michel Marcus_, Apr 20 2024
%Y A371883 Cf. A000005, A182816, A279024, A371513, A371884.
%K A371883 nonn
%O A371883 1,6
%A A371883 _Juri-Stepan Gerasimov_, Apr 10 2024