A086932 -id:A086932 - cp's OEIS frontend

A089002 Number of non-congruent solutions to x^2 + 2y^2 == -1 (mod n).

1, 2, 2, 4, 6, 4, 8, 0, 6, 12, 10, 8, 14, 16, 12, 0, 16, 12, 18, 24, 16, 20, 24, 0, 30, 28, 18, 32, 30, 24, 32, 0, 20, 32, 48, 24, 38, 36, 28, 0, 40, 32, 42, 40, 36, 48, 48, 0, 56, 60, 32, 56, 54, 36, 60, 0, 36, 60, 58, 48, 62, 64, 48, 0, 84, 40, 66, 64, 48, 96

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 02 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. A088965, A086932, A309710.

f[2, e_] := If[e < 3, 2^e, 0]; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p - 2, 8]], (p - 1), (p + 1)] * p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 2020 *)

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[(-1-2*i)%n + 1])} \\ Andrew Howroyd, Jul 09 2018

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

Multiplicative with a(2^e) = 2^e for e <= 2, a(2^e) = 0 for e > 2, a(p^e) = (p-1)*p^(e-1) for p-2 mod 8 = +-1, a(p^e) = (p+1)*p^(e-1) for p-2 mod 8 = +-3. - Andrew Howroyd, Jul 15 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = 7/(16*A309710) = 0.410900684788977656... . - Amiram Eldar, Nov 21 2023

A229179 Number of solutions of x^2 + y^2 + z^2 == -1 (mod n) with x, y, and z in 0..n-1.

Original entry on oeis.org

1, 4, 12, 8, 30, 48, 56, 0, 108, 120, 132, 96, 182, 224, 360, 0, 306, 432, 380, 240, 672, 528, 552, 0, 750, 728, 972, 448, 870, 1440, 992, 0, 1584, 1224, 1680, 864, 1406, 1520, 2184, 0, 1722, 2688, 1892, 1056, 3240, 2208, 2256, 0, 2744, 3000, 3672, 1456

Offset: 1

José María Grau Ribas, Sep 29 2013

			As 60 = 4 * 3 * 5, a(60) = a(4) * a(3) * a(5) = 8 * (3 * (3 + 1)) * (5 * (5 + 1)) = 8 * 12 * 30 = 2880. - _David A. Corneth_, Jun 24 2018

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

Cf. A086932, A229180.

Table[Sum[ If[Mod[a^2 + b^2 + c^2 + 1, n] == 0, 1, 0], {c, 0, n - 1}, {b, 0,  n - 1}, {a, 0, n - 1}], {n, 14}]
f[p_, e_] := If[p == 2, Which[e == 1, 4, e == 2, 8, e > 2, 0], (p + 1)*p^(2*e - 1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Oct 18 2022 *)

a(n)={my(p=Mod(sum(i=0, n-1, x^(i^2 % n)), x^n-1)); polcoeff(lift(p^3), n-1)} \\ Andrew Howroyd, Jun 24 2018

first(n) = {my(res = vector(n)); forstep(i = 1, n, 2, f = factor(i); res[i] = 1; for(j = 1, #f~, res[i] *= f[j, 1] * (f[j, 1] + 1) * f[j, 1] ^ ((f[j, 2] - 1) << 1)); res); for(k = 1, 2, forstep(i = 1, n >> k, 2, res[i << k] = res[i] << (k+1))); res} \\ David A. Corneth, Jun 24 2018

a(8 * n) = 0; for odd prime p, a(p^k) = p^(2 * k - 1) * (p + 1); a(2) = 4, a(4) = 8. - David A. Corneth, Jun 24 2018

Sum_{k=1..n} a(k) ~ c * n^3, where c = 13/(4*Pi^2) = 0.329293... . - Amiram Eldar, Oct 18 2022

A227553 Number of solutions to x^2 - y^2 - z^2 == 1 (mod n).

Original entry on oeis.org

1, 4, 6, 8, 30, 24, 42, 32, 54, 120, 110, 48, 182, 168, 180, 128, 306, 216, 342, 240, 252, 440, 506, 192, 750, 728, 486, 336, 870, 720, 930, 512, 660, 1224, 1260, 432, 1406, 1368, 1092, 960, 1722, 1008, 1806, 880, 1620, 2024, 2162, 768, 2058, 3000, 1836

Offset: 1

José María Grau Ribas, Jul 16 2013

Conjecture: a(2) = 4; if s > 1 then a(2^s) = 2^(2s-1); if p == 1 (mod 4) then a(p^s) = (p+1)*p^(2s-1); if p == 3 (mod 4) then a(p^s) = (p-1)*p^(2s-1).

Andrew Howroyd, Table of n, a(n) for n = 1..2500
L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.

Cf. A208895, A086932, A089003, A060968, A087784.

a[1] = 1; a[n_] := Sum[If[Mod[a^2-b^2-c^2, n] == 1, 1, 0], {a, n}, {b, n}, {c, n}]; Table[a[n], {n, 10}]

M(n,f)={sum(i=0, n-1, Mod(x^(f(i)%n), x^n-1))}
a(n)={polcoeff(lift(M(n, i->i^2) * M(n, i->-(i^2))^2 ), 1%n)} \\ Andrew Howroyd, Jun 24 2018

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

A089002 Number of non-congruent solutions to x^2 + 2y^2 == -1 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A229179 Number of solutions of x^2 + y^2 + z^2 == -1 (mod n) with x, y, and z in 0..n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A227553 Number of solutions to x^2 - y^2 - z^2 == 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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