A264083 -id:A264083 - cp's OEIS frontend

A087784 Number of solutions to x^2 + y^2 + z^2 = 1 mod n.

1, 4, 6, 24, 30, 24, 42, 96, 54, 120, 110, 144, 182, 168, 180, 384, 306, 216, 342, 720, 252, 440, 506, 576, 750, 728, 486, 1008, 870, 720, 930, 1536, 660, 1224, 1260, 1296, 1406, 1368, 1092, 2880, 1722, 1008, 1806, 2640, 1620, 2024, 2162, 2304, 2058, 3000

Offset: 1

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

Michael De Vlieger, 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, Journal of Integer Sequences, 17 (2014), Article 14.11.6.

Cf. A006752, A060968, A087687, A208895, A264083.

Table[With[{f = FactorInteger[n][[All, 1]]}, Apply[Times, Map[1 + 1/# &, Select[f, Mod[#, 4] == 1 &]]] Apply[Times, Map[1 - 1/# &, Select[f, Mod[#, 4] == 3 &]]] (1 + Boole[Divisible[n, 4]]/2) n^2] - Boole[n == 1], {n, 50}] (* Michael De Vlieger, Feb 15 2018 *)

a(n) = {my(f=factor(n)); if ((n % 4), 1, 3/2)*n^2*prod(k=1, #f~, p = f[k,1]; m = p % 4; if (m==1, 1+1/p, if (m==3, 1-1/p, 1)));} \\ Michel Marcus, Feb 14 2018

a(n) = n^2 * (3/2 if 4|n) * Product_{primes p == 1 mod 4 dividing n} (1+1/p) * Product_{primes p == 3 mod 4 dividing n} (1-1/p). - Bjorn Poonen, Dec 09 2003

Sum_{k=1..n} a(k) ~ c * n^3 + O(n^2 * log(n)), where c = 36*G/Pi^4 = 0.338518..., where G is Catalan's constant (A006752) (Tóth, 2014). - Amiram Eldar, Oct 18 2022

More terms from David Wasserman, Jun 17 2005

A071302 a(n) = (1/2) * (number of n X n 0..2 matrices M with MM' mod 3 = I, where M' is the transpose of M and I is the n X n identity matrix).

Original entry on oeis.org

1, 4, 24, 576, 51840, 13063680, 9170703360, 19808719257600, 131569513308979200, 2600339861038664908800, 152915585868239728626892800, 27051378802435080953011843891200, 14395932257291877030764312963579904000

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

Also, number of n X n orthogonal matrices over GF(3) with determinant 1. - Max Alekseyev, Nov 06 2022

			From _Petros Hadjicostas_, Dec 17 2019: (Start)
For n = 2, the 2*a(2) = 8 n X n matrices M with elements in {0, 1, 2} that satisfy MM' mod 3 = I are the following:
(a) With 1 = det(M) mod 3:
[[1,0],[0,1]];  [[0,1],[2,0]]; [[0,2],[1,0]]; [[2,0],[0,2]].
This is the abelian group SO(2, Z_3). See the comments for sequence A060968.
(b) With 2 = det(M) mod 3:
[[0,1],[1,0]];  [[0,2],[2,0]]; [[1,0],[0,2]]; [[2,0],[0,1]].
Note that, for n = 3, we have 2*a(3) = 2*24 = 48 = A264083(3). (End)

Jianing Song, Structure of the group SO(2,Z_n).
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), #14.11.6.
Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

Cf. A003053, A003920, A060968, A071303, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609.

FoldList[Times, 1, LinearRecurrence[{3, -3, 9}, {4, 6, 24}, 12]] (* Amiram Eldar, Jun 22 2025 *)

{ a071302(n) = my(t=n\2); prod(i=0,t-1,3^(2*t)-3^(2*i)) * if(n%2,3^t,1/(3^t+(-1)^t)); } \\ Max Alekseyev, Nov 06 2022

a(2k+1) = 3^k * Product_{i=0..k-1} (3^(2k) - 3^(2i)); a(2k) = (3^k + (-1)^(k+1)) * Product_{i=1..k-1} (3^(2k) - 3^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

a(n+1) = a(n) * A318609(n+1) for n >= 1. - conjectured by Petros Hadjicostas, Dec 18 2019; proved based on the explicit formula by Max Alekseyev, Nov 06 2022

Terms a(8) onward from Max Alekseyev, Nov 06 2022

A071303 1/2 times the number of n X n 0..3 matrices M with MM' mod 4 = I, where M' is the transpose of M and I is the n X n identity matrix.

Original entry on oeis.org

1, 8, 192, 12288, 1966080, 1509949440, 5411658792960

Offset: 1

R. H. Hardin, Jun 11 2002

It seems that a(n) = n! * 2^(binomial(n+1,2) - 1) for n = 1, 2, 3, 4, 5, while for n = 6, a(n) is twice this number. The number n! * 2^(binomial(n+1,2) - 1) appears in Proposition 6.1 in Eriksson and Linusson (2000) as an upper bound to the number of three-dimensional permutation arrays of size n (see column k = 3 of A330490). - Petros Hadjicostas, Dec 16 2019

a(7) = 7! * 2^30. - Sean A. Irvine, Jul 11 2024

			From _Petros Hadjicostas_, Dec 16 2019: (Start)
For n = 2, here are the 2*a(2) = 16 2 x 2 matrices M with elements in {0,1,2,3} that satisfy MM'  mod 4 = I:
(a) With 1 = det(M) mod 4:
  [[1,0],[0,1]]; [[0,1],[3,0]]; [[0,3],[1,0]]; [[1,2],[2,1]];
  [[2,1],[3,2]]; [[2,3],[1,2]]; [[3,0],[0,3]]; [[3,2],[2,3]].
These form the abelian group SO(2, Z_n). See the comments for sequence A060968.
(b) With 3 = det(M) mod 4:
  [[0,1],[1,0]]; [[0,3],[3,0]]; [[1,0],[0,3]];  [[1,2],[2,3]];
  [[2,1],[1,2]]; [[2,3],[3,2]]; [[3,0],[0,1]];  [[3,2],[2,1]].
Note that, for n = 3, we have 2*a(3) = 2*192 = 384 = A264083(4). (End)

Kimmo Eriksson and Svante Linusson, A combinatorial theory of higher-dimensional permutation arrays, Adv. Appl. Math. 25(2) (2000a), 194-211; see Proposition 6.1 (p. 210).
Sean A. Irvinne, Java program (github)
Jianing Song, Structure of the group SO(2,Z_n).
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), #14.11.6.

Cf. A003920, A060968, A071302, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A229136, A264083, A330490.

a(7) from Sean A. Irvine, Jul 11 2024

A071304 a(n) = (1/2) * (number of n X n 0..4 matrices M with MM' mod 5 = I, where M' is the transpose of M and I is the n X n identity matrix).

Original entry on oeis.org

1, 4, 120, 14400, 9360000, 29016000000, 457002000000000, 35646156000000000000, 13946558535000000000000000, 27230655539587500000000000000000, 266009466302345390625000000000000000000, 12987912192212013697265625000000000000000000000

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

Also, number of n X n orthogonal matrices over GF(5) with determinant 1. - Max Alekseyev, Nov 06 2022

			From _Petros Hadjicostas_, Dec 17 2019: (Start)
For n = 2, the 2*a(2) = 8 n X n matrices M with elements in {0,1,2,3,4} that satisfy MM' mod 5 = I are the following:
(a) those with 1 = det(M) mod 5:
[[1,0],[0,1]]; [[0,4],[1,0]]; [[0,1],[4,0]]; [[4,0],[0,4]].
These form the abelian group SO(2, Z_5). See the comments for sequence A060968.
(b) those with 4 = det(M) mod 5:
[[0,1],[1,0]]; [[0,4],[4,0]]; [[1,0],[0,4]]; [[4,0],[0,1]].
Note that, for n = 3, we have 2*a(3) = 2*120 = 240 = A264083(5). (End)

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.
Jianing Song, Structure of the group SO(2,Z_n).

Cf. A060968, A071302, A071303, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609, A330607.

{ a071304(n) = my(t=n\2); prod(i=0, t-1, 5^(2*t)-5^(2*i)) * if(n%2, 5^t, 1/(5^t+1)); } \\ Max Alekseyev, Nov 06 2022

a(2k+1) = 5^k * Product_{i=0..k-1} (5^(2k) - 5^(2i)); a(2k) = (5^k - 1) * Product_{i=1..k-1} (5^(2k) - 5^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022
From Petros Hadjicostas, Dec 20 2019: (Start)
Let b(n) be the number of solutions to the equation Sum_{i = 1..n} x_i^2 = 1 (mod 5) with x_i in 0..4. We have that b(n) = 5*b(n-1) + 5*b(n-2) - 25*b(n-3) for n >= 3 with b(0) = 0, b(1) = 2, and b(2) = 4.
We have b(n) = A330607(n, k=1) for n >= 0.
We conjecture that a(n+1) = a(n)*b(n+1) for n >= 1. (End)

Terms a(7) onward from Max Alekseyev, Nov 06 2022

A071306 a(n) = (1/2) * (number of n X n 0..6 matrices M with MM' mod 7 = I, where M' is the transpose of M and I is the n X n identity matrix).

Original entry on oeis.org

1, 8, 336, 112896, 276595200, 4662288691200, 546914437209907200, 450219964711195607040000, 2596509480922336727312302080000, 104784757384177668346109081238896640000, 29597339316082819652234687848790174733434880000

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

Also, number of n X n orthogonal matrices over GF(7) with determinant 1. - Max Alekseyev, Nov 06 2022

			From _Petros Hadjicostas_, Dec 19 2019: (Start)
For n = 2, the 2*a(2) = 16 n X n matrices M with elements in 0..6 that satisfy MM' = I are the following:
(a) those with 1 = det(M) mod 7:
[[1,0],[0,1]]; [[0,1],[6,0]]; [[0,6],[1,0]]; [[2,2],[5,2]];
[[2,5],[2,2]]; [[5,2],[5,5]]; [[5,5],[2,5]]; [[6,0],[0,6]].
These are the elements of the abelian group SO(2,Z_7). See the comments for sequence A060968.
(b) those with 6 = det(M) mod 7:
[[0,1],[1,0]]; [[0,6],[6,0]]; [[1,0],[0,6]]; [[2,2],[2,5]];
[[2,5],[5,5]]; [[5,2],[2,2]]; [[5,5],[5,2]]; [[6,0],[0,1]].
Note that, for n = 3, we have 2*a(3) = 2*336 = 672 = A264083(7). (End)

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

Cf. A060968, A071302, A071303, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609.

{ a071306(n) = my(t=n\2); prod(i=0, t-1, 7^(2*t)-7^(2*i)) * if(n%2, 7^t, 1/(7^t+(-1)^t)); } \\ Max Alekseyev, Nov 06 2022

a(2k+1) = 7^k * Product_{i=0..k-1} (7^(2k) - 7^(2i)); a(2k) = (7^k + (-1)^(k+1)) * Product_{i=1..k-1} (7^(2k) - 7^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

Conjecture: Let b(n) be the number of solutions to the equation Sum_{i = 1..n} x_i^2 = 1 (mod 7) with x_i in 0..6. We conjecture that b(n) = 7*b(n-1) - 7*b(n-2) + 49*b(n-3) for n >= 4 with b(1) = 2, b(2) = 8, and b(3) = 42. We also conjecture that a(n+1) = a(n)*b(n+1) for n >= 1. - Petros Hadjicostas, Dec 19 2019

Terms a(6) onward from Max Alekseyev, Nov 06 2022

A071900 1/4 times the number of n X n 0..7 matrices with MM' mod 8 = I, where M' is the transpose of M and I is the n X n identity matrix.

Original entry on oeis.org

1, 16, 1536, 786432, 2013265920

Offset: 1

R. H. Hardin, Jun 12 2002

			From _Petros Hadjicostas_, Dec 18 2019: (Start)
For n = 2, the 4*a(2) = 64 n X n matrices M with elements in 0..7 that satisfy MM' mod 8 = I can be classified into four categories:
(a) Matrices M with 1 = det(M) mod 8. These form the abelian group SO(2, Z_8). See the comments for sequence A060968.
(b) Matrices M with 3 = det(M) mod 8. These are the elements of the left coset A*SO(2, Z_8) = {AM: M in SO(2, Z_8)}, where A = [[3,0],[0,1]].
(c) Matrices M with 5 = det(M) mod 8. These are the elements of the left coset B*SO(2, Z_8) = {BM: M in SO(2, Z_8)}, where B = [[5,0],[0,1]].
(d) Matrices M with 7 = det(M) mod 8. These are the elements of the left coset C*SO(2, Z_8) = {CM: M in SO(2, Z_8)}, where C= [[7,0],[0,1]].
All four classes of matrices have the same number of elements, that is, 16 each.
Note that for n = 3 we have 4*a(3) = 4*1536 = 6144 = A264083(8). (End)

Jianing Song, Structure of the group SO(2,Z_n).
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), #14.11.6.

Cf. A060968, A071302, A071303, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083.

Conjecture: a(n) = 2^(n*(n-1)/2) * A071303(n) for n >= 1. - Michel Marcus, Nov 08 2022

cp's OEIS Frontend

A087784 Number of solutions to x^2 + y^2 + z^2 = 1 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A071302 a(n) = (1/2) * (number of n X n 0..2 matrices M with MM' mod 3 = I, where M' is the transpose of M and I is the n X n identity matrix).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A071303 1/2 times the number of n X n 0..3 matrices M with MM' mod 4 = I, where M' is the transpose of M and I is the n X n identity matrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A071304 a(n) = (1/2) * (number of n X n 0..4 matrices M with MM' mod 5 = I, where M' is the transpose of M and I is the n X n identity matrix).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A071306 a(n) = (1/2) * (number of n X n 0..6 matrices M with MM' mod 7 = I, where M' is the transpose of M and I is the n X n identity matrix).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A071900 1/4 times the number of n X n 0..7 matrices with MM' mod 8 = I, where M' is the transpose of M and I is the n X n identity matrix.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula