OFFSET
1,8
LINKS
Carl Friedrich Gauss, Vierter Abschnitt. Von den Congruenzen zweiten Grades. Quadratische Reste und Nichtreste. Art. 97, in "Untersuchungen über die höhere Arithmetik", Hrsg. H. Maser, Verlag von Julius Springer, Berlin, 1889.
FORMULA
Let two positive numbers n, k be given. We write (n R k) if two integers x and y exist, such that x^2 = n + k*y, and (n N k) otherwise. If the condition is satisfied n is called a quadratic residue modulo k. We distinguish four cases:
[n | k] := 0 if (n N k) and (k N n);
[n | k] := 1 if (n R k) and (k R n);
[n | k] := 2 if (n R k) and (k N n);
[n | k] := 3 if (n N k) and (k R n).
We set T(n, k) = [n - k + 1 | k].
Exchanging 2 <-> 3 reverses the rows.
All terms of row n are 1 <==> n = 1, 2 or n is of the form k*(k-2), k >= 3.
EXAMPLE
Triangle starts:
[ 1] 1;
[ 2] 1, 1;
[ 3] 1, 1, 1;
[ 4] 1, 2, 3, 1;
[ 5] 1, 2, 1, 3, 1;
[ 6] 1, 2, 2, 3, 3, 1;
[ 7] 1, 2, 0, 1, 0, 3, 1;
[ 8] 1, 1, 1, 1, 1, 1, 1, 1;
[ 9] 1, 2, 2, 3, 1, 2, 3, 3, 1;
[10] 1, 2, 0, 3, 2, 3, 2, 0, 3, 1;
[11] 1, 2, 2, 1, 0, 1, 0, 1, 3, 3, 1;
[12] 1, 2, 2, 1, 0, 2, 3, 0, 1, 3, 3, 1;
MAPLE
QRS := proc(n, k) local QR, p, q, a, b;
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n);
a := QR(n, k); b := QR(k, n);
if a = -1 and b = -1 then return 0 fi;
if a = 1 and b = 1 then return 1 fi;
if a = 1 and b = -1 then return 2 fi;
if a = -1 and b = 1 then return 3 fi;
end: for n from 1 to 12 do lprint([n], seq(QRS(n-k+1, k), k = 1..n)) od;
MATHEMATICA
QR[n_, k_] := Module[{x, y}, If[Reduce[x^2 == n + k*y, {x, y}, Integers] =!= False, 1, -1]];
QRS[n_, k_] := With[{a = QR[n, k], b = QR[k, n]}, Which[
a == -1 && b == -1, 0,
a == 1 && b == 1, 1,
a == 1 && b == -1, 2,
a == -1 && b == 1, 3]];
Table[QRS[n - k + 1, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 08 2024 *)
PROG
(Python)
from sympy.ntheory import is_quad_residue
def QR(n, k): return is_quad_residue(n, k)
def QRS(n, k):
a = QR(n, k); b = QR(k, n)
if not a and not b: return 0
if a and b: return 1
if a and not b: return 2
if not a and b: return 3
def T(n, k): return QRS(n - k + 1, k)
for n in range(1, 13): print([n], [T(n, k) for k in range(1, n + 1)])
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jun 02 2024
STATUS
approved