A086933 -id:A086933 - cp's OEIS frontend

A062803 Number of solutions to x^2 == y^2 (mod n).

1, 2, 5, 8, 9, 10, 13, 24, 21, 18, 21, 40, 25, 26, 45, 64, 33, 42, 37, 72, 65, 42, 45, 120, 65, 50, 81, 104, 57, 90, 61, 160, 105, 66, 117, 168, 73, 74, 125, 216, 81, 130, 85, 168, 189, 90, 93, 320, 133, 130, 165, 200, 105, 162, 189, 312, 185, 114, 117, 360, 121, 122, 273

Offset: 1

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

Amiram Eldar, Table of n, a(n) for n = 1..10000
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.

Cf. A086933, A327767, A332794, A344372.

f[2, e_] := e*2^e; f[p_, e_] := ((p-1)*e+p)*p^(e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 10 2020 *)

a(n) is multiplicative and, for an odd prime p, a(p) = 2*p - 1.
Multiplicative with a(2^e)=e*2^e and a(p^e)=((p-1)*e+p)*p^(e-1) for an odd prime p. - Vladeta Jovovic, Sep 22 2003
From Ridouane Oudra, Jun 17 2025: (Start)
a(n) = (-1)^n*gcd(n,2)*Sum_{d|n} (-1)^d*d*phi(n/d).
a(n) = A327767(n)*A332794(n).
a(2*n) = 2*A344372(n).
a(2*n+1) = A332794(2*n+1). (End)

More terms from Vladeta Jovovic, Sep 22 2003

A087687 Number of solutions to x^2 + y^2 + z^2 == 0 (mod n).

Original entry on oeis.org

1, 4, 9, 8, 25, 36, 49, 32, 99, 100, 121, 72, 169, 196, 225, 64, 289, 396, 361, 200, 441, 484, 529, 288, 725, 676, 891, 392, 841, 900, 961, 256, 1089, 1156, 1225, 792, 1369, 1444, 1521, 800, 1681, 1764, 1849, 968, 2475, 2116, 2209, 576, 2695, 2900, 2601

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003

To show that a(n) is multiplicative is simple number theory. If gcd(n,m)=1, then any solution of x^2 + y^2 + z^2 == 0 (mod n) and any solution (mod m) can combined to a solution (mod nm) using the Chinese Remainder Theorem and any solution (mod nm) gives solutions (mod n) and (mod m). Hence a(nm) = a(n)*a(m). - Torleiv Kløve, Jan 26 2009

Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 80 terms from Robert Gerbicz)
C. Calderón and M. J. De Velasco, On divisors of a quadratic form, Boletim da Sociedade Brasileira de Matemática, Vol. 31, No. 1 (2000), pp. 81-91; alternative link.
László Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq., Vol. 17 (2014), Article # 14.11.6; arXiv preprint, arXiv:1404.4214 [math.NT], 2014.
Index to sequences related to sums of squares

Cf. A086933, A062775.

Different from A064549.

A087687 := proc(n)
    a := 1;
    for pe in ifactors(n)[2] do
        p := op(1,pe) ;
        e := op(2,pe) ;
        if p = 2 then
            a := a*p^(e+ceil(e/2)) ;
        elif 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 do:
    a ;
end proc:
seq(A087687(n),n=1..100) ; # R. J. Mathar, Jun 25 2018

a[n_] := Module[{k=1}, Do[{p, e} = pe; k = k*If[p == 2, p^(e + Ceiling[ e/2]), If[OddQ[e], p^((3*e-1)/2)*(p^((e+1)/2) + p^((e-1)/2) - 1), p^(3*e/2 - 1)*(p^(e/2 + 1) + p^(e/2) - 1)]], {pe, FactorInteger[n]}]; k];
Array[a, 100] (* Jean-François Alcover, Jul 10 2018, after R. J. Mathar *)

a(n)=local(v=vector(n),w);for(i=1,n,v[i^2%n+1]++);w=vector(n,i,sum(j=1,n,v[j]*v[(i-j)%n+1]));sum(j=1,n,w[j]*v[(1-j)%n+1]) \\ Martin Fuller

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

a(2^k) = 2^(k + ceiling(k/2)). 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). - Martin Fuller, Jan 26 2009

Sum_{k=1..n} a(k) ~ (4*zeta(3))/(15*zeta(4)) * n^3 + O(n^2 * log(n)) (Calderón and de Velasco, 2000). - Amiram Eldar, Mar 04 2021

More terms from Robert Gerbicz, Aug 22 2006

Edited by Steven Finch, Feb 06 2009, Feb 12 2009

A240547 Number of non-congruent solutions of x^2 + y^2 + z^2 + t^2 == 0 mod n.

Original entry on oeis.org

1, 8, 33, 32, 145, 264, 385, 128, 945, 1160, 1441, 1056, 2353, 3080, 4785, 512, 5185, 7560, 7201, 4640, 12705, 11528, 12673, 4224, 18625, 18824, 26001, 12320, 25201, 38280, 30721, 2048, 47553, 41480, 55825, 30240, 51985, 57608, 77649, 18560, 70561, 101640

