cp's OEIS Frontend

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

%I A130290 #59 May 22 2025 08:47:28
%S A130290 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 A130290 50,51,53,54,56,63,65,68,69,74,75,78,81,83,86,89,90,95,96,98,99,105,
%U A130290 111,113,114,116,119,120,125,128,131,134,135,138,140,141,146,153,155,156,158
%N A130290 Number of nonzero quadratic residues modulo the n-th prime.
%C A130290 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 A130290 From _Vladimir Shevelev_, Jun 18 2016: (Start)
%C A130290 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 A130290 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 A130290 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 A130290 Vincenzo Librandi, <a href="/A130290/b130290.txt">Table of n, a(n) for n = 1..1000</a>
%H A130290 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%H A130290 Wikipedia, <a href="http://en.wikipedia.org/wiki/Quadratic_residue">Quadratic Residue</a>
%F A130290 a(n) = floor( A000040(n)/2 ) = #{ even positive integers <= A000040(n) }
%F A130290 a(n) = A055034(A000040(n)), n>=1. - _Wolfdieter Lang_, Sep 20 2012
%F A130290 a(n) = A005097(n-[n>1]) = A005097(max(n-1,1)). - _M. F. Hasler_, Dec 13 2019
%e A130290 a(1)=1 since the only nonzero element of Z/2Z equals its square.
%e A130290 a(3)=2 since 1=1^2=(-1)^2 and 4=2^2=(-2)^2 are the only nonzero squares in Z/5Z.
%e A130290 a(1000000) = 7742931 = (prime(1000000)-1)/2.
%p A130290 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 A130290 Quotient[Prime[Range[66]], 2] (* _Vladimir Joseph Stephan Orlovsky_, Sep 20 2008 *)
%o A130290 (PARI) A130290(n) = prime(n)>>1
%o A130290 (Magma) [Floor((NthPrime(n))/2): n in [1..60]]; // _Vincenzo Librandi_, Jan 16 2013
%o A130290 (Python)
%o A130290 from sympy import prime
%o A130290 def A130290(n): return prime(n)//2  # _Chai Wah Wu_, Jun 04 2022
%Y A130290 Essentially the same as A005097.
%Y A130290 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 A130290 Appears in A217983. - _Johannes W. Meijer_, Oct 25 2012
%K A130290 easy,nonn
%O A130290 1,3
%A A130290 _M. F. Hasler_, May 21 2007