Characterizing the set of positive integers which cannot be represented as $p+a^2$

Question

An exercise in Burton's book "Elementary Number Theory" 7ed, p43 prob 2, is to give a counterexample to the statement:

Every positive integer $n$ has a representation $n=p+a^2$, where $p$ is $1$ or a prime, and $a\ge 0$ is a nonnegative integer.

This is false for $n=25$. I'm interested in finding all $n,$ or maybe some infinite families of $n$, for which it is false.

By looking at factors of a difference of squares, I found the family $n=m^2$, where $2m-1$ is composite. $25$ is in this family.

When $n$ is square the ability to factor makes the problem simple; so I'm looking for larger sets of counterexamples. I'd be surprised if one could characterize all $n$ which are counterexamples, but would want to use whatever result is found to actually generate the appropriate counterexamples.

Answer 1

No infinite family except squares is known. In fact, only $21$ numbers are known that are not a square nor a prime plus a square, see OEIS/A020495:

$ 10,34,58,85,91,130,214,226,370,526,706,730,771,1255,1351,1414,1906,2986,3676,9634,21679 $

Apparently, these are all the examples up to $3000000000$.

Answer 2

This set is A014090, and related OEIS sequences:

• squares in this set: A104275^2
• nonsquares in this set: A020495 (conjectured to be finite with 21 numbers, the largest number is 21679)
• 0 is not counted as square: A064233
• 0 is not counted as square, primes in this set: A065377 (conjectured to be finite with 15 numbers, the largest number is 7549)

Related problem for the odd positive integers which cannot be represented as p+2*a^2 with prime p, this set is conjectured to be {1, 5777, 5993}

• 0 is not counted as square: A060003 (conjectured to be finite with 10 numbers, the largest number is 5993)
• 0 is not counted as square, primes in this set (together with the “oddest” prime 2): A042978 (conjectured to be finite with 8 numbers, the largest number is 1493)

The combine of these two problems: positive integers which cannot be represented as p+2*a^2 or 2*p+2*a^2 with odd prime p and 0 is not counted as square (i.e. p=2 or/and a=0 is not allowed), the set is 2*A064233 together with A060003 together the number 6 (6 is the only number requiring the even prime 2), and this set is infinite, since all 2*A104275^2 are in this set, and for all numbers in this set which are not twice a square number, see A347567 (A347567 = the union of 2*A020495, 2*A065377, A060003, and the number 6 (6 is the only number requiring the even prime 2), thus A347567 has 21 + 15 + 10 + 1 = 47 numbers), which is conjectured to be finite with 47 numbers, the largest number is 43358

And for the similar problem about triangular numbers (instead of square numbers):

This set is A076768, and related OEIS sequences:

• triangular numbers in this set: 1+2+3+….+A138666
• non-triangular numbers in this set: (conjectured only the number 216)
• 0 is not counted as triangular number: A111908
• 0 is not counted as triangular number, non-triangular numbers in this set: A255904
• 0 is not counted as triangular number, primes in this set: A065397 (conjectured to be finite with 4 numbers, the largest number is 211)

Related problem for the odd positive integers which cannot be represented as p+a*(a+1) with prime p, this set is conjectured to be {1}, and if 0 is not counted as triangular number, then this set is conjectured to be {1, 3}

The combine of these two problems: positive integers which cannot be represented as p+a*(a+1) or 2*p+a*(a+1) with odd prime p and 0 is not counted as triangular number (i.e. p=2 or/and a=0 is not allowed), the set is 2*A111908 together with {1, 3} together the number 10 (10 is the only number requiring the even prime 2), and this set is infinite, since all 2*(1+2+3+….+A138666) are in this set, and for all numbers in this set which are not twice a triangular number, see A347568 (A347568 = the union of {432}, 2*A065397, {1, 3}, and the number 10 (10 is the only number requiring the even prime 2), thus A347568 has 1 + 4 + 2 + 1 = 8 numbers), which is conjectured to be finite with 8 numbers, the largest number is 432