login
A063987
Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.
25
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, 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, 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
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
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
Cf. A063988, A010379 (6th row), A010381 (7th row), A010385 (8th row), A010391 (9th row), A010392 (10th row), A278580 (row 23), A230077.
Cf. A076409 (row sums).
Cf. A046071 (for all n), A048152 (for all n, with 0's).
Sequence in context: A366397 A080508 A178141 * A236269 A010126 A021712
KEYWORD
nonn,tabf,nice,easy
AUTHOR
Suggested by Gary W. Adamson, Sep 18 2001
EXTENSIONS
Edited by Wolfdieter Lang, Mar 06 2016
STATUS
approved