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

%I #49 Jan 21 2023 15:08:33

%S 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,

%T 50,51,53,54,56,63,65,68,69,74,75,78,81,83,86,89,90,95,96,98,99,105,

%U 111,113,114,116,119,120,125,128,131,134,135,138,140,141,146,153,155,156,158

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

%C 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.

%C From _Vladimir Shevelev_, Jun 18 2016: (Start)

%C 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)).

%C 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)

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

%H Vincenzo Librandi, <a href="/A130290/b130290.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Quadratic_residue">Quadratic Residue</a>

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

%F a(n) = A055034(A000040(n)), n>=1. - _Wolfdieter Lang_, Sep 20 2012

%F a(n) = A005097(n-[n>1]) = A005097(max(n-1,1)). - _M. F. Hasler_, Dec 13 2019

%e a(1)=1 since the only nonzero element of Z/2Z equals its square.

%e a(3)=2 since 1=1^2=(-1)^2 and 4=2^2=(-2)^2 are the only nonzero squares in Z/5Z.

%e a(1000000) = 7742931 = (prime(1000000)-1)/2.

%p 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

%t Quotient[Prime[Range[66]], 2] (* _Vladimir Joseph Stephan Orlovsky_, Sep 20 2008 *)

%o (PARI) A130290(n) = prime(n)>>1

%o (Magma) [Floor((NthPrime(n))/2): n in [1..60]]; // _Vincenzo Librandi_, Jan 16 2013

%o (Python)

%o from sympy import prime

%o def A130290(n): return prime(n)//2 # _Chai Wah Wu_, Jun 04 2022

%Y Essentially the same as A005097.

%Y 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.

%Y Appears in A217983. - _Johannes W. Meijer_, Oct 25 2012

%K easy,nonn

%O 1,3

%A _M. F. Hasler_, May 21 2007