A373354 Triangle read by rows: T(n, k) = [n - k + 1 | k] where [n | k] is defined below.
1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 2, 1, 3, 1, 1, 2, 2, 3, 3, 1, 1, 2, 0, 1, 0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 0, 3, 2, 3, 2, 0, 3, 1, 1, 2, 2, 1, 0, 1, 0, 1, 3, 3, 1, 1, 2, 2, 1, 0, 2, 3, 0, 1, 3, 3, 1, 1, 2, 3, 3, 2, 0, 1, 0, 3, 2, 2, 3, 1
Offset: 1
Examples
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;
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.
Programs
-
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 *) -
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)])
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.