A063454 -id:A063454 - cp's OEIS frontend

A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.

1, 4, 9, 24, 25, 36, 49, 96, 99, 100, 121, 216, 169, 196, 225, 448, 289, 396, 361, 600, 441, 484, 529, 864, 725, 676, 891, 1176, 841, 900, 961, 1792, 1089, 1156, 1225, 2376, 1369, 1444, 1521, 2400, 1681, 1764, 1849, 2904, 2475, 2116, 2209, 4032, 2695, 2900

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001

a(n) is multiplicative and, for a prime p, a(p) = p^2. Hence a(n) = n^2 if n is squarefree.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe, terms 1001..5000 from Seiichi Manyama)
Gottfried Helms, Pythagorean triples mod n / Solution enhanced, newsgroup sci.math.research, 2003.
László Tóth, Counting solutions of quadratic congruences in several variables revisited,arXiv:1404.4214 [math.NT], 2014.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
Index to sequences related to sums of squares.

Cf. A091143 (number of solutions to x^2 + y^2 = z^2 mod 2^n).
Cf. A060968, A087687, A002117, A013662.
Number of solutions to x^k + y^k = z^k mod n: this sequence (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

A062775 := proc(n)
    a := 1;
    for pe in ifactors(n)[2] do
        p := op(1,pe) ;
        e := op(2,pe) ;
        if p = 2 then
            if type(e,'odd') then
                a := a*p^((3*e+1)/2)*(2^((e+1)/2)-1) ;
            else
                a := a*p^(3*e/2)*(2^(e/2+1)-1) ;
            end if;
        else
            if type(e,'odd') then
                a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;
            else
                a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;
            end if;
        end if;
    end do:
    a ;
end proc:
seq(A062775(n),n=1..100) ; # R. J. Mathar, Jun 25 2018

Table[cnt=0; Do[If[Mod[x^2+y^2-z^2, n]==0, cnt++ ], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}]
f[p_, e_] := If[OddQ[e], p^(3*(e+1)/2 - 2)*(p^((e+1)/2) + p^((e-1)/2) - 1), p^(3*e/2 - 1) * (p^(e/2 + 1) + p^(e/2) - 1)]; f[2, e_] := If[OddQ[e], 2^(3*(e+1)/2 - 1)*(2^((e+1)/2) - 1), 2^(3*e/2)*(2^(e/2+1)-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Oct 18 2022 *)

a(n) is multiplicative. For the powers of primes p, there are four cases. For p=2, there are cases for even and odd powers: a(2^(2k-1)) = 2^(3k-1) (2^k-1) and a(2^(2k)) = 2^(3k) (2^(k+1)-1). Similarly, for odd primes p, a(p^(2k-1)) = p^(3k-2) (p^k+p^(k-1)-1) and a(p^(2k)) = p^(3k-1) (p^(k+1)+p^k-1). - T. D. Noe, Dec 22 2003
From  Gottfried Helms, May 13 2004: (Start)
If the canonical form of n is n = 2^i * 3^j * 5^k *... * p^q, then it appears that a(n) = n * f(2, i) * f(3, j) * f(5, k) * ... * f(p, q), where f(p, 1) = p for any prime p; f(2, i) = 2^i + 2^i - 2^ceiling(i/2); f(p, i) = p^i + p^(i-1) - p^floor((i-1)/2) for any odd prime p.
For example, a(7) = 49 because a(7) = 7*f(7, 1) = 7*7; a(16) = 448 because a(16) = a(2^4) = 16 * f(2, 4) = 16 * (16+16-4) = 16*28 = 448; a(12) = 216 because a(12) = a(3*2^2) = 12*f(2, 2)*f(3, 1) = 12*(4+4-2)*3 = 216. (End)
Sum_{k=1..n} a(k) ~ c * n^3, where c = (16/45) * Product_{p prime} (1 + 1/(p^3 + p^2 + p)) = (16/45)*zeta(3)/zeta(4) = 0.39488943478263044166... . - Amiram Eldar, Oct 18 2022, Nov 30 2023

More terms from Sascha Kurz, Mar 25 2002

A288099 Number of solutions to x^4 + y^4 = z^4 mod n.

Original entry on oeis.org

1, 4, 9, 24, 33, 36, 49, 192, 99, 132, 121, 216, 97, 196, 297, 1536, 193, 396, 361, 792, 441, 484, 529, 1728, 925, 388, 1377, 1176, 1121, 1188, 961, 6144, 1089, 772, 1617, 2376, 1441, 1444, 873, 6336, 481, 1764, 1849, 2904, 3267, 2116, 2209, 13824, 2695, 3700, 1737

Offset: 1

Seiichi Manyama, Jun 05 2017

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

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), this sequence (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^4)), 1-x^n)); vecsum(Vec( serconvol(lift(p^2) + O(x^n), lift(p) + O(x^n))))} \\ Andrew Howroyd, Jul 17 2018

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288100 Number of solutions to x^5 + y^5 = z^5 mod n.

Original entry on oeis.org

1, 4, 9, 20, 25, 36, 49, 112, 99, 100, 151, 180, 169, 196, 225, 704, 289, 396, 361, 500, 441, 604, 529, 1008, 1625, 676, 1377, 980, 841, 900, 1951, 4864, 1359, 1156, 1225, 1980, 1369, 1444, 1521, 2800, 601, 1764, 1849, 3020, 2475, 2116, 2209, 6336, 2695, 6500, 2601

Offset: 1

Seiichi Manyama, Jun 05 2017

Equivalently, the number of solutions to x^5 + y^5 + z^5 == 0 (mod n). - Andrew Howroyd, Jul 17 2018

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

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), this sequence (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^5)), 1-x^n)); polcoeff(lift(p^3), 0)} \\ Andrew Howroyd, Jul 17 2018

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288101 Number of solutions to x^6 + y^6 = z^6 mod n.

