cp's OEIS Frontend

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.

%I A373355 #16 Oct 08 2024 07:27:21
%S A373355 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 A373355 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 A373355 1,2,3,1,1,2,3,1,3,3,1,1,1,1,2,0,1,0,3,1,1,1,1
%N 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.
%H A373355 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 A373355 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 A373355   [n | k] := 0 if (n N k) and (k N n);
%F A373355   [n | k] := 1 if (n R k) and (k R n);
%F A373355   [n | k] := 2 if (n R k) and (k N n);
%F A373355   [n | k] := 3 if (n N k) and (k R n).
%F A373355 We write [n || k] for [prime(n) | prime(k)] and set T(n, k) = [n - k + 1 || k].
%F A373355 Exchanging 2 <-> 3 reverses the rows.
%e A373355 Triangle starts:
%e A373355   [ 1] 1;
%e A373355   [ 2] 2, 3;
%e A373355   [ 3] 2, 1, 3;
%e A373355   [ 4] 1, 0, 0, 1;
%e A373355   [ 5] 2, 2, 1, 3, 3;
%e A373355   [ 6] 2, 3, 0, 0, 2, 3;
%e A373355   [ 7] 1, 1, 1, 1, 1, 1, 1;
%e A373355   [ 8] 2, 0, 0, 2, 3, 0, 0, 3;
%e A373355   [ 9] 1, 2, 0, 0, 1, 0, 0, 3, 1;
%e A373355   [10] 2, 3, 1, 0, 0, 0, 0, 1, 2, 3;
%e A373355   [11] 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1;
%e A373355   [12] 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3;
%p A373355 QRP := proc(n, k) local QR, p, q, a, b;
%p A373355    QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n);
%p A373355    p := ithprime(n); q := ithprime(k);
%p A373355    a := QR(p, q); b := QR(q, p);
%p A373355    if a = -1 and b = -1 then return 0 fi;
%p A373355    if a =  1 and b =  1 then return 1 fi;
%p A373355    if a =  1 and b = -1 then return 2 fi;
%p A373355    if a = -1 and b =  1 then return 3 fi;
%p A373355 end: for n from 1 to 12 do lprint([n], seq(QRP(n-k+1, k), k = 1..n)) od;
%t A373355 QR[n_, k_] := Module[{x, y}, If[Reduce[x^2 == n + k*y, {x, y}, Integers] =!= False, 1, -1]];
%t A373355 QRS[n_, k_] := Module[{p = Prime[n], q = Prime[k], a, b}, a = QR[p, q]; b = QR[q, p]; Which[
%t A373355       a == -1 && b == -1, 0,
%t A373355       a == 1 && b == 1, 1,
%t A373355       a == 1 && b == -1, 2,
%t A373355       a == -1 && b == 1, 3]];
%t A373355 Table[QRS[n - k + 1, k], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Oct 08 2024, after Maple program *)
%o A373355 (Python)
%o A373355 from sympy.ntheory import is_quad_residue, prime
%o A373355 def QR(n, k): return is_quad_residue(n, k)
%o A373355 def QRS(n, k):
%o A373355     p = prime(n); q = prime(k)
%o A373355     a = QR(p, q); b = QR(q, p)
%o A373355     if not a and not b: return 0
%o A373355     if a and b: return 1
%o A373355     if a and not b: return 2
%o A373355     if not a and b: return 3
%o A373355 def T(n, k): return QRS(n - k + 1, k)
%o A373355 for n in range(1, 13): print([n], [T(n, k) for k in range(1, n + 1)])
%Y A373355 Cf. A063987, A373223.
%K A373355 nonn,tabl
%O A373355 1,2
%A A373355 _Peter Luschny_, Jun 02 2024