Offset: 1

Laszlo Toth, Apr 07 2014

			For n=2 the a(2)=8 solutions are (0,0,0,0), (1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1), (1,1,1,1).

David A. Corneth, Table of n, a(n) for n = 1..10000
László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint 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. A020478, A069097, A086933, A087687, A208895, A229179.

A240547 := proc(n) local a, x, y, z, t ; a := 0 ; for x from 0 to n-1 do for y
from 0 to n-1 do for z from 0 to n-1 do for t from 0 to n-1 do if
(x^2+y^2+z^2+t^2) mod n = 0 mod n then a := a+1 ; fi; od; od ; od; od;
a ; end proc;
# alternative
A240547 := proc(n)
    a := 1;
    for pe in ifactors(n)[2] do
        p := op(1,pe) ;
        e := op(2,pe) ;
        if p = 2 then
            a := a*p^(2*e+1) ;
        else
            a := a* p^(2*e-1)*(p^(e+1)+p^e-1) ;
        end if;
    end do:
    a ;
end proc:
seq(A240547(n),n=1..100) ; # R. J. Mathar, Jun 25 2018

b[2, e_] := 2^(2 e + 1);
b[p_, e_] := p^(2 e - 1)*(p^(e + 1) + p^e - 1);
a[n_] := Times @@ b @@@ FactorInteger[n];
Array[a, 42] (* Jean-François Alcover, Dec 05 2017 *)

a(n) = my(m); if( n<1, 0, forvec( v = vector(4, i, [0, n-1]), m += (0 == norml2(v)%n))); m /* Michael Somos, Apr 07 2014 */

a(n) = {my(f = factor(n), res = 1, start = 1, p, e, i); if(n % 2 == 0, res = 1<<(f[1,2]<<1+1); start = 2); for(i = start, #f~, p = f[i, 1]; e = f[i, 2]; res*=(p^(e<<1-1)*(p^(e+1)+p^e-1))); res} \\ David A. Corneth, Jul 22 2018

Multiplicative, with a(2^e) = 2^(2e+1) for e>=1, a(p^e) = p^(2e-1)*(p^(e+1)+p^e-1) for p > 2, e>=1.
For odd n, a(n) = A069097(n)*n = A020478(n). - R. J. Mathar, Jun 23 2018
Sum_{k=1..n} a(k) ~ c * n^4 + O(n^3 * log(n)), where c = 5*Pi^2/(168*zeta(3)) = 0.244362... (Tóth, 2014). - Amiram Eldar, Oct 18 2022

A229296 Number of solutions to x^2 + y^2 == n (mod 2n) for x,y in [0, 2n).

Original entry on oeis.org

2, 4, 2, 8, 18, 4, 2, 16, 18, 36, 2, 8, 50, 4, 18, 32, 66, 36, 2, 72, 2, 4, 2, 16, 130, 100, 18, 8, 114, 36, 2, 64, 2, 132, 18, 72, 146, 4, 50, 144, 162, 4, 2, 8, 162, 4, 2, 32, 98, 260, 66, 200, 210, 36, 18, 16, 2, 228, 2, 72, 242, 4, 18, 128, 450, 4, 2

Offset: 1

José María Grau Ribas, Sep 22 2013

nonn

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

Cf. A086933, A229294, A229295, A229296, A229297.

A[n_] := Sum[If[Mod[a^2+b^2, 2n] == n, 1, 0], {a, 0, 2n - 1}, {b, 0, 2n - 1}]; Array[A, 100]

a(n)={my(m=2*n); my(p=Mod(sum(i=0, m-1, x^(i^2%m)), x^m-1)^2); polcoeff( lift(p), n)} \\ Andrew Howroyd, Aug 07 2018

a(n) = 2*A086933(n). - Andrew Howroyd, Aug 07 2018

A087561 Number of solutions to x^2 + 2y^2 == 0 (mod n).

Original entry on oeis.org

1, 2, 5, 4, 1, 10, 1, 8, 21, 2, 21, 20, 1, 2, 5, 16, 33, 42, 37, 4, 5, 42, 1, 40, 25, 2, 81, 4, 1, 10, 1, 32, 105, 66, 1, 84, 1, 74, 5, 8, 81, 10, 85, 84, 21, 2, 1, 80, 49, 50, 165, 4, 1, 162, 21, 8, 185, 2, 117, 20, 1, 2, 21, 64, 1, 210, 133, 132, 5, 2, 1, 168, 145, 2, 125, 148, 21

Offset: 1

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

Andrew Howroyd, Table of n, a(n) for n = 1..10000
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A086933, A088964, A088965, A089002, A309710.

a[n_] := If[n == 1, 1, Product[{p, e} = pe; Which[p == 2, 2^e, Abs[Mod[p, 8] - 2] != 1, (p^2)^Quotient[e, 2], True, (p + e (p-1)) p^(e-1)], {pe, FactorInteger[n]}]];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 20 2019, from PARI *)

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

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i, 1], e=f[i, 2]); if(p==2, 2^e, if(abs(p%8-2)<>1, (p^2)^(e\2), (p+e*(p-1))*p^(e-1))))} \\ Andrew Howroyd, Jul 16 2018

