A257301 -id:A257301 - cp's OEIS frontend

A046530 Number of distinct cubic residues mod n.

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

Offset: 1

David W. Wilson

In other words, number of distinct cubes mod n. - N. J. A. Sloane, Oct 05 2024
Cubic analog of A000224. - Steven Finch, Mar 01 2006
A074243 contains values of n such that a(n) = n. - Dmitri Kamenetsky, Nov 03 2012

T. D. Noe, Table of n, a(n) for n = 1..1000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2005-2016.
Shuguang 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.
Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 7.

For number of k-th power residues mod n, see A000224 (k=2), A052273 (k=4), A052274 (k=5), A052275 (k=6), A085310 (k=7), A085311 (k=8), A085312 (k=9), A085313 (k=10), A085314 (k=12), A228849 (k=13).

Cf. A000578, A087786, A257301.

import Data.List (nub)
a046530 n = length $ nub $ map (`mod` n) $
                           take (fromInteger n) $ tail a000578_list
-- Reinhard Zumkeller, Aug 01 2012

A046530 := proc(n)
        local a,pf ;
        a := 1 ;
        if n = 1 then
                return 1;
        end if;
        for i in  ifactors(n)[2] do
                p := op(1,i) ;
                e := op(2,i) ;
                if p = 3 then
                        if e mod 3 = 0 then
                                a := a*(3^(e+1)+10)/13 ;
                        elif e mod 3 = 1 then
                                a := a*(3^(e+1)+30)/13 ;
                        else
                                a := a*(3^(e+1)+12)/13 ;
                        end if;
                elif p mod 3 = 2 then
                        if e mod 3 = 0 then
                                a := a*(p^(e+2)+p+1)/(p^2+p+1) ;
                        elif e mod 3 = 1 then
                                a := a*(p^(e+2)+p^2+p)/(p^2+p+1) ;
                        else
                                a := a*(p^(e+2)+p^2+1)/(p^2+p+1) ;
                        end if;
                else
                        if e mod 3 = 0 then
                                a := a*(p^(e+2)+2*p^2+3*p+3)/3/(p^2+p+1) ;
                        elif e mod 3 = 1 then
                                a := a*(p^(e+2)+3*p^2+3*p+2)/3/(p^2+p+1) ;
                        else
                                a := a*(p^(e+2)+3*p^2+2*p+3)/3/(p^2+p+1) ;
                        end if;
                end if;
        end do:
        a ;
end proc:
seq(A046530(n),n=1..40) ; # R. J. Mathar, Nov 01 2011

