|
|
A052273
|
|
Number of distinct 4th powers mod n.
|
|
15
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005
|
|
LINKS
|
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.
|
|
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
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;
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|