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

1, 5, 5, 21, 101, 501, 2505, 12505, 62521, 312601, 1563001, 7815005, 39075005, 195375021, 976875101, 4884375501, 24421877505, 122109387505, 610546937521, 3052734687601, 15263673438001, 76318367190005, 381591835950005, 1907959179750021, 9539795898750101, 47698979493750501, 238494897468752505, 1192474487343762505, 5962372436718812521, 29811862183594062601

Offset: 0

Author

Albert Mukovskiy, Aug 24 2023

Keywords

• nonn
• easy

Comments

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.

Links

• Index entries for linear recurrences with constant coefficients, signature (5,0,0,0,1,-5).

Crossrefs

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

Programs

Mathematica

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

Python

def A365104(n): return len({pow(x,5,5**n) for x in range(5**n)}) # Chai Wah Wu, Sep 17 2023

Formula

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

Extensions

Terms a(16) onward from Max Alekseyev, Feb 19 2024