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

A365100 Number of distinct residues of x^n (mod n^3), x=0..n^3-1.

Original entry on oeis.org

1, 3, 7, 6, 21, 8, 43, 18, 55, 22, 111, 20, 157, 44, 147, 65, 273, 56, 343, 30, 105, 112, 507, 68, 501, 158, 487, 110, 813, 88, 931, 257, 777, 274, 903, 140, 1333, 344, 371, 102, 1641, 64, 1807, 280, 1155, 508, 2163, 260, 2059, 502, 1911, 200, 2757, 488, 483, 374, 805, 814

Offset: 1

Albert Mukovskiy, Aug 21 2023

nonn

Cf. A195637, A365099, A365101, A365102, A023105, A046631, A365103, A365104.

a(n) = #Set(vector(n^3, x, Mod(x-1,n^3)^n)); \\ Michel Marcus, Aug 22 2023

def A365100(n): return len({pow(x,n,n**3) for x in range(n**3)}) # Chai Wah Wu, Aug 23 2023

A365101 Number of distinct residues of x^n (mod n^4), x=0..n^4-1.

Original entry on oeis.org

1, 4, 21, 18, 101, 30, 295, 130, 487, 153, 1211, 170, 2029, 444, 1919, 1025, 4625, 732, 6499, 442, 1881, 1818, 11639, 1290, 12501, 3045, 13123, 2516, 23549, 1530, 28831, 8193, 23009, 6939, 29795, 4148, 49285, 9750, 12863, 3354, 67241, 1500, 77659, 10302, 49187, 17460, 101615

Offset: 1

Albert Mukovskiy, Aug 21 2023

nonn

Cf. A195637, A365099, A365100, A365102, A023105, A046631, A365103, A365104.

a(n) = #Set(vector(n^4, x, Mod(x-1,n^4)^n)); \\ Michel Marcus, Aug 22 2023

def A365101(n): return len({pow(x,n,n**4) for x in range(n**4)}) # Chai Wah Wu, Aug 23 2023

A365103 Number of distinct quartic residues x^4 (mod 4^n), x=0..4^n-1.

Original entry on oeis.org

1, 2, 2, 6, 18, 70, 274, 1094, 4370, 17478, 69906, 279622, 1118482, 4473926, 17895698, 71582790, 286331154, 1145324614, 4581298450, 18325193798, 73300775186, 293203100742, 1172812402962, 4691249611846, 18764998447378

Offset: 0

Albert Mukovskiy, Aug 24 2023

nonn

a(n) = A364811(2n).
For n>=2, A319281(a(n)) == 4^n + [n mod 2 == 1].
For n>=2, a(n)=k: [ A319281(k) == 4^n + [n mod 2 == 1] ].

Index entries for linear recurrences with constant coefficients, signature (4, 1, -4).

Cf. A023105, A046631, A195637, A365104, A364811, A319281.

a[n_] = Ceiling[4^n/15] + Boole[Mod[n,2]==1]; Array[a, 24]

PARI
```
a(n) = ceil(4^n/15)+(Mod(n,2)==1);
```

def A365103(n): return len({pow(x,4,1<<(n<<1)) for x in range(1<<(n<<1))}) # Chai Wah Wu, Sep 18 2023

a(n) = ceiling(4^n/15) + (n mod 2).

A365099 Number of distinct residues of x^n (mod n^2), x=0..n^2-1.

Original entry on oeis.org

1, 2, 3, 2, 5, 4, 7, 3, 7, 6, 11, 4, 13, 8, 15, 5, 17, 8, 19, 4, 9, 12, 23, 6, 21, 14, 19, 8, 29, 12, 31, 9, 33, 18, 35, 8, 37, 20, 15, 6, 41, 8, 43, 12, 35, 24, 47, 10, 43, 22, 51, 8, 53, 20, 15, 12, 21, 30, 59, 8, 61, 32, 21, 17, 65, 24, 67, 10, 69, 24, 71, 12, 73, 38, 63

Offset: 1

Albert Mukovskiy, Aug 21 2023

nonn

Cf. A195637, A365100, A365101, A365102, A023105, A046631, A365103.

a(n) = #Set(vector(n^2, x, Mod(x-1,n^2)^n)); \\ Michel Marcus, Aug 22 2023

def A365099(n): return len({pow(x,n,n**2) for x in range(n**2)}) # Chai Wah Wu, Aug 22 2023

A365104 Number of distinct quintic residues x^5 (mod 5^n), x=0..5^n-1.

Original entry on oeis.org

1, 5, 5, 21, 101, 501, 2505, 12505, 62521, 312601, 1563001, 7815005, 39075005, 195375021, 976875101, 4884375501, 24421877505, 122109387505, 610546937521, 3052734687601, 15263673438001, 76318367190005, 381591835950005, 1907959179750021, 9539795898750101, 47698979493750501, 238494897468752505, 1192474487343762505, 5962372436718812521, 29811862183594062601

Offset: 0

Albert Mukovskiy, Aug 24 2023

It appears that for a prime p>2 the number of distinct residues x^p (mod p^n) is a(n) = (p-1)*p^(n-2) + a(n-p), with a(n<1)=1, a(1)=p.

