login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A373354
Triangle read by rows: T(n, k) = [n - k + 1 | k] where [n | k] is defined below.
0
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,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
Cf. A373223, A373355 (restricted to primes).
Sequence in context: A372571 A191770 A120966 * A189041 A055444 A102383
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jun 02 2024
STATUS
approved