cp's OEIS Frontend

A195743 Number of distinct residues of prime(k)^n (mod n), prime(k) <= n.

%I A195743 #23 Nov 20 2020 16:19:08
%S A195743 0,1,2,2,3,3,4,2,3,3,5,3,6,5,6,2,7,3,8,3,5,6,9,3,5,7,3,5,10,5,11,2,11,
%T A195743 8,11,3,12,11,8,3,13,4,14,7,10,11,15,3,7,4,15,5,16,3,9,5,11,13,17,4,
%U A195743 18,16,6,2,18,8,19,6,19,9,20,3,21,17,10,11,21,5
%N A195743 Number of distinct residues of prime(k)^n (mod n), prime(k) <= n.
%C A195743 If n = prime(k), then a(n) = k.
%H A195743 Alois P. Heinz, <a href="/A195743/b195743.txt">Table of n, a(n) for n = 1..10000</a>
%H A195743 I. M. Vinogradov, <a href="https://doi.org/10.1090/S0002-9947-1927-1501384-3">On a general theorem concerning the distribution of the residues and non-residues of powers</a>, Trans. American Math. Soc., 29 (1927), 209-217.
%e A195743 a(11) = a(prime(5)) = 5, and we check:  2^11, 3^11, 5^11, 7^11, 11^11 == 2, 3, 5, 7, 0 (mod 11) respectively => 5 distinct residues;
%e A195743 a(18) = 3 because 2^18, 3^18, 5^18, 7^18, 11^18, 13^18, 17^18 == 10, 9, 1, 1, 1, 1, 1 (mod 18) respectively => 3 distinct residues.
%p A195743 a:= proc(n) local p, s; s:= {}; p:=2; while p<=n do s:= s union {p&^n mod n}; p:= nextprime(p) od; nops(s) end: seq(a(n), n=1..100);
%t A195743 a[n_] := PowerMod[#, n, n]& /@ Prime[Range[PrimePi[n]]] // Union // Length;
%t A195743 Array[a, 100] (* _Jean-François Alcover_, Nov 20 2020 *)
%o A195743 (PARI) a(n) = #Set(vector(primepi(n), k, Mod(prime(k), n)^n)); \\ _Michel Marcus_, Nov 20 2020
%Y A195743 Cf. A195637.
%K A195743 nonn
%O A195743 1,3
%A A195743 _Michel Lagneau_, Sep 23 2011