Index entries for linear recurrences with constant coefficients, signature (5,0,0,0,1,-5).

Cf. A023105, A046631, A195637, A365099, A365100, A365101, A365102.

a[n_]:=CountDistinct[Table[PowerMod[x-1, 5, 5^(n-1)], {x, 1, 5^(n-1)}]]; Array[a, 13]

def A365104(n): return len({pow(x,5,5**n) for x in range(5**n)}) # Chai Wah Wu, Sep 17 2023

For n >= 6, a(n) = 4*5^(n-2) + a(n-5) = 5*a(n-1) + a(n-5) - 5*a(n-6). O.g.f: (-5*x^5 - 4*x^4 - 4*x^3 - 20*x^2 + 1)/(5*x^6 - x^5 - 5*x + 1). - Max Alekseyev, Feb 19 2024

Terms a(16) onward from Max Alekseyev, Feb 19 2024

A367484 Number of integers of the form (x^4 + y^4) mod 3^n; a(n) = A289559(3^n).

Original entry on oeis.org

1, 3, 7, 19, 55, 165, 493, 1477, 4429, 13287, 39859, 119575, 358723, 1076169, 3228505, 9685513, 29056537

Offset: 0

Albert Mukovskiy, Nov 19 2023

It appears that for n > 4: a(n) = 2*3^(n-1) + a(n-4).
For n < 5: a(n) = 2*3^(n-1) + 1.
Conjecture in closed form: a(n) = 2*ceiling(3^(n+3)/80) - 1.

Subsequence of A289559.

Cf. A000244, A039300, A046631, A155918.

a(n) = #setbinop((x, y)->Mod(x,3^n)^4+Mod(y,3^n)^4, [0..3^n-1]);

def A367484(n):
    m = 3**n
    return len({(pow(x,4,m)+pow(y,4,m))%m for x in range(m) for y in range(x+1)}) # Chai Wah Wu, Jan 23 2024

Conjecture: a(n) = 2*ceiling(3^(n+3)/80) - 1.

a(n) = A289559(3^n). - Thomas Scheuerle, Nov 20 2023

A046634 Number of cubic residues mod 6^n.

Original entry on oeis.org

1, 6, 9, 35, 210, 1083, 6253, 37518, 222705, 1331099, 7986594, 47871651, 287102581, 1722615486, 10334532969, 62003849075, 372023094450, 2232108315723, 13392560190013, 80355361140078, 482131358602785

Offset: 0

David W. Wilson

Index entries for linear recurrences with constant coefficients, signature (6,0,36,-216,0,-251,1506,0,216,-1296)

LinearRecurrence[{6,0,36,-216,0,-251,1506,0,216,-1296},{1,6,9,35,210,1083,6253,37518,222705,1331099},30] (* Harvey P. Dale, Mar 17 2023 *)

From R. J. Mathar, Feb 27 2011: (Start)
a(n) = A046530(6^n) = A046631(n)*A046630(n).
a(n) = +6*a(n-1) +36*a(n-3) -216*a(n-4) -251*a(n-6) +1506*a(n-7) +216*a(n-9) -1296*a(n-10).
G.f.: ( 1-27*x^2-55*x^3+795*x^5+690*x^6-2808*x^8-1296*x^9 ) / ( (x-1) *(6*x-1) *(3*x-1) *(2*x-1) *(1+x+x^2) *(4*x^2+2*x+1) *(9*x^2+3*x+1) ). (End)

A046637 Number of cubic residues mod 9^n.

Original entry on oeis.org

1, 3, 21, 169, 1515, 13629, 122641, 1103763, 9933861, 89404729, 804642555, 7241782989, 65176046881, 586584421923, 5279259797301, 47513338175689, 427620043581195, 3848580392230749, 34637223530076721, 311735011770690483

Offset: 0

David W. Wilson

Index entries for linear recurrences with constant coefficients, signature (9,0,1,-9)

LinearRecurrence[{9,0,1,-9},{1,3,21,169},30] (* Harvey P. Dale, Oct 09 2017 *)

a(n) = A046530(9^n) = A046631(2n). G.f. ( 1-6*x-6*x^2-21*x^3 ) / ( (x-1)*(9*x-1)*(1+x+x^2) ). - R. J. Mathar, Feb 28 2011

If n>=1, a(n) = 9*a(n-1) -6 if n is not a multiple of 3, otherwise a(n) = 9*a(n-1) -20. - Vincenzo Librandi, Mar 18 2011

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

A365100 Number of distinct residues of x^n (mod n^3), x=0..n^3-1.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

A365101 Number of distinct residues of x^n (mod n^4), x=0..n^4-1.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

A365103 Number of distinct quartic residues x^4 (mod 4^n), x=0..4^n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A365099 Number of distinct residues of x^n (mod n^2), x=0..n^2-1.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

A365104 Number of distinct quintic residues x^5 (mod 5^n), x=0..5^n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A367484 Number of integers of the form (x^4 + y^4) mod 3^n; a(n) = A289559(3^n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Python

Formula

A046634 Number of cubic residues mod 6^n.

Views

Author

Keywords

Links

Programs

Mathematica