Original entry on oeis.org

1, 4, 9, 24, 25, 36, 73, 192, 243, 100, 121, 216, 217, 292, 225, 1024, 289, 972, 217, 600, 657, 484, 529, 1728, 725, 868, 2673, 1752, 841, 900, 1441, 6144, 1089, 1156, 1825, 5832, 3241, 868, 1953, 4800, 1681, 2628, 505, 2904, 6075, 2116, 2209, 9216, 3871, 2900, 2601

Offset: 1

Seiichi Manyama, Jun 05 2017

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

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), this sequence (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^6)), 1-x^n)); vecsum(Vec( serconvol(lift(p^2) + O(x^n), lift(p) + O(x^n))))} \\ Andrew Howroyd, Jul 17 2018

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288102 Number of solutions to x^7 + y^7 = z^7 mod n.

Original entry on oeis.org

1, 4, 9, 20, 25, 36, 49, 112, 99, 100, 121, 180, 169, 196, 225, 704, 289, 396, 361, 500, 441, 484, 529, 1008, 725, 676, 1377, 980, 589, 900, 961, 4864, 1089, 1156, 1225, 1980, 1369, 1444, 1521, 2800, 1681, 1764, 4999, 2420, 2475, 2116, 2209, 6336, 10633, 2900

Offset: 1

Seiichi Manyama, Jun 05 2017

Equivalently, the number of solutions to x^7 + y^7 + z^7 == 0 (mod n). - Andrew Howroyd, Jul 17 2018

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

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), this sequence (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^7)), 1-x^n)); polcoeff(lift(p^3), 0)} \\ Andrew Howroyd, Jul 17 2018

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288103 Number of solutions to x^8 + y^8 = z^8 mod n.

Original entry on oeis.org

1, 4, 9, 24, 33, 36, 49, 192, 99, 132, 121, 216, 97, 196, 297, 1536, 385, 396, 361, 792, 441, 484, 529, 1728, 925, 388, 1377, 1176, 1121, 1188, 961, 12288, 1089, 1540, 1617, 2376, 1441, 1444, 873, 6336, 641, 1764, 1849, 2904, 3267, 2116, 2209, 13824, 2695, 3700

Offset: 1

Seiichi Manyama, Jun 05 2017

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

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), this sequence (k=8), A288104 (k=9), A288105 (k=10).

Table[cnt=0; Do[If[Mod[x^8 + y^8 - z^8, n]==0, cnt++], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}] (* Vincenzo Librandi, Jul 18 2018 *)

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^8)), 1-x^n)); vecsum(Vec( serconvol(lift(p^2) + O(x^n), lift(p) + O(x^n))))} \\ Andrew Howroyd, Jul 17 2018

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288104 Number of solutions to x^9 + y^9 = z^9 mod n.

Original entry on oeis.org

1, 4, 9, 20, 25, 36, 55, 112, 189, 100, 121, 180, 109, 220, 225, 704, 289, 756, 487, 500, 495, 484, 529, 1008, 725, 436, 5103, 1100, 841, 900, 1081, 4864, 1089, 1156, 1375, 3780, 973, 1948, 981, 2800, 1681, 1980, 1513, 2420, 4725, 2116, 2209, 6336, 2989, 2900, 2601

Offset: 1

Seiichi Manyama, Jun 05 2017

Equivalently, the number of solutions to x^9 + y^9 + z^9 == 0 (mod n). - Andrew Howroyd, Jul 17 2018

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Seiichi Manyama)

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), this sequence (k=9), A288105 (k=10).

Table[cnt=0; Do[If[Mod[x^9 + y^9 - z^9, n]==0, cnt++], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}] (* Vincenzo Librandi, Jul 18 2018 *)

a(n)={my(p=Mod(sum(i=0, n-1, x^lift(Mod(i,n)^9)), 1-x^n)); polcoeff(lift(p^3), 0)} \\ Andrew Howroyd, Jul 17 2018

def A288104(n):
    ndict = {}
    for i in range(n):
        m = pow(i,9,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 05 2017

Keyword:mult added by Andrew Howroyd, Jul 17 2018

A288105 Number of solutions to x^10 + y^10 = z^10 mod n.

Original entry on oeis.org

1, 4, 9, 24, 25, 36, 49, 192, 99, 100, 201, 216, 169, 196, 225, 1024, 289, 396, 361, 600, 441, 804, 529, 1728, 3125, 676, 1377, 1176, 841, 900, 601, 6144, 1809, 1156, 1225, 2376, 1369, 1444, 1521, 4800, 1201, 1764, 1849, 4824, 2475, 2116, 2209, 9216, 2695, 12500

Offset: 1

Seiichi Manyama, Jun 05 2017

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Seiichi Manyama)

Number of solutions to x^k + y^k = z^k mod n: A062775 (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), this sequence (k=10).

Table[cnt=0; Do[If[Mod[x^10 + y^10 - z^10, n]==0, cnt++], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}] (* Vincenzo Librandi, Jul 18 2018 *)

def A288105(n):
    ndict = {}
    for i in range(n):
        m = pow(i,10,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 05 2017

Keyword:mult added by Andrew Howroyd, Jul 17 2018

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

cp's OEIS Frontend

A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A288099 Number of solutions to x^4 + y^4 = z^4 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A288100 Number of solutions to x^5 + y^5 = z^5 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A288101 Number of solutions to x^6 + y^6 = z^6 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A288102 Number of solutions to x^7 + y^7 = z^7 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A288103 Number of solutions to x^8 + y^8 = z^8 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A288104 Number of solutions to x^9 + y^9 = z^9 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A288105 Number of solutions to x^10 + y^10 = z^10 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs