cp's OEIS Frontend

A063987 Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.

%I A063987 #96 Aug 16 2024 08:36:26
%S A063987 1,1,1,4,1,2,4,1,3,4,5,9,1,3,4,9,10,12,1,2,4,8,9,13,15,16,1,4,5,6,7,9,
%T A063987 11,16,17,1,2,3,4,6,8,9,12,13,16,18,1,4,5,6,7,9,13,16,20,22,23,24,25,
%U A063987 28,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28,1,3,4,7,9,10,11,12,16,21,25
%N A063987 Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.
%C A063987 For n >= 2, row lengths are (prime(n) - 1)/2. For example, since 17 is the 7th prime number, the length of row 7 is (17 - 1)/2 = 8. - _Geoffrey Critzer_, Apr 04 2015
%D A063987 Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 82 at p. 202.
%H A063987 T. D. Noe, <a href="/A063987/b063987.txt">Rows n = 1..100 of triangle, flattened</a>
%H A063987 C. F. 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.
%e A063987 Modulo the 5th prime, 11, the (11 - 1)/2 = 5 quadratic residues are 1,3,4,5,9 and the 5 non-residues are 2, 6, 7, 8, 10.
%e A063987 The irregular triangle T(n, k) begins (p is prime(n)):
%e A063987    n    p  \k 1 2 3 4  5  6  7  8  9 10 11 12 13 14
%e A063987    1,   2:    1
%e A063987    2,   3:    1
%e A063987    3,   5:    1 4
%e A063987    4,   7:    1 2 4
%e A063987    5,  11:    1 3 4 5  9
%e A063987    6:  13:    1 3 4 9 10 12
%e A063987    7,  17:    1 2 4 8  9 13 15 16
%e A063987    8,  19:    1 4 5 6  7  9 11 16 17
%e A063987    9,  23:    1 2 3 4  6  8  9 12 13 16 18
%e A063987   10,  29:    1 4 5 6  7  9 13 16 20 22 23 24 25 28
%e A063987   ...  reformatted by _Wolfdieter Lang_, Mar 06 2016
%p A063987 with(numtheory): for n from 1 to 20 do for j from 1 to ithprime(n)-1 do if legendre(j, ithprime(n)) = 1 then printf(`%d,`,j) fi; od: od:
%p A063987 # Alternative:
%p A063987 QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
%p A063987 for n from 1 to 10 do p := ithprime(n):
%p A063987 print(select(a -> 1 = QR(a, p), [seq(1..p-1)])) od:  # _Peter Luschny_, Jun 02 2024
%t A063987 row[n_] := (p = Prime[n]; Select[ Range[p - 1], JacobiSymbol[#, p] == 1 &]); Flatten[ Table[ row[n], {n, 1, 12}]] (* _Jean-François Alcover_, Dec 21 2011 *)
%o A063987 (PARI) residue(n,m)=local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r
%o A063987 isA063987(n,m)=residue(n,prime(m)) /* _Michael B. Porter_, May 07 2010 */
%o A063987 (PARI) row(n) = my(p=prime(n)); select(x->issquare(Mod(x,p)), [1..p-1]); \\ _Michel Marcus_, Nov 07 2020
%o A063987 (Python)
%o A063987 from sympy import jacobi_symbol as J, prime
%o A063987 def a(n):
%o A063987     p = prime(n)
%o A063987     return [1] if n==1 else [i for i in range(1, p) if J(i, p)==1]
%o A063987 for n in range(1, 11): print(a(n)) # _Indranil Ghosh_, May 27 2017
%o A063987 (SageMath)
%o A063987 for p in prime_range(30): print(quadratic_residues(p)[1:])
%o A063987 # _Peter Luschny_, Jun 02 2024
%Y A063987 Cf. A063988, A010379 (6th row), A010381 (7th row), A010385 (8th row), A010391 (9th row), A010392 (10th row), A278580 (row 23), A230077.
%Y A063987 Cf. A076409 (row sums).
%Y A063987 Cf. A046071 (for all n), A048152 (for all n, with 0's).
%K A063987 nonn,tabf,nice,easy
%O A063987 1,4
%A A063987 Suggested by _Gary W. Adamson_, Sep 18 2001
%E A063987 Edited by _Wolfdieter Lang_, Mar 06 2016