Length[Union[#]]& /@ Table[Mod[k^3, n], {n, 75}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *)
Length[Union[#]]&/@Table[PowerMod[k,3,n],{n,80},{k,n}] (* Harvey P. Dale, Aug 12 2015 *)

g(p,e)=if(p==3,(3^(e+1)+if(e%3==1,30,if(e%3,12,10)))/13, if(p%3==2, (p^(e+2)+if(e%3==1,p^2+p,if(e%3,p^2+1,p+1)))/(p^2+p+1),(p^(e+2)+if(e%3==1,3*p^2+3*p+2, if(e%3,3*p^2+2*p+3,2*p^2+3*p+3)))/3/(p^2+p+1)))
a(n)=my(f=factor(n));prod(i=1,#f[,1],g(f[i,1],f[i,2])) \\ Charles R Greathouse IV, Jan 03 2013

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); 1 + sum(i=0, (e-1)\3, if(p%3==1 || (p==3&&3*iAndrew Howroyd, Jul 17 2018

a(n) = n - A257301(n). - Stanislav Sykora, Apr 21 2015
a(2^n) = A046630(n). a(3^n) = A046631(n). a(5^n) = A046633(n). a(7^n) = A046635(n). - R. J. Mathar, Sep 28 2017
Multiplicative with a(p^e) = 1 + Sum_{i=0..floor((e-1)/3)} (p - 1)*p^(e-3*i-1)/k where k = 3 if (p = 3 and 3*i + 1 = e) or (p mod 3 = 1) otherwise k = 1. - Andrew Howroyd, Jul 17 2018
Sum_{k=1..n} a(k) ~ c * n^2/log(n)^(1/3), where c = (6/(13*Gamma(2/3))) * (2/3)^(-1/3) * Product_{p prime == 2 (mod 3)} (1 - (p^2+1)/((p^2+p+1)*(p^2-p+1)*(p+1))) * (1-1/p)^(-1/3) * Product_{p prime == 1 (mod 3)} (1 - (2*p^4+3*p^2+3)/(3*(p^2+p+1)*(p^2-p+1)*(p+1))) * (1-1/p)^(-1/3) = 0.48487418844474389597... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022

A074243 Numbers n such that every integer has a cube root mod n.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 15, 17, 22, 23, 29, 30, 33, 34, 41, 46, 47, 51, 53, 55, 58, 59, 66, 69, 71, 82, 83, 85, 87, 89, 94, 101, 102, 106, 107, 110, 113, 115, 118, 123, 131, 137, 138, 141, 142, 145, 149, 159, 165, 166, 167, 170, 173, 174, 177, 178, 179, 187, 191, 197

Offset: 1

Jack Brennen, Sep 19 2002

A positive integer n is in the sequence if x^3 (modulo n) describes a bijection from the set [0...n-1] to itself.
Every member of the sequence is squarefree. If m and n are coprime members of the sequence, m*n is also a member.
All primes > 3 in this sequence are congruent to 5 mod 6. See A045309. - Zak Seidov, Feb 16 2013
Products of distinct members of A045309 (primes not 1 mod 3). - Charles R Greathouse IV, Apr 20 2015
This sequence gives all values, ordered increasingly, for which A257301 vanishes, i.e., A257301(a(n))=0 for any n. - Stanislav Sykora, May 26 2015

			The number 30 is in the sequence because the function x^3 (mod 30) describes a bijection from [0...29] to itself. Thus every integer has a cube root, modulo 30.

Robert Israel, Table of n, a(n) for n = 1..10000 (terms 1..1501 from Zak Seidov).
Olivier Garet, How often is x->x^3 one-to-one in Z/nZ?, arXiv:2504.13511 [math.NT], 2025.
Dainis Zeps, On Grinbergs' differential geometry and finite fields, University of Latvia (2019).

Cf. A045309, A257301.

N:= 1000: # to get all terms <= N
Primes:= {2,3} union select(isprime, {seq(6*i+5,i=0..floor((N-5)/6))}):
A:= {1}:
for p in Primes do
A:= A union map(`*`, select(`<=`, A, floor(N/p)),p)
od:
A;
# if using Maple 11 or earlier, uncomment the next line
# sort(convert(A,list)); # Robert Israel, Apr 20 2015

fQ[n_] := Sort[PowerMod[#, 3, n] & /@ Range@ n] == Range@ n - 1; Select[Range@ 200, fQ] (* Michael De Vlieger, Apr 20 2015 *)

is(n)=my(f=factor(n)); if(n>1 && vecmax(f[,2])>1, return(0)); for(i=1,#f~, if(f[i,1]%3==1, return(0))); 1 \\ Charles R Greathouse IV, Apr 20 2015

a(n) ~ k*n*sqrt(log(n)) for some constant k. - Charles R Greathouse IV, Apr 20 2015

New name from Charles R Greathouse IV, Apr 20 2015

A257302 Number of 4th power nonresidues modulo n.

Original entry on oeis.org

0, 0, 1, 2, 3, 2, 3, 6, 5, 6, 5, 8, 9, 6, 11, 14, 12, 10, 9, 16, 13, 10, 11, 20, 19, 18, 17, 20, 21, 22, 15, 28, 21, 24, 27, 28, 27, 18, 31, 36, 30, 26, 21, 32, 37, 22, 23, 44, 27, 38, 41, 44, 39, 34, 43, 48, 37, 42, 29, 52, 45, 30, 47, 58, 57, 42, 33, 58

Offset: 1

Stanislav Sykora, Apr 19 2015

nonn

a(n) is the number of values r, 0<=r=0, (m^p)%n != r.

Stanislav Sykora, Table of n, a(n) for n = 1..10000

Cf. A095972 (p=2), A257301 (p=3), A257303 (p=5).

Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^4, n]]]], {n, 100}] (* Vincenzo Librandi, Apr 20 2015 *)

nrespowp(n,p) = {my(v=vector(n),d=0);
  for(r=0,n-1,v[1+(r^p)%n]+=1);
  for(k=1,n,if(v[k]==0,d++));
  return(d);}
a(n) = nrespowp(n,4)

a(n) = n - A052273(n).

Satisfies a(n) <= n-2 (residues 0 and 1 are always present).

A257303 Number of 5th power nonresidues modulo n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 3, 2, 0, 8, 3, 0, 0, 0, 7, 0, 4, 0, 5, 0, 16, 0, 9, 20, 0, 8, 7, 0, 0, 24, 15, 24, 0, 0, 15, 0, 0, 0, 15, 32, 0, 0, 35, 10, 0, 0, 21, 6, 40, 0, 13, 0, 16, 40, 21, 0, 0, 0, 15, 48, 48, 14, 30, 0, 48, 0, 17, 0, 0, 56, 37, 0, 0, 60, 19, 56, 0, 0, 35, 26, 64, 0, 21, 0, 0, 0, 73, 0

Offset: 1

Stanislav Sykora, Apr 19 2015

nonn

a(n) is the number of values r, 0<=r=0, (m^p)%n != r.

Stanislav Sykora, Table of n, a(n) for n = 1..10000

Cf. A095972 (p=2), A257301 (p=3), A257302 (p=4).

Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^5, n]]]], {n, 100}] (* Vincenzo Librandi, Apr 20 2015 *)

nrespowp(n,p) = {my(v=vector(n),d=0);
  for(r=0,n-1,v[1+(r^p)%n]+=1);
  for(k=1,n,if(v[k]==0,d++));
  return(d);}
a(n) = nrespowp(n,5)

a(n) = n-A052274(n).

Satisfies a(n) <= n-3 (residues 0, 1, and n-1 are always present).

cp's OEIS Frontend

A046530 Number of distinct cubic residues mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

A074243 Numbers n such that every integer has a cube root mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A257302 Number of 4th power nonresidues modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A257303 Number of 5th power nonresidues modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula