A063987 -id:A063987 - cp's OEIS frontend

A177864 a(n) is the smallest nontrivial quadratic residue modulo prime(n), for n >= 3.

4, 2, 3, 3, 2, 4, 2, 4, 2, 3, 2, 4, 2, 4, 3, 3, 4, 2, 2, 2, 3, 2, 2, 4, 2, 3, 3, 2, 2, 3, 2, 4, 4, 2, 3, 4, 2, 4, 3, 3, 2, 2, 4, 2, 4, 2, 3, 3, 2, 2, 2, 3, 2, 2, 4, 2, 3, 2, 4, 4, 4, 2, 2, 4, 4, 2, 3, 3, 2, 2, 2, 3, 4, 2, 4, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 4, 2, 3, 2, 2, 3, 4, 2, 4, 2, 4, 3

Offset: 3

Jonathan Sondow, May 16 2010

There is no quadratic residue > 1 modulo the first or 2nd prime, so the sequence begins with a(3).

			The quadratic residues modulo prime(3) = 5 are 1 and 4, so a(3) = 4.

Wikipedia, Quadratic residue
Wikipedia, Quadratic reciprocity

Cf. A063987 (triangle in which the n-th row gives the quadratic residues modulo prime(n)), A053760 (smallest positive quadratic nonresidue modulo prime(n)).

Flatten[Table[ Extract[Flatten[ Position[Table[JacobiSymbol[i, Prime[n]], {i, 1, Prime[n] - 1}], 1]], {2}], {n, 3, 100}]]

a(n,p=prime(n))=[2,0,0,0,4,0,2,0,0,0,3,0,3,0,0,0,2,0,4,0,0,0,2][p%24] \\ Charles R Greathouse IV, Jun 14 2022

a(n) = 2 or 3 or 4 according as prime(n) == 1,7,9,15,17,23 or 11,13 or 3,5,19,21 (mod 24), respectively, for n > 2, by the quadratic reciprocity law and its supplements.

A270819 a(n) is the number of arithmetic progressions of length 3 among the quadratic residues modulo prime(n).

Original entry on oeis.org

0, 0, 0, 0, 10, 12, 16, 36, 44, 84, 90, 144, 160, 210, 230, 312, 406, 420, 528, 560, 576, 702, 820, 880, 1056, 1200, 1224, 1378, 1404, 1456, 1890, 2080, 2176, 2346, 2664, 2700, 2964, 3240, 3320, 3612, 3916, 3960, 4370, 4416, 4704, 4752, 5460, 5994, 6328, 6384, 6496

Offset: 1

Michel Marcus, Mar 23 2016

nonn

Wraparound progressions as well as decreasing progressions are counted.

			For p=prime(5)=11, whose quadratic residues are (1,3,4,5,9), some examples of 3-term arithmetic progressions are (3,4,5), (4,9,3) and (5,4,3).

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see Exercise 2.29 p. 111.

Cf. A063987.

