A087786 -id:A087786 - 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

A376203 a(n) = A376202(2*n-1)/2.

Original entry on oeis.org

0, 1, 0, 3, 0, 0, 6, 0, 0, 9, 6, 0, 0, 0, 0, 15, 0, 0, 18, 12, 0, 21, 0, 0, 21, 0, 0, 0, 18, 0, 30, 0, 0, 33, 0, 0, 36, 0, 0, 39, 0, 0, 0, 0, 0, 72, 30, 0, 48, 0, 0, 51, 0, 0, 54, 36, 0, 0, 0, 0, 0, 0, 0, 63, 42, 0, 108, 0, 0, 69

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..7814

Cf. A000086, A087786, A046530, A290731, A376202, A376755, A376756, A376757.

from math import gcd
def A376203(n):
    c, m = 0, (n<<1)-1
    for x in range(1,m):
        if gcd(x,m) == 1:
            for y in range(x,m):
                if gcd(y,m)==gcd(z:=x+y,m)==1 and not (w:=z**2-x*y)//gcd(w,x*y*z)%m:
                    c += 1
    return c>>1 # Chai Wah Wu, Oct 06 2024

A376755 a(n) = A376202(6*n+1)/6.

Original entry on oeis.org

1, 2, 3, 0, 5, 6, 7, 7, 0, 10, 11, 12, 13, 0, 24, 16, 17, 18, 0, 0, 21, 36, 23, 0, 25, 26, 27, 26, 0, 30, 0, 32, 33, 0, 35, 60, 37, 38, 0, 40, 72, 0, 72, 0, 45, 46, 47, 0, 0, 84, 51, 52, 0, 0, 55, 56, 49, 58, 0, 57, 61, 62, 63, 0, 0, 66, 120, 68, 0, 70, 120, 72

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..3470

Cf. A000086, A046530, A087786, A290731, A376202, A376203, A376756, A376757.

from math import gcd
def A376755(n):
    c, m = 0, 6*n|1
    for x in range(1,m):
        if gcd(x,m) == 1:
            for y in range(x,m):
                if gcd(y,m)==gcd(z:=x+y,m)==1 and not (w:=z**2-x*y)//gcd(w,x*y*z)%m:
                    c += 1
    return c//6 # Chai Wah Wu, Oct 06 2024

a(51)-a(72) from Chai Wah Wu, Oct 06 2024

A376756 Number of pairs 0 <= x <= y <= n-1 such that x^2 + x*y + y^2 == 0 (mod n).

Original entry on oeis.org

1, 1, 3, 3, 1, 3, 7, 3, 6, 1, 1, 9, 13, 7, 3, 10, 1, 6, 19, 3, 21, 1, 1, 9, 15, 13, 18, 27, 1, 3, 31, 10, 3, 1, 7, 21, 37, 19, 39, 3, 1, 21, 43, 3, 6, 1, 1, 30, 70, 15, 3, 51, 1, 18, 1, 27, 57, 1, 1, 9, 61, 31, 60, 36, 13, 3, 67, 3, 3, 7, 1, 21, 73, 37, 45, 75, 7, 39, 79, 10, 45, 1, 1, 81, 1, 43, 3, 3, 1, 6, 163, 3, 93, 1, 19, 30, 97

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000086, A046530, A087786, A290731, A376202, A376203, A376755, A376757.

def A376756(n):
    c = 0
    for x in range(n):
        z = x**2%n
        for y in range(x,n):
            if not (z+y*(x+y))%n:
                c += 1
    return c # Chai Wah Wu, Oct 06 2024

A376757 Number of pairs 0 <= x <= y <= n-1 such that x^3 == y^3 (mod n).

Original entry on oeis.org

1, 2, 3, 5, 5, 6, 13, 14, 18, 10, 11, 15, 25, 26, 15, 28, 17, 36, 37, 25, 39, 22, 23, 42, 35, 50, 81, 71, 29, 30, 61, 72, 33, 34, 65, 99, 73, 74, 75, 70, 41, 78, 85, 55, 90, 46, 47, 84, 112, 70, 51, 137, 53, 162, 55, 218, 111, 58, 59, 75, 121, 122, 288, 208, 125, 66, 133, 85, 69, 130, 71, 306, 145, 146, 105, 203, 143, 150, 157

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

