A069004 - OEIS

%I #44 Mar 01 2023 09:13:59

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

%T 8,5,6,7,3,9,5,5,8,8,7,9,6,7,10,8,6,9,10,5,8,8,6,10,11,8,11,10,6,9,15,

%U 5,10,11,4,11,13,6,12,10,12,11,9,8,11,19,10,15,9,8,19,11,8,11,14,15,13

%N Number of times n^2 + s^2 is prime for positive integers s < n.

%C Conjecture: a(n)>0 for all n>1. - Entries checked by _Franklin T. Adams-Watters_, May 05 2006

%C The graph of this sequence inspires the following conjecture: A > a(n)/pi(n) > B, where A and B are constants and pi(n) is the prime counting function (A000720). - _T. D. Noe_, Feb 26 2007

%C Stronger conjecture: Let pi(n) be the prime counting function (A000720). Then pi(n) >= a(n) >= pi(n)/5 for n>1, with the following equalities: pi(2)=a(2), pi(10)=a(10) and a(12)=pi(12)/5. - _T. D. Noe_, Feb 26 2007

%C Records in a(n) are for n = 1, 2, 5, 8, 10, 20, 25, 35, 40, 49, 59, 65, 80, 115, 125, 130, 158, 200, 250, 265, 310, ... - _Thomas Ordowski_, Mar 05 2017

%C Number of primes p = (x^2 + y^2)/2 with 0 < x < y such that x + y = 2n. - _Thomas Ordowski_, Mar 06 2017

%H T. D. Noe, <a href="/A069004/b069004.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = O(n/log(n)). a(n) <= phi(n), a(n) = phi(n) for n = 2, 6, and 10. a(n) <= phi(2n)/2, a(n) = phi(2n)/2 for n = 2, 3, 5, 6, and 10. - _Thomas Ordowski_, Mar 01 2017

%e a(5)=2 because there are 2 values of s (2 and 4) such that 5^2 + s^2 is a prime number.

%t maxN=100; lst={}; For[n=1, n<=maxN, n++, cnt=0; For[d=1, d<n, d=d+2, p=n^2+(n-d)^2; If[PrimeQ[p], cnt++ ] ]; AppendTo[lst, cnt]; ]; lst

%t Table[Count[n^2+Range[n-1]^2,_?PrimeQ],{n,100}] (* _Harvey P. Dale_, Mar 01 2023 *)

%o (PARI) a(n) = sum(s=1, n-1, isprime(n^2+s^2)); \\ _Michel Marcus_, Jan 15 2017

%Y Cf. A000010, A036468, A057368, A281543.

%K easy,nonn

%O 1,5

%A _T. D. Noe_, Apr 02 2002

%E Entries checked by _Franklin T. Adams-Watters_, May 05 2006