A000224 -id:A000224 - cp's OEIS frontend

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

N. J. A. Sloane, Feb 05 2000

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

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).

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).

A052273 := proc(n,k) local i; nops({seq(i^k mod n,i=0..n-1)}); end; # number of k-th powers mod n

a[n_] := Table[PowerMod[i, 4, n], {i, 0, n-1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 24 2020 *)

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

\\ 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

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

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)

A052274 Number of distinct 5th powers mod n.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 5, 7, 10, 3, 9, 13, 14, 15, 9, 17, 14, 19, 15, 21, 6, 23, 15, 5, 26, 19, 21, 29, 30, 7, 17, 9, 34, 35, 21, 37, 38, 39, 25, 9, 42, 43, 9, 35, 46, 47, 27, 43, 10, 51, 39, 53, 38, 15, 35, 57, 58, 59, 45, 13, 14, 49, 34, 65, 18, 67, 51, 69, 70

Offset: 1

N. J. A. Sloane, Feb 05 2000

This sequence is multiplicative. - Leon P Smith, Apr 16 2005

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

Cf. A000224 (squares), A046530 (cubic residues), A052273 (4th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

A052274 := proc(m)
    {seq( modp(b^5,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A052274(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

With[{nn=100},Table[Length[Union[PowerMod[Range[nn],5,n]]],{n,nn}]] (* Harvey P. Dale, Mar 19 2016 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^5%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

Conjecture: a(5^e) = 1+floor[(5-1)*5^(e+3)/(5^5-1)] if e == {0,2,3,4} (mod 5). a(5^e) = 5+floor[(5-1)*5^(e+3)/(5^5-1)] if e==1 (mod 5). - R. J. Mathar, Oct 22 2017

Conjecture: a(p^e) = 1+floor[(p-1)*p^(e+4)/{gcd(p-1,5)*(p^5-1)}] for primes p<>5 - R. J. Mathar, Oct 22 2017

A052275 Number of distinct 6th powers mod n.

Original entry on oeis.org

1, 2, 2, 2, 3, 4, 2, 2, 2, 6, 6, 4, 3, 4, 6, 3, 9, 4, 4, 6, 4, 12, 12, 4, 11, 6, 4, 4, 15, 12, 6, 5, 12, 18, 6, 4, 7, 8, 6, 6, 21, 8, 8, 12, 6, 24, 24, 6, 8, 22, 18, 6, 27, 8, 18, 4, 8, 30, 30, 12, 11, 12, 4, 9, 9, 24, 12, 18, 24, 12, 36, 4, 13, 14, 22, 8, 12, 12

Offset: 1

N. J. A. Sloane, Feb 05 2000

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

Same as the number of distinct elements that are both squares and cubes mod n. - Steven Finch, Mar 01 2006

T. D. Noe, Table of n, a(n) for n = 1..1000
S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n (arXiv:math.NT/0604465).
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

Cf. A000224 (squares), A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

A052275 := proc(m)
    {seq( modp(b^6,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A052275(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

Length[Union[#]]&/@Table[PowerMod[k,6,n],{n,100},{k,n}] (* Zak Seidov, Feb 17 2013 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^6%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

Conjecture: a(2^n) = 1,2,2,2,3,5,9,18,... with g.f. ( 1-2*x^2-2*x^3-x^4-x^5-2*x^6 ) / ( (x-1)*(2*x-1)*(1+x)*(1+x+x^2)*(x^2-x+1) ). - R. J. Mathar, Sep 28 2017

Conjecture: a(3^n) = 1,2,2,4,10,28,82,.... with g.f. ( 1-x-4*x^2-2*x^3-2*x^4-2*x^5-3*x^6 ) / ( (x-1)*(3*x-1)*(1+x)*(x^2-x+1)*(1+x+x^2) ). - R. J. Mathar, Sep 28 2017

A085310 Number of distinct 7th powers modulo n.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 5, 7, 10, 11, 9, 13, 14, 15, 9, 17, 14, 19, 15, 21, 22, 23, 15, 21, 26, 19, 21, 5, 30, 31, 17, 33, 34, 35, 21, 37, 38, 39, 25, 41, 42, 7, 33, 35, 46, 47, 27, 7, 42, 51, 39, 53, 38, 55, 35, 57, 10, 59, 45, 61, 62, 49, 33, 65, 66, 67, 51, 69, 70, 11, 35, 73, 74

Offset: 1

Labos Elemer, Jun 27 2003

Compare with enigmatic similarity of analogous odd-th power counts to A055653.

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

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

Cf. A000224[k=2], A046530[k=3], A052273[k=4], A052274[k=5], A052275[k=6], A085311[k=8], A085312[k=9], A085313[k=10], A085314[k=11], A228849[k=12], A055653.

A085310 := proc(m)
    {seq( modp(b^7,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A085310(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

a[n_] := Table[PowerMod[i, 7, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 24 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^7%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A085311 Number of distinct 8th powers modulo n.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 6, 4, 4, 8, 4, 2, 3, 8, 10, 4, 8, 12, 12, 4, 6, 8, 10, 8, 8, 8, 16, 2, 12, 6, 8, 8, 10, 20, 8, 4, 6, 16, 22, 12, 8, 24, 24, 4, 22, 12, 6, 8, 14, 20, 12, 8, 20, 16, 30, 8, 16, 32, 16, 3, 8, 24, 34, 6, 24, 16, 36, 8, 10, 20, 12, 20, 24, 16, 40, 4, 28, 12, 42, 16, 6

Offset: 1

Labos Elemer, Jun 27 2003

This sequence is multiplicative. - Leon P Smith, Apr 16 2005

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
R. J. Mathar, Size of the set of residues of integer powers of fixed exponent, (2017).

Cf. A000224[k=2], A046530[k=3], A052273[k=4], A052274[k=5], A052275[k=6], A085310[k=7], A085312[k=9], A085313[k=10], A085314[k=11], A228849[k=12], A055653.

A085311 := proc(m)
    {seq( modp(b^8,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A085311(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

a[n_] := Table[PowerMod[i, 8, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 24 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^8%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A085312 Number of distinct 9th powers modulo n.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 3, 5, 3, 10, 11, 9, 5, 6, 15, 9, 17, 6, 3, 15, 9, 22, 23, 15, 21, 10, 3, 9, 29, 30, 11, 17, 33, 34, 15, 9, 5, 6, 15, 25, 41, 18, 15, 33, 15, 46, 47, 27, 15, 42, 51, 15, 53, 6, 55, 15, 9, 58, 59, 45, 21, 22, 9, 33, 25, 66, 23, 51, 69, 30, 71, 15, 9, 10, 63, 9, 33, 30, 27

Offset: 1

Labos Elemer, Jun 27 2003

Compare with enigmatic similarity of analogous odd-th power counts to A055653.

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

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

Cf. A000224[k=2], A046530[k=3], A052273[k=4], A052274[k=5], A052275[k=6], A085310[k=7], A085311[k=8], A085313[k=10], A085314[k=11], A228849[k=12], A055653.

A085312 := proc(m)
    {seq( modp(b^9,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A085312(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

a[n_] := Table[PowerMod[i, 9, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 25 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^9%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A085313 Number of distinct 10th power residues modulo n.

Original entry on oeis.org

1, 2, 2, 2, 3, 4, 4, 2, 4, 6, 2, 4, 7, 8, 6, 3, 9, 8, 10, 6, 8, 4, 12, 4, 3, 14, 10, 8, 15, 12, 4, 5, 4, 18, 12, 8, 19, 20, 14, 6, 5, 16, 22, 4, 12, 24, 24, 6, 22, 6, 18, 14, 27, 20, 6, 8, 20, 30, 30, 12, 7, 8, 16, 9, 21, 8, 34, 18, 24, 24, 8, 8, 37, 38, 6, 20, 8, 28, 40, 9, 28, 10, 42, 16

Offset: 1

Labos Elemer, Jun 27 2003

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

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

Cf. A000224[k=2], A046530[k=3], A052273[k=4], A052274[k=5], A052275[k=6], A085310[k=7], A085311[k=8], A085312[k=9], A085314[k=11], A228849[k=12], A055653.

A085313 := proc(m)
    {seq( modp(b^10,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A085313(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

a[n_] := Table[PowerMod[i, 10, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 25 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^10%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A085314 Number of distinct 11th powers modulo n.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 5, 7, 10, 11, 9, 13, 14, 15, 9, 17, 14, 19, 15, 21, 22, 3, 15, 21, 26, 19, 21, 29, 30, 31, 17, 33, 34, 35, 21, 37, 38, 39, 25, 41, 42, 43, 33, 35, 6, 47, 27, 43, 42, 51, 39, 53, 38, 55, 35, 57, 58, 59, 45, 61, 62, 49, 33, 65, 66, 7, 51, 9, 70, 71, 35, 73, 74, 63

Offset: 1

Labos Elemer, Jun 27 2003

Compare with enigmatic similarity of this and analogous odd-th power counts to A055653.

This sequence is multiplicative [Li]. - Leon P Smith, Apr 16 2005

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

Cf. A000224[k=2], A046530[k=3], A052273[k=4], A052274[k=5], A052275[k=6], A085310[k=7], A085311[k=8], A085312[k=9], A085313[k=10], A228849[k=12], A055653.

A085314 := proc(m)
    {seq( modp(b^11,m),b=0..m-1) };
    nops(%) ;
end proc:
seq(A085314(m),m=1..100) ; # R. J. Mathar, Sep 22 2017

a[n_] := Table[PowerMod[i, 11, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 25 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^11%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A228849 Number of distinct 12th powers modulo n.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 6, 4, 2, 4, 4, 2, 5, 4, 4, 4, 4, 12, 12, 4, 6, 4, 4, 4, 8, 8, 6, 3, 12, 10, 4, 4, 4, 8, 4, 4, 11, 8, 8, 12, 4, 24, 24, 4, 8, 12, 10, 4, 14, 8, 12, 4, 8, 16, 30, 8, 6, 12, 4, 5, 4, 24, 12, 10, 24, 8, 36, 4, 7, 8, 12, 8, 12, 8, 14, 4, 10

Offset: 1

Arkadiusz Wesolowski, Sep 05 2013

R. J. Mathar, Table of n, a(n) for n = 1..10000

Cf. A000224 (squares), A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers).

[#Set([k^12 mod n : k in [1..n]]) : n in [1..81]];

A228849 := proc(n)
    {seq(i^12 mod n, i=0..n-1)} ;
    nops(%) ;
end proc: # R. J. Mathar, Sep 21 2017

a[n_] := Table[PowerMod[i, 12, n], {i, 0, n - 1}] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Mar 24 2020 *)

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], my(k=f[i, 1]^f[i, 2]); #vecsort(vector(k, i, i^12%k), , 8)) \\ Charles R Greathouse IV, Sep 05 2013

A290731 Number of distinct values of X*(X+1) mod n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 4, 4, 3, 6, 4, 7, 4, 6, 8, 9, 4, 10, 6, 8, 6, 12, 8, 11, 7, 11, 8, 15, 6, 16, 16, 12, 9, 12, 8, 19, 10, 14, 12, 21, 8, 22, 12, 12, 12, 24, 16, 22, 11, 18, 14, 27, 11, 18, 16, 20, 15, 30, 12, 31, 16, 16, 32, 21, 12, 34, 18, 24, 12, 36, 16, 37, 19, 22, 20, 24, 14, 40, 24

Offset: 1

N. J. A. Sloane, Aug 10 2017

Also the number of distinct values of X^2+X+1 mod n. - N. J. A. Sloane, Oct 05 2024

			The values taken by X^2+X mod n for small n are:
1, [0]
2, [0]
3, [0, 2]
4, [0, 2]
5, [0, 1, 2]
6, [0, 2]
7, [0, 2, 5, 6]
8, [0, 2, 4, 6]
9, [0, 2, 3, 6]
10, [0, 2, 6]
11, [0, 1, 2, 6, 8, 9]
12, [0, 2, 6, 8]
...

Andrew Howroyd, Table of n, a(n) for n = 1..10000
Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], (24-August-2016). See Table 5.

Cf. A000224 (analog for X^2), A290732.

a:=[]; M:=80;
for n from 1 to M do
q1:={};
for i from 0 to n-1 do q1:={op(q1), (i^2+i) mod n}; od;
s1:=sort(convert(q1,list));
a:=[op(a),nops(s1)];
od:
a;

a[n_] := Product[{p, e} = pe; If[p==2, 2^(e-1), 1+Quotient[p^(e+1), (2p+2)]], {pe, FactorInteger[n]}];
Array[a, 100] (* Jean-François Alcover, Aug 05 2018, after Andrew Howroyd *)

a(n)={my(v=vector(n)); for(i=0, n-1, v[i*(i+1)%n + 1]=1); vecsum(v)} \\ Andrew Howroyd, Aug 01 2018

a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); if(p==2, 2^(e-1), 1 + p^(e+1)\(2*p+2)))} \\ Andrew Howroyd, Aug 01 2018

from math import prod
from sympy import factorint
def A290731(n): return prod((p**(e+1)//(p+(q:=p>2))>>1)+q for p, e in factorint(n).items()) # Chai Wah Wu, Oct 07 2024

Multiplicative with a(2^e) = 2^(e-1), a(p^2) = 1 + floor(p^(e+1)/(2*p+2)) for odd prime p. - Andrew Howroyd, Aug 01 2018

cp's OEIS Frontend

A052273 Number of distinct 4th powers mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A052274 Number of distinct 5th powers mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A052275 Number of distinct 6th powers mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A085310 Number of distinct 7th powers modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A085311 Number of distinct 8th powers modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A085312 Number of distinct 9th powers modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A085313 Number of distinct 10th power residues modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs