cp's OEIS Frontend

A052273 Number of distinct 4th powers mod n.

%I A052273 #59 Apr 09 2025 16:10:25
%S A052273 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,
%T A052273 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,
%U A052273 16,30,8,16,32,16,6,8,24,34,10,24,16,36,8,19,20,12,20
%N A052273 Number of distinct 4th powers mod n.
%C A052273 This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005
%H A052273 T. D. Noe, <a href="/A052273/b052273.txt">Table of n, a(n) for n = 1..1000</a>
%H A052273 S. Li, <a href="http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-aav86i2p113bwm">On the number of elements with maximal order in the multiplicative group modulo n</a>, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1
%H A052273 Samer Seraj, <a href="https://doi.org/10.7546/nntdm.2022.28.4.730-743">Counting general power residues</a>, Notes on Number Theory and Discrete Mathematics, 28:4 (2022), 730-743. Substituting k=4 into Theorem 1.1 gives a closed formula.
%H A052273 Samer Seraj, <a href="http://math.colgate.edu/~integers/x62/x62.pdf">Resolution of Mathar's Conjectures on Counting Power Residues</a>, #A62 INTEGERS 23 (2023).
%F A052273 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
%F A052273 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
%F A052273 From _Samer Seraj_, Nov 09 2022: (Start)
%F A052273 The above conjectures are correct, and a unified form is:
%F A052273 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)
%p A052273 A052273 := proc(n,k) local i; nops({seq(i^k mod n,i=0..n-1)}); end; # number of k-th powers mod n
%t A052273 a[n_] := Table[PowerMod[i, 4, n], {i, 0, n-1}] // Union // Length;
%t A052273 Array[a, 100] (* _Jean-François Alcover_, Mar 24 2020 *)
%o A052273 (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
%o A052273 (PARI) \\ general formula for k-th powers, see Seraj link
%o A052273 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
%o A052273 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
%o A052273 (Python)
%o A052273 from math import prod
%o A052273 from sympy import factorint
%o A052273 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
%Y A052273 Cf. A000224 (squares), A046530 (cubic residues), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).
%K A052273 nonn,mult
%O A052273 1,2
%A A052273 _N. J. A. Sloane_, Feb 05 2000