OFFSET
1,4
COMMENTS
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
REFERENCES
Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 82 at p. 202.
LINKS
T. D. Noe, Rows n = 1..100 of triangle, flattened
C. F. 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.
EXAMPLE
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.
The irregular triangle T(n, k) begins (p is prime(n)):
n p \k 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1, 2: 1
2, 3: 1
3, 5: 1 4
4, 7: 1 2 4
5, 11: 1 3 4 5 9
6: 13: 1 3 4 9 10 12
7, 17: 1 2 4 8 9 13 15 16
8, 19: 1 4 5 6 7 9 11 16 17
9, 23: 1 2 3 4 6 8 9 12 13 16 18
10, 29: 1 4 5 6 7 9 13 16 20 22 23 24 25 28
... reformatted by Wolfdieter Lang, Mar 06 2016
MAPLE
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:
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do p := ithprime(n):
print(select(a -> 1 = QR(a, p), [seq(1..p-1)])) od: # Peter Luschny, Jun 02 2024
MATHEMATICA
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 *)
PROG
(PARI) residue(n, m)=local(r); r=0; for(i=0, floor(m/2), if(i^2%m==n, r=1)); r
isA063987(n, m)=residue(n, prime(m)) /* Michael B. Porter, May 07 2010 */
(PARI) row(n) = my(p=prime(n)); select(x->issquare(Mod(x, p)), [1..p-1]); \\ Michel Marcus, Nov 07 2020
(Python)
from sympy import jacobi_symbol as J, prime
def a(n):
p = prime(n)
return [1] if n==1 else [i for i in range(1, p) if J(i, p)==1]
for n in range(1, 11): print(a(n)) # Indranil Ghosh, May 27 2017
(SageMath)
for p in prime_range(30): print(quadratic_residues(p)[1:])
# Peter Luschny, Jun 02 2024
CROSSREFS
KEYWORD
nonn,tabf,nice,easy
AUTHOR
Suggested by Gary W. Adamson, Sep 18 2001
EXTENSIONS
Edited by Wolfdieter Lang, Mar 06 2016
STATUS
approved