Multiplicative with a(2^e) = 2^e, a(p^e) = p^(2*floor(e/2)) for p - 2 == +-3 (mod 8), a(p^e) = ((p-1)*e+p)*p^(e-1) for p - 2 == +-1 (mod 8). - Andrew Howroyd, Jul 16 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi/(4*sqrt(2)*A309710) = 0.521595326207... . - Amiram Eldar, Nov 21 2023

More terms from David Wasserman, Jun 07 2005

A305191 Table read by rows: T(n,k) is the number of pairs (x,y) mod n such that x^2 + y^2 == k (mod n), for k from 0 to n-1.

Original entry on oeis.org

1, 2, 2, 1, 4, 4, 4, 8, 4, 0, 9, 4, 4, 4, 4, 2, 8, 8, 2, 8, 8, 1, 8, 8, 8, 8, 8, 8, 8, 16, 16, 0, 8, 16, 0, 0, 9, 12, 12, 0, 12, 12, 0, 12, 12, 18, 8, 8, 8, 8, 18, 8, 8, 8, 8, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 32, 16, 0, 16, 32, 4, 0, 16, 8, 16, 0, 25, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12

Offset: 1

Jack Zhang, May 27 2018

			Table begins:
  1;
  2,  2;
  1,  4,  4;
  4,  8,  4,  0;
  9,  4,  4,  4,  4;
  2,  8,  8,  2,  8,  8;
  1,  8,  8,  8,  8,  8,  8;
  8, 16, 16,  0,  8, 16,  0,  0;
  9, 12, 12,  0, 12, 12,  0, 12, 12;
E.g., for n = 4:
4 pairs satisfy x^2 + y^2 = 4k: (0, 0), (0, 2), (2, 0), (2, 2)
8 pairs satisfy x^2 + y^2 = 4k+1: (0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3), (3, 0), (3, 2)
4 pairs satisfy x^2 + y^2 = 4k+2: (1, 1), (1, 3), (3, 1), (3, 3)
0 pairs satisfy x^2 + y^2 = 4k+3

Jianing Song, Table of n, a(n) for n = 1..5050 (first 100 rows)

Cf. A155918 (number of nonzeros in row n).

Cf. A086933 (1st column), A060968 (2nd column), A086932 (right diagonal).

row(n) = {v = vector(n); for (x=0, n-1, for (y=0, n-1, k = (x^2 + y^2) % n; v[k+1]++;);); v;} \\ Michel Marcus, Jun 08 2018

T(n,k)=
{
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2], b=valuation(k,p));
        if(p==2, r*=if(b>=e-1, 2^e, if((k/2^b)%4==1, 2^(e+1), 0)));
        if(p%4==1, r*=if(b>=e, ((p-1)*e+p)*p^(e-1), (b+1)*(p-1)*p^(e-1)));
        if(p%4==3, r*=if(b>=e, p^(e-(e%2)), if(b%2, 0, (p+1)*p^(e-1))));
    );
    return(r);
}
tabl(nn) = for(n=1, nn, for(k=0, n-1, print1(T(n, k), ", ")); print()) \\ Jianing Song, Apr 20 2019

[[len([(x, y) for x in range(n) for y in range(n) if (pow(x,2,n)+pow(y,2,n))%n==d]) for d in range(n)] for n in range(1,10)]

T(n,k) is multiplicative with respect to n, that is, if gcd(n,m)=1 then T(n*m,k) = T(n,k mod n)*T(m,k mod m).
T(n,0) = A086933(n). Let n = p^e and k = r*p^b (0 <= b < e, gcd(r,p) = 1, 0 < k < n). For p == 1 (mod 4), T(n,k) = (b+1)*(p-1)*p^(e-1). For p == 3 (mod 4), T(n,k) = (p+1)*p^(e-1) if b even; 0 if b odd. For p = 2, T(n,k) = 2^e if k = 2^(e-1); 2^(e+1) if b <= e-2 and r == 1 (mod 4); 0 if r == 3 (mod 4). [Corrected by Jianing Song, Apr 20 2019]
If p is an odd prime then T(p,k) = p - (-1)^(p-1)/2 if k > 0, otherwise p + (p-1)*(-1)^(p-1)/2.

Offset corrected by Jianing Song, Apr 20 2019

cp's OEIS Frontend

A062803 Number of solutions to x^2 == y^2 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A087687 Number of solutions to x^2 + y^2 + z^2 == 0 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A240547 Number of non-congruent solutions of x^2 + y^2 + z^2 + t^2 == 0 mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A229296 Number of solutions to x^2 + y^2 == n (mod 2*n) for x,y in [0, 2*n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A087561 Number of solutions to x^2 + 2y^2 == 0 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A305191 Table read by rows: T(n,k) is the number of pairs (x,y) mod n such that x^2 + y^2 == k (mod n), for k from 0 to n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Python

Formula

Extensions

A229296 Number of solutions to x^2 + y^2 == n (mod 2n) for x,y in [0, 2n).