A087786 includes pairs (x,y) with x>y (which are excluded from the present sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000086, A087786, A046530, A290731, A376202, A376203, A376755, A376756.

a(n) = sum(x=0, n-1, sum(y=x, n-1, Mod(x, n)^3 == Mod(y, n)^3)); \\ Michel Marcus, Oct 06 2024

from collections import Counter
def A376757(n): return sum(d*(d+1)>>1 for d in Counter(pow(x,3,n) for x in range(n)).values()) # Chai Wah Wu, Oct 06 2024

A087412 a(n) is the number of solutions to x^3 + y^3 == 1 (mod n).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 8, 18, 10, 11, 12, 6, 12, 15, 16, 17, 36, 24, 20, 18, 22, 23, 24, 25, 12, 54, 24, 29, 30, 33, 32, 33, 34, 30, 72, 24, 48, 18, 40, 41, 36, 33, 44, 90, 46, 47, 48, 42, 50, 51, 24, 53, 108, 55, 48, 72, 58, 59, 60

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 21 2003

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A087786.

a[n_] := Module[{v = Table[0, {n}]}, For[i = 0, i <= n-1, i++, v[[Mod[i^3, n] + 1]]++]; Sum[v[[i+1]] v[[Mod[1-i, n] + 1]], {i, 0, n-1}]];
a /@ Range[1, 60] (* Jean-François Alcover, Sep 17 2019, after Andrew Howroyd *)

a(n) = {nb = 0; for (x = 0, n-1, for (y = 0, n-1, if (Mod(x^3,n) + Mod(y^3,n) == Mod(1, n), nb++););); nb;} \\ Michel Marcus, Aug 06 2013

a(n)={my(v=vector(n)); for(i=0, n-1, v[i^3%n + 1]++); sum(i=0, n-1, v[i+1]*v[(1-i)%n + 1])} \\ Andrew Howroyd, Jul 17 2018

From Andrew Howroyd, Jul 17 2018: (Start)
a(p^e) = p^e for p prime and p mod 3 = 2.
Conjecture: a(3^e) = 2*3^e for e > 1.
a(p^e) = p^(e-1)*(p - 1 + Sum_{b=1..p-1} Legendre(12*b^(-1) - 3*b^2, p)) for p prime and p <> 3.
The final formula arises from factoring x^3 + y^3 as (x + y)*(x*2 - x*y + y^2), then substituting b = x + y and counting the solutions to the resulting quadratic equation 3*x^2 - 3*b*x + b^2 == b^(-1) (mod p) for each nonzero value of b. (End)

More terms from Michel Marcus, Aug 06 2013

A137401 a(n) is the number of ordered solutions (x,y,z) to x^3 + y^3 == z^3 mod n with 1 <= x,y,z <= n-1.

Original entry on oeis.org

0, 0, 2, 7, 12, 20, 0, 63, 116, 72, 90, 131, 0, 108, 182, 339, 240, 602, 324, 415, 326, 420, 462, 839, 604, 216, 1808, 763, 756, 812, 810, 1735, 992, 1056, 1092, 3311, 648, 1620, 650, 2511, 1560, 1640, 1134, 2227, 4328, 1980, 2070, 3683, 2484, 2644, 2450, 1519

Offset: 1

Neven Juric (neven.juric(AT)apis-it.hr), Apr 11 2008

nonn

Record values of A137401: 0, 2, 7, 12, 20, 63, 116, 131, 182, 339, 602, 839, 1808, 3311, 4328, 7964, 8864, 9231, 19583, 21986, 41363, 52676, 81467, 87596, 92087, 112616, 236951, 247940, 378071, 386423, 521135, ... - Robert G. Wilson v

			a(4)=7 because (1, 2, 1), (1, 3, 2), (2, 1, 1), (2, 2, 2), (2, 3, 3), (3, 1, 2), (3, 2, 3) are solutions for n=4.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms n = 1..425 from Robert G. Wilson v)

Cf. A063454.

f[n_] := Block[ {c = 0}, Do[ If[ Mod[x^3 + y^3, n] == Mod[z^3, n], c++ ], {x, n - 1}, {y, n - 1}, {z, n - 1}]; c];
Table[Length[Select[Tuples[Range[n - 1], 3], Mod[ #[[1]]^3 + #[[2]]^3 - #[[3]]^3, n] == 0 &]], {n, 2, 50}] (* Stefan Steinerberger, Apr 12 2008 *)

def A137401(n):
    ndict = {}
    for i in range(1,n):
        m = pow(i,3,n)
        if m in ndict:
            ndict[m] += 1
        else:
            ndict[m] = 1
    count = 0
    for i in ndict:
        ni = ndict[i]
        for j in ndict:
            k = (i+j) % n
            if k in ndict:
                count += ni*ndict[j]*ndict[k]
    return count # Chai Wah Wu, Jun 06 2017

a(n) = A063454(n)-3*A087786(n)+3*A000189(n)-1. - Vladeta Jovovic, Apr 11 2008

More terms from Stefan Steinerberger and Robert G. Wilson v, Apr 12 2008

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Original entry on oeis.org

1, 8, 27, 64, 125, 216, 336, 512, 1296, 1000, 1331, 1728, 1794, 2688, 3375, 4096, 4913, 10368, 7410, 8000, 9072, 10648, 12167, 13824, 15625, 14352, 34992, 21504, 24389, 27000, 30225, 32768, 35937, 39304, 42000, 82944, 48396, 59280, 48438, 64000, 68921, 72576, 77529, 85184, 162000, 97336

Offset: 1

José María Grau Ribas, Sep 22 2016

It appears that a(n) = n^3 for n in A088232. See also A066498. - Michel Marcus, Oct 11 2016

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A000189, A047726, A060839, A063454, A087412, A087786, A254073, A276920.

JJJ[4, n, lam] = Sum[If[Mod[a^3 + b^3 + c^3 + d^3, n] == Mod[lam, n], 1, 0], {d, 0, n - 1}, {a, 0, n - 1}, {b, 0, n - 1}, {c, 0 , n - 1}]; Table[JJJ[4, n, 1], {n, 1, 50}]

a(n) = sum(x=1, n, sum(y=1, n, sum(z=1, n, sum(t=1, n, Mod(x,n)^3 + Mod(y,n)^3 + Mod(z,n)^3 + Mod(t,n)^3 == 1)))); \\ Michel Marcus, Oct 11 2016

qperms(v) = {my(r=1,t); v = vecsort(v); for(i=1,#v-1, if(v[i]==v[i+1], t++, r*=binomial(i,t+1);t=0));r*=binomial(#v,t+1)}
a(n) = {my(t=0); forvec(v=vector(4,i,[1,n]), if(sum(i=1, 4, Mod(v[i], n)^3)==1, print1(v", "); t+=qperms(v)),1);t} \\ David A. Corneth, Oct 11 2016

def A276919(n):
    ndict = {}
    for i in range(n):
        i3 = pow(i,3,n)
        for j in range(i+1):
            j3 = pow(j,3,n)
            m = (i3+j3) % n
            if m in ndict:
                if i == j:
                    ndict[m] += 1
                else:
                    ndict[m] += 2
            else:
                if i == j:
                    ndict[m] = 1
                else:
                    ndict[m] = 2
    count = 0
    for i in ndict:
        j = (1-i) % n
        if j in ndict:
            count += ndict[i]*ndict[j]
    return count # Chai Wah Wu, Jun 06 2017

A276920 Number of solutions to x^3 + y^3 + z^3 + t^3 == 0 (mod n) for 1 <= x, y, z, t <= n.

Original entry on oeis.org

1, 8, 27, 72, 125, 216, 595, 704, 1539, 1000, 1331, 1944, 3133, 4760, 3375, 5632, 4913, 12312, 8911, 9000, 16065, 10648, 12167, 19008, 16125, 25064, 45927, 42840, 24389, 27000, 35371, 47104, 35937, 39304, 74375, 110808, 58645, 71288, 84591, 88000

Offset: 1

José María Grau Ribas, Sep 22 2016

a(n) = n^3 if n is in A074243. - Robert Israel, Oct 13 2016

			For n = 3, we see that all nondecreasing solutions {x, y, z, t} are in {{1, 1, 1, 3}, {1, 1, 2, 2}, {1, 2, 3, 3}, {2, 2, 2, 3}, {3, 3, 3, 3}}. The numbers in the sets can be ordered in 4, 6, 12, 4 and 1 ways respectively. Therefore, a(3) = 4 + 6 + 12 + 4 + 1 = 27. - _David A. Corneth_, Oct 11 2016

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms n = 1..242 from Robert Israel)

Cf. A000189, A047726, A060839, A063454, A074243, A087412, A087786, A254073, A276919.

CF:= table([[false, false, true] = 12, [true, false, false] = 12, [true, false, true] = 6, [false, false, false] = 24, [true, true, true] = 1, [false, true, true] = 4, [false, true, false] = 12, [true, true, false] = 4]):
f1:= proc(n)
  option remember;
  local count, t, x,y,z,signature;
  if isprime(n) and n mod 3 = 2 then return n^3 fi;
  count:= 0;
  for t from 1 to n do
    for x from 1 to t do
      for y from 1 to x do
        for z from 1 to y do
          if t^3 + x^3 + y^3 + z^3 mod n = 0 then
            signature:= map(evalb,[z=y,y=x,x=t]);
            count:= count + CF[signature];
          fi
  od od od od;
  count
end proc:
f:= proc(n) local t;
    mul(f1(t[1]^t[2]),t=ifactors(n)[2])
end proc:
map(f, [$1..40]); # Robert Israel, Oct 13 2016

JJJ[4, n, lam] = Sum[If[Mod[a^3 + b^3 + c^3 + d^3, n] == Mod[lam, n], 1, 0], {d, 0, n - 1}, {a, 0, n - 1}, {b, 0, n - 1}, {c, 0 , n - 1}]; Table[JJJ[4, n, 0], {n, 1, 50}]

a(n) = sum(x=1, n, sum(y=1, n, sum(z=1, n, sum(t=1, n, Mod(x,n)^3 + Mod(y,n)^3 + Mod(z,n)^3 + Mod(t,n)^3 == 0)))); \\ Michel Marcus, Oct 11 2016

qperms(v) = {my(r=1,t); v = vecsort(v); for(i=1,#v-1, if(v[i]==v[i+1], t++, r*=binomial(i, t+1);t=0));r*=binomial(#v,t+1)}
a(n) = {my(t=0); forvec(v=vector(4,i,[1,n]), if(sum(i=1,4,Mod(v[i],n)^3)==0, t+=qperms(v)),1);t} \\ David A. Corneth, Oct 11 2016

def A276920(n):
    ndict = {}
    for i in range(n):
        i3 = pow(i,3,n)
        for j in range(i+1):
            j3 = pow(j,3,n)
            m = (i3+j3) % n
            if m in ndict:
                if i == j:
                    ndict[m] += 1
                else:
                    ndict[m] += 2
            else:
                if i == j:
                    ndict[m] = 1
                else:
                    ndict[m] = 2
    count = 0
    for i in ndict:
        j = (-i) % n
        if j in ndict:
            count += ndict[i]*ndict[j]
    return count # Chai Wah Wu, Jun 06 2017

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

A376203 a(n) = A376202(2*n-1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A376755 a(n) = A376202(6*n+1)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A376756 Number of pairs 0 <= x <= y <= n-1 such that x^2 + x*y + y^2 == 0 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A376757 Number of pairs 0 <= x <= y <= n-1 such that x^3 == y^3 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A087412 a(n) is the number of solutions to x^3 + y^3 == 1 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A137401 a(n) is the number of ordered solutions (x,y,z) to x^3 + y^3 == z^3 mod n with 1 <= x,y,z <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Views

Author

Keywords

Comments