A195637 - OEIS

%I #28 Oct 11 2023 22:22:42

%S 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 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 8,21,30,59,8,61,32,9,2,65,24,67,10,69,24,71,4,73

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

%C a(n) = n if n prime.

%H Alois P. Heinz, <a href="/A195637/b195637.txt">Table of n, a(n) for n = 1..10000</a>

%e a(18) = 4 because k^18 == 0, 1, 9, 10 (mod 18) => 4 distinct residues.

%e From _R. J. Mathar_, Aug 27 2013: (Start)

%e The triangle of k^n (mod n) starts in row n=1 with columns k>=0 as:

%e   0;

%e   0, 1;

%e   0, 1, 2;

%e   0, 1, 0, 1;

%e   0, 1, 2, 3, 4;

%e   0, 1, 4, 3, 4, 1;

%e   0, 1, 2, 3, 4, 5, 6;

%e   0, 1, 0, 1, 0, 1, 0, 1;

%e   0, 1, 8, 0, 1, 8, 0, 1, 8;

%e   0, 1, 4, 9, 6, 5, 6, 9, 4, 1;

%e   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;

%e   0, 1, 4, 9, 4, 1, 0, 1, 4, 9,  4,  1;

%e   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;

%e Its row sums are 0, 1, 3, 2, 10, 13, 21, 4, 27, 45, 55, 38, 78, 77, 105, 8,.... (End)

%p a:= n-> nops({seq(k&^n mod n, k=0..n-1)}):

%p seq(a(n), n=1..100);

%t Table[Length[Union[PowerMod[Range[0, n - 1], n, n]]], {n, 100}] (* _T. D. Noe_, Sep 21 2011 *)

%o (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 (Python)

%o def A195637(n): return len({pow(x,n,n) for x in range(n)}) # _Chai Wah Wu_, Aug 22 2023

%K nonn,nice

%O 1,2

%A _Michel Lagneau_, Sep 21 2011