A373355 - OEIS

%I #16 Oct 08 2024 07:27:21

%S 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,

%T 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,

%U 1,2,3,1,1,2,3,1,3,3,1,1,1,1,2,0,1,0,3,1,1,1,1

%N 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.

%H Carl Friedrich Gauss, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=PPN373456743%7CLOG_0008">Vierter Abschnitt. Von den Congruenzen zweiten Grades. Quadratische Reste und Nichtreste. Art. 97</a>, in "Untersuchungen über die höhere Arithmetik", Hrsg. H. Maser, Verlag von Julius Springer, Berlin, 1889.

%F 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:

%F   [n | k] := 0 if (n N k) and (k N n);

%F   [n | k] := 1 if (n R k) and (k R n);

%F   [n | k] := 2 if (n R k) and (k N n);

%F   [n | k] := 3 if (n N k) and (k R n).

%F We write [n || k] for [prime(n) | prime(k)] and set T(n, k) = [n - k + 1 || k].

%F Exchanging 2 <-> 3 reverses the rows.

%e Triangle starts:

%e   [ 1] 1;

%e   [ 2] 2, 3;

%e   [ 3] 2, 1, 3;

%e   [ 4] 1, 0, 0, 1;

%e   [ 5] 2, 2, 1, 3, 3;

%e   [ 6] 2, 3, 0, 0, 2, 3;

%e   [ 7] 1, 1, 1, 1, 1, 1, 1;

%e   [ 8] 2, 0, 0, 2, 3, 0, 0, 3;

%e   [ 9] 1, 2, 0, 0, 1, 0, 0, 3, 1;

%e   [10] 2, 3, 1, 0, 0, 0, 0, 1, 2, 3;

%e   [11] 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1;

%e   [12] 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3;

%p QRP := proc(n, k) local QR, p, q, a, b;

%p    QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n);

%p    p := ithprime(n); q := ithprime(k);

%p    a := QR(p, q); b := QR(q, p);

%p    if a = -1 and b = -1 then return 0 fi;

%p    if a =  1 and b =  1 then return 1 fi;

%p    if a =  1 and b = -1 then return 2 fi;

%p    if a = -1 and b =  1 then return 3 fi;

%p end: for n from 1 to 12 do lprint([n], seq(QRP(n-k+1, k), k = 1..n)) od;

%t QR[n_, k_] := Module[{x, y}, If[Reduce[x^2 == n + k*y, {x, y}, Integers] =!= False, 1, -1]];

%t QRS[n_, k_] := Module[{p = Prime[n], q = Prime[k], a, b}, a = QR[p, q]; b = QR[q, p]; Which[

%t       a == -1 && b == -1, 0,

%t       a == 1 && b == 1, 1,

%t       a == 1 && b == -1, 2,

%t       a == -1 && b == 1, 3]];

%t Table[QRS[n - k + 1, k], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Oct 08 2024, after Maple program *)

%o (Python)

%o from sympy.ntheory import is_quad_residue, prime

%o def QR(n, k): return is_quad_residue(n, k)

%o def QRS(n, k):

%o     p = prime(n); q = prime(k)

%o     a = QR(p, q); b = QR(q, p)

%o     if not a and not b: return 0

%o     if a and b: return 1

%o     if a and not b: return 2

%o     if not a and b: return 3

%o def T(n, k): return QRS(n - k + 1, k)

%o for n in range(1, 13): print([n], [T(n, k) for k in range(1, n + 1)])

%Y Cf. A063987, A373223.

%K nonn,tabl

%O 1,2

%A _Peter Luschny_, Jun 02 2024