Table[(# - 1) Floor[(# - 2)/8] &@ Prime@ n, {n, 51}] (* Michael De Vlieger, Mar 23 2016 *)

PARI
```
a(n) = my(p=prime(n)); (p-1)*((p-2)\8);
```

a(n) = (prime(n)-1)*floor((prime(n)-2)/8).

A338756 Number of consecutive triples of quadratic residues mod p in the interval [1..p-1] where p is the n-th prime.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 4, 3, 4, 2, 5, 5, 4, 7, 8, 8, 8, 8, 9, 10, 8, 8, 12, 12, 13, 12, 14, 15, 16, 18, 17, 16, 18, 16, 20, 20, 24, 22, 24, 23, 24, 24, 24, 26, 27, 28, 24, 24, 29, 32, 31, 30, 32, 36, 33, 36, 32, 35, 40, 38, 38, 34, 36, 41, 38, 43, 44, 38, 44, 45, 44, 47

Offset: 1

Michel Marcus, Nov 07 2020

nonn

Number of consecutive triples in A063987.

			The 8th row of A063987 for prime 19 is [1, 4, 5, 6, 7, 9, 11, 16, 17] has 2 consecutive triples [4, 5, 6] and [5, 6, 7], so a(8)=2.

George E. Andrews, Consecutive triples of quadratic residues, paragraph 10-2, p. 133, in Number Theory, W.B. Saunders Company 1971.

Cf. A000040, A063987.

a:= n-> (l-> add(`if`(l[i]-l[i-1]=1 and l[i+1]-l[i]=1 , 1, 0),
         i=2..nops(l)-1))((p-> select(j-> numtheory[legendre]
         (j, p)=1, [$1..p-1]))(ithprime(n))):
seq(a(n), n=1..80);  # Alois P. Heinz, Nov 08 2020

a[n_] := With[{p = Prime[n], KS = KroneckerSymbol},
   Sum[(1+KS[k, p])*(1+KS[k+1, p])*(1+KS[k+2, p])/8, {k, 1, p-3}]];
Table[a[n], {n, 1, 75}] (* Jean-François Alcover, Jan 27 2025 *)

C(k, p) = (1+kronecker(k,p))*(1+kronecker(k+1,p))*(1+kronecker(k+2,p))/8;
a(n) = my(p=prime(n)); sum(k=1, p-3, C(k,p));

a(n)={my(p=prime(n), v=vector(p-1,n,issquare(Mod(n,p))), ct=0); for(j=1,#v-2,ct+=(v[j]&&v[j+1]&&v[j+2])); ct}
vector(66,n,a(n)) \\ Joerg Arndt, Nov 08 2020

a(n) = Sum_{k=1, p-3} (1+(k/p))*(1+((k+1)/p))*(1+((k+2)/p))/8 where (x/y) is the Kronecker symbol and p is the n-th prime. See Andrews pp. 133-134.

A371497 Irregular triangle read by rows: n-th row gives congruence classes s such that the n-th prime q is a quadratic residue modulo an odd prime p if and only if p = plus or minus s for some s (mod m), where m = q if q is of the form 4k + 1, else m = 4q.

Original entry on oeis.org

1, 1, 1, 1, 3, 9, 1, 5, 7, 9, 19, 1, 3, 4, 1, 2, 4, 8, 1, 3, 5, 9, 15, 17, 25, 27, 31, 1, 7, 9, 11, 13, 15, 19, 25, 29, 41, 43, 1, 4, 5, 6, 7, 9, 13, 1, 3, 5, 9, 11, 15, 23, 25, 27, 33, 41, 43, 45, 49, 55, 1, 3, 4, 7, 9, 10, 11, 12, 16, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 1, 3, 7, 9, 13, 17

Offset: 1

Nick Hobson, Mar 25 2024

If n-th prime q is of the form 4k + 1, then by quadratic reciprocity row n consists of quadratic residues mod q, that are less than 2k; i.e., for q > 3, the first half of the corresponding row in A063987.

The first term in each row is always 1.

			The 1st prime, 2, not of the form 4k + 1, is a square modulo odd primes p if and only if p = +/- 1 (mod 4*2 = 8).
The 6th prime, 13, of the form 4k + 1, is a square modulo odd primes p if and only if p = +/- 1, +/- 3, or +/- 4 (mod 13).
The irregular triangle T(n,k) begins (q is prime(n)):
 n   q \k 1 2 3 4 5 6 7 8 9 10 11
 1,  2: 1
 2,  3: 1
 3,  5: 1
 4,  7: 1 3 9
 5, 11: 1 5 7 9 19
 6: 13: 1 3 4
 7, 17: 1 2 4 8
 8, 19: 1 3 5 9 15 17 25 27 31
 9, 23: 1 7 9 11 13 15 19 25 29 41 43
10, 29: 1 4 5 6 7 9 13

Cf. A063987, A081728.

from sympy import prime
def A371497_row(n):
    q = prime(n)
    res = {i*i % q for i in range(1, q//2 + 1)}
    if q % 4 == 1:
        res = {a for a in res if 2*a < q}
    else:
        res = {((a % 4 - 1) * q + a) % (4*q) for a in res}
        res = {a if a < 2*q else 4*q - a for a in res}
    return sorted(res)

cp's OEIS Frontend

A177864 a(n) is the smallest nontrivial quadratic residue modulo prime(n), for n >= 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A270819 a(n) is the number of arithmetic progressions of length 3 among the quadratic residues modulo prime(n).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

Formula

A338756 Number of consecutive triples of quadratic residues mod p in the interval [1..p-1] where p is the n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A371497 Irregular triangle read by rows: n-th row gives congruence classes s such that the n-th prime q is a quadratic residue modulo an odd prime p if and only if p = plus or minus s for some s (mod m), where m = q if q is of the form 4k + 1, else m = 4q.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python