%I #12 Apr 24 2014 09:00:07

%S 0,0,0,1,1,1,1,2,1,1,3,2,4,2,3,3,3,1,5,5,4,6,5,5,3,5,5,3,3,4,7,3,7,4,

%T 6,7,7,4,4,3,6,8,8,6,5,8,7,8,6,6,8,11,8,6,7,7,5,9,2,8,3,11,10,8,6,8,7,

%U 10,5,8,8,9,13,10,10,6,6,10,11,10

%N a(n) = |{0 < k < sqrt(prime(n)): k^2 + 1 is a quadratic residue modulo prime(n)}|.

%C a(n) > 0 for all n > 3. In fact, for any prime p > 5 one of 1^2 + 1 = 2, 2^2 + 1 = 5 and 3^2 + 1 = 10 is a quadratic residue modulo p. Similarly, if p > 7 is a prime not equal to 19, then k^2 - 1 is a quadratic residue modulo p for some positive integer k < sqrt(p). In fact, for any prime p > 7, one of 2^2 - 1 = 3, 3^2 - 1 = 8 and 5^2 - 1 = 24 is a quadratic residue modulo p.

%C See also A239957 for a similar conjecture involving primitive roots modulo primes. Note that a primitive root modulo an odd prime p must be a quadratic nonresidue modulo p.

%H Zhi-Wei Sun, <a href="/A241472/b241472.txt">Table of n, a(n) for n = 1..10000</a>

%e a(6) = 1 since 3^2 + 1 = 10 is a quadratic residue modulo prime(6) = 13.

%e a(7) = 1 since 1^2 + 1 = 2 is a quadratic residue modulo prime(7) = 17.

%e a(9) = 1 since 1^2 + 1 = 2 is a quadratic residue modulo prime(9) = 23.

%e a(10) = 1 since 2^2 + 1 = 5 is a quadratic residue modulo prime(10) = 29.

%e a(18) = 1 since 2^2 + 1 = 5 is a quadratic residue modulo prime(18) = 61.

%t a[n_]:=Sum[If[JacobiSymbol[k^2+1,Prime[n]]==1,1,0],{k,1,Sqrt[Prime[n]-1]}]

%t Table[a[n],{n,1,80}]

%Y Cf. A000040, A002522, A239957, A241492.

%K nonn

%O 1,8

%A _Zhi-Wei Sun_, Apr 23 2014