OFFSET
1,2
COMMENTS
This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005
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).
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)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,mult
AUTHOR
N. J. A. Sloane, Feb 05 2000
STATUS
approved