cp's OEIS Frontend

A195637 Number of distinct residues of k^n (mod n), k=0..n-1.

%I A195637 #28 Oct 11 2023 22:22:42
%S A195637 1,2,3,2,5,4,7,2,3,6,11,4,13,8,15,2,17,4,19,4,9,12,23,4,5,14,3,8,29,
%T A195637 12,31,2,33,18,35,4,37,20,15,4,41,8,43,12,15,24,47,4,7,6,51,8,53,4,15,
%U A195637 8,21,30,59,8,61,32,9,2,65,24,67,10,69,24,71,4,73
%N A195637 Number of distinct residues of k^n (mod n), k=0..n-1.
%C A195637 a(n) = n if n prime.
%H A195637 Alois P. Heinz, <a href="/A195637/b195637.txt">Table of n, a(n) for n = 1..10000</a>
%e A195637 a(18) = 4 because k^18 == 0, 1, 9, 10 (mod 18) => 4 distinct residues.
%e A195637 From _R. J. Mathar_, Aug 27 2013: (Start)
%e A195637 The triangle of k^n (mod n) starts in row n=1 with columns k>=0 as:
%e A195637   0;
%e A195637   0, 1;
%e A195637   0, 1, 2;
%e A195637   0, 1, 0, 1;
%e A195637   0, 1, 2, 3, 4;
%e A195637   0, 1, 4, 3, 4, 1;
%e A195637   0, 1, 2, 3, 4, 5, 6;
%e A195637   0, 1, 0, 1, 0, 1, 0, 1;
%e A195637   0, 1, 8, 0, 1, 8, 0, 1, 8;
%e A195637   0, 1, 4, 9, 6, 5, 6, 9, 4, 1;
%e A195637   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;
%e A195637   0, 1, 4, 9, 4, 1, 0, 1, 4, 9,  4,  1;
%e A195637   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
%e A195637 Its row sums are 0, 1, 3, 2, 10, 13, 21, 4, 27, 45, 55, 38, 78, 77, 105, 8,.... (End)
%p A195637 a:= n-> nops({seq(k&^n mod n, k=0..n-1)}):
%p A195637 seq(a(n), n=1..100);
%t A195637 Table[Length[Union[PowerMod[Range[0, n - 1], n, n]]], {n, 100}] (* _T. D. Noe_, Sep 21 2011 *)
%o A195637 (PARI) a(n)=if(isprime(n), n, #Set(vector(n,i,lift(Mod(i-1,n)^n)))) \\ _Charles R Greathouse IV_, Jul 31 2016
%o A195637 (Python)
%o A195637 def A195637(n): return len({pow(x,n,n) for x in range(n)}) # _Chai Wah Wu_, Aug 22 2023
%K A195637 nonn,nice
%O A195637 1,2
%A A195637 _Michel Lagneau_, Sep 21 2011