A052273 Number of distinct 4th powers mod n.
1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 6, 4, 4, 8, 4, 2, 5, 8, 10, 4, 8, 12, 12, 4, 6, 8, 10, 8, 8, 8, 16, 4, 12, 10, 8, 8, 10, 20, 8, 4, 11, 16, 22, 12, 8, 24, 24, 4, 22, 12, 10, 8, 14, 20, 12, 8, 20, 16, 30, 8, 16, 32, 16, 6, 8, 24, 34, 10, 24, 16, 36, 8, 19, 20, 12, 20
Offset: 1
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- S. Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1
- Samer Seraj, Counting general power residues, Notes on Number Theory and Discrete Mathematics, 28:4 (2022), 730-743. Substituting k=4 into Theorem 1.1 gives a closed formula.
- Samer Seraj, Resolution of Mathar's Conjectures on Counting Power Residues, #A62 INTEGERS 23 (2023).
Crossrefs
Programs
-
Maple
A052273 := proc(n,k) local i; nops({seq(i^k mod n,i=0..n-1)}); end; # number of k-th powers mod n
-
Mathematica
a[n_] := Table[PowerMod[i, 4, n], {i, 0, n-1}] // Union // Length; Array[a, 100] (* Jean-François Alcover, Mar 24 2020 *) -
PARI
a(n)=my(f=factor(n)); prod(i=1,#f[,1],my(k=f[i,1]^f[i,2]); #vecsort(vector(k,i,i^4%k),,8)) \\ Charles R Greathouse IV, May 26 2013
-
PARI
\\ general formula for k-th powers, see Seraj link h(p,e,k=4)=my(a=(p-1)/gcd(k,p-1),b=if(k%2+p%2,0,valuation(k,p)+1)+p%2*valuation(k,p),g=(e-1)%k+1,G=p^g,B=p^(b+1),K=p^k,E=p^e); a*(K/B*(E-G)/(K-1)+ceil(G/B))+1 a(n,f=factor(n),k=4)=prod(i=1,#f~, h(f[i,1],f[i,2],k)) \\ Charles R Greathouse IV, Nov 09 2022
-
Python
from math import prod from sympy import factorint def A052273(n): return prod(1+(p**e//15+bool(e&3) if p==2 else (p-1)*p**(e+3)//((4 if p&3==1 else 2)*(p**4-1))) for p, e in factorint(n).items()) # Chai Wah Wu, Apr 09 2025
Formula
Conjecture: a(2^e) = 1 + floor(2^e/(2^4-1)) if e == 0 (mod 4). a(2^e) = 2 + floor(2^e/(2^4-1)) if e == {1,2,3} mod 4. - R. J. Mathar, Oct 22 2017
Conjecture: a(p^e) = 1 + floor((p-1)*p^(e+3)/(gcd(p-1,4)*(p^4-1))) for odd primes p. - R. J. Mathar, Oct 22 2017
From Samer Seraj, Nov 09 2022: (Start)
The above conjectures are correct, and a unified form is:
a(p^m) = alpha*((p^3 / p^beta)*((p^m - p^gamma)/(p^4 -1)) + ceiling((p^gamma)/(p^(beta+1)))) + 1, where p is any prime, m is any positive integer, alpha = (p-1)/gcd(4,p-1), beta = 3 if p = 2 or beta = 0 if p is odd, and gamma = 4 if 4|m or gamma = (m mod 4) otherwise. (End)
Comments