A373355 Triangle read by rows: T(n, k) = [n - k + 1 || k] where [n || k] is defined below. Ways in which two primes can relate to each other modulo quadratic residue.

1, 2, 3, 2, 1, 3, 1, 0, 0, 1, 2, 2, 1, 3, 3, 2, 3, 0, 0, 2, 3, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 2, 3, 0, 0, 3, 1, 2, 0, 0, 1, 0, 0, 3, 1, 2, 3, 1, 0, 0, 0, 0, 1, 2, 3, 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1, 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3, 1, 1, 1, 1, 2, 0, 1, 0, 3, 1, 1, 1, 1

Offset

1,2

Links

Table of n, a(n) for n=1..91.

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 write [n || k] for [prime(n) | prime(k)] and set T(n, k) = [n - k + 1 || k].

Exchanging 2 <-> 3 reverses the rows.

Example

Triangle starts:
  [ 1] 1;
  [ 2] 2, 3;
  [ 3] 2, 1, 3;
  [ 4] 1, 0, 0, 1;
  [ 5] 2, 2, 1, 3, 3;
  [ 6] 2, 3, 0, 0, 2, 3;
  [ 7] 1, 1, 1, 1, 1, 1, 1;
  [ 8] 2, 0, 0, 2, 3, 0, 0, 3;
  [ 9] 1, 2, 0, 0, 1, 0, 0, 3, 1;
  [10] 2, 3, 1, 0, 0, 0, 0, 1, 2, 3;
  [11] 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1;
  [12] 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3;

Maple

QRP := proc(n, k) local QR, p, q, a, b;
   QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n);
   p := ithprime(n); q := ithprime(k);
   a := QR(p, q); b := QR(q, p);
   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(QRP(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_] := Module[{p = Prime[n], q = Prime[k], a, b}, a = QR[p, q]; b = QR[q, p]; 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, after Maple program *)

Prog

(Python)
from sympy.ntheory import is_quad_residue, prime
def QR(n, k): return is_quad_residue(n, k)
def QRS(n, k):
    p = prime(n); q = prime(k)
    a = QR(p, q); b = QR(q, p)
    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. A063987, A373223.

Sequence in context: A134819 A135267 A242406 * A270469 A395438 A204933

Adjacent sequences: A373352 A373353 A373354 * A373356 A373357 A373358

Keyword

nonn,tabl

Author

Peter Luschny, Jun 02 2024

Status

approved