login
Number of distinct quintic residues x^5 (mod 5^n), x=0..5^n-1.
5

%I #57 Feb 20 2024 10:30:45

%S 1,5,5,21,101,501,2505,12505,62521,312601,1563001,7815005,39075005,

%T 195375021,976875101,4884375501,24421877505,122109387505,610546937521,

%U 3052734687601,15263673438001,76318367190005,381591835950005,1907959179750021,9539795898750101,47698979493750501,238494897468752505,1192474487343762505,5962372436718812521,29811862183594062601

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

%C It appears that for a prime p>2 the number of distinct residues x^p (mod p^n) is a(n) = (p-1)*p^(n-2) + a(n-p), with a(n<1)=1, a(1)=p.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (5,0,0,0,1,-5).

%F For n >= 6, a(n) = 4*5^(n-2) + a(n-5) = 5*a(n-1) + a(n-5) - 5*a(n-6). O.g.f: (-5*x^5 - 4*x^4 - 4*x^3 - 20*x^2 + 1)/(5*x^6 - x^5 - 5*x + 1). - _Max Alekseyev_, Feb 19 2024

%t a[n_]:=CountDistinct[Table[PowerMod[x-1, 5, 5^(n-1)], {x, 1, 5^(n-1)}]]; Array[a, 13]

%o (Python)

%o def A365104(n): return len({pow(x,5,5**n) for x in range(5**n)}) # _Chai Wah Wu_, Sep 17 2023

%Y Cf. A023105, A046631, A195637, A365099, A365100, A365101, A365102.

%K nonn,easy

%O 0,2

%A _Albert Mukovskiy_, Aug 24 2023

%E Terms a(16) onward from _Max Alekseyev_, Feb 19 2024