A036468 Number of ways to represent 2n+1 as a+b with 0 < a < b and a^2 + b^2 prime.

1, 2, 2, 2, 3, 3, 4, 4, 4, 3, 4, 8, 4, 6, 5, 4, 9, 8, 6, 9, 7, 7, 7, 5, 7, 9, 14, 8, 9, 11, 7, 17, 11, 10, 9, 11, 9, 8, 13, 9, 15, 20, 11, 14, 13, 8, 18, 14, 10, 18, 16, 10, 17, 16, 13, 20, 20, 13, 14, 17, 12, 23, 18, 14, 22, 15, 17, 18, 21, 12, 19, 29, 16, 23, 21, 14, 27, 24

Offset: 1

Author

R. K. Guy

Keywords

• nonn

Comments

Zhang Ming-Zhi (zamiz(AT)mail.sc.cninfo.net) asks if a(m) is always > 0.

I have confirmed that a(n) > 0 for 0 < n < 10^7. - T. D. Noe, Oct 17 2004

This open problem is mentioned by Guy at the end of section C1. - T. D. Noe, Apr 22 2009

a(n) <= phi(2n+1)/2, where phi(m) = A000010(m), while a(n) = phi(2n+1)/2 only for n = 1, 2, and 7. - Thomas Ordowski, Jan 25 2014

Records in a(n) are for 2n+1 = 3, 5, 11, 15, 25, 35, 55, 65, 85, 125, 145, 185, 205, 215, 235, 265, 295, 325, 365, 415, ... cf. A001750. - Thomas Ordowski, Mar 02 2017

a(n) tends to be larger for n == 2 (mod 5): see plot in Links. - Robert Israel, Mar 02 2017

Number of primes p = ((2n+1)^2 + x^2)/2 for positive integers x < 2n+1. - Thomas Ordowski, Mar 06 2017

References

• R. K. Guy, Unsolved Problems in Theory of Numbers, Section C1.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Gordon Hamilton, Unsolved K-12: Grade 7, 2014. (video)
• Robert Israel, a(5k+j) for j=0,1,2,3,4

Crossrefs

Cf. A082519, A099468, A281543.

Programs

Maple

a:= n-> add(`if`(isprime(i^2+(2*n+1-i)^2), 1, 0), i=1..n):
seq(a(n), n=1..80);  # Alois P. Heinz, Jul 09 2016

Mathematica

Table[cnt=0; m=2n+1; Do[If[PrimeQ[k^2+(m-k)^2], cnt++ ], {k, n}]; cnt, {n, 100}]

PARI

a(n)=sum(k=1,n,isprime(k^2+(2*n-k+1)^2)) \\ Charles R Greathouse IV, Jan 09 2014

Formula

a(n) = O(n/log(n)). - Thomas Ordowski, Feb 11 2013

Extensions

More terms from David W. Wilson and Michael Kleber