A130290 Number of nonzero quadratic residues modulo the n-th prime.

1, 1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36, 39, 41, 44, 48, 50, 51, 53, 54, 56, 63, 65, 68, 69, 74, 75, 78, 81, 83, 86, 89, 90, 95, 96, 98, 99, 105, 111, 113, 114, 116, 119, 120, 125, 128, 131, 134, 135, 138, 140, 141, 146, 153, 155, 156, 158

Offset: 1

Author

M. F. Hasler, May 21 2007

Keywords

• easy
• nonn

Comments

Row lengths for formatting A063987 as a table: The number of nonzero quadratic residues modulo a prime p equals floor(p/2), or (p-1)/2 if p is odd. The number of squares including 0 is (p+1)/2, if p is odd (rows prime(i) of A096008 formatted as a table). In fields of characteristic 2, all elements are squares. For any m > 0, floor(m/2) is the number of even positive integers less than or equal to m, so a(n) also equals the number of even positive integers less than or equal to the n-th prime. For all n > 0, A130290(n+1) = A005097(n) = A102781(n+1) = A102781(n+1) = A130291(n+1)-1 = A111333(n+1)-1 = A006254(n)-1.

From Vladimir Shevelev, Jun 18 2016: (Start)

a(1)+2 and, for n >= 2, a(n)+1 is the smallest k such that there exists 0 < k_1 < k with the condition k_1^2 == k^2 (mod prime(n)).

Indeed, for n >= 2, if prime(n) = 4*t+1 then k = 2*t+1 = a(n)+1, since (2*t+1)^2 == (2*t)^2 (mod prime(n)) and there cannot be a smaller value of k; if prime(n) = 4*t-1, then k = 2*t = a(n)+1, since (2*t)^2 == (2*t-1)^2 (mod prime(n)). (End)

a(n) is the number of pairs (a,b) such that a + b = prime(n) with 1 <= a <= b. - Nicholas Leonard, Oct 02 2022

Examples

			a(1)=1 since the only nonzero element of Z/2Z equals its square.
a(3)=2 since 1=1^2=(-1)^2 and 4=2^2=(-2)^2 are the only nonzero squares in Z/5Z.
a(1000000) = 7742931 = (prime(1000000)-1)/2.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Quadratic Residue
• Wikipedia, Quadratic Residue

Crossrefs

Essentially the same as A005097.

Cf. A102781 (Number of even numbers less than the n-th prime), A063987 (quadratic residues modulo the n-th prime), A006254 (Numbers n such that 2n-1 is prime), A111333 (Number of odd numbers <= n-th prime), A000040 (prime numbers), A130291.

Appears in A217983. - Johannes W. Meijer, Oct 25 2012

Programs

Magma

[Floor((NthPrime(n))/2): n in [1..60]]; // Vincenzo Librandi, Jan 16 2013

Maple

A130290 := proc(n): if n =1 then 1 else (A000040(n)-1)/2 fi: end: A000040 := proc(n): ithprime(n) end: seq(A130290(n), n=1..55); # Johannes W. Meijer, Oct 25 2012

Mathematica

Quotient[Prime[Range[66]], 2] (* Vladimir Joseph Stephan Orlovsky, Sep 20 2008 *)

PARI

A130290(n) = prime(n)>>1

Python

from sympy import prime
def A130290(n): return prime(n)//2  # Chai Wah Wu, Jun 04 2022

Formula

a(n) = floor( A000040(n)/2 ) = #{ even positive integers <= A000040(n) }

a(n) = A055034(A000040(n)), n>=1. - Wolfdieter Lang, Sep 20 2012

a(n) = A005097(n-[n>1]) = A005097(max(n-1,1)). - M. F. Hasler, Dec 13 2019