# How to prove this obviously true conjecture?

I've tested computationally if a natural number $n$ can be written as $n=c+m^2$, where $m$ is an integer greater than zero and $c$ is a composite with at least two different primefactors. It seems that just $11$ numbers can not be written in that form:

1 100000 ~ :| n | n test 0= ; intcond zet. {1,2,3,4,5,6,8,9,12,17,20} ok


Therefore, I would like to see a proof of the conjecture:

All integers $n$, large enough, can be written as $n=c+m^2$, where $m\in \mathbb Z_+$ and $\omega(c)>1$.

It's very plausible that there is a maximal number not satisfying 'test'. Otherwise there would be arbitrary large integers $n$ such that $n-m^2$ is a prime power for every $m$ such that $n<m^2$. But how to prove it?

Given an integer $n$ there are $\lceil\sqrt{n}\rceil-1$ perfect squares less than $n$, so there are $\lceil\sqrt{n}\rceil-1$ numbers $n-m^2$ that all must be prime powers in order to be an exception. Due to What's the asymptotic distribution of $p^n$ (powers of primes)? the number of prime powers less than a number $x$ is asymptotically equivalent with $\frac{x}{\ln x}$. Thus, the probability of $n-m^2$ to be a prime power is $\frac{1}{\ln (n-m^2)}$ and the probability $P_n$ for n to be an exception is: $$P_n=\prod_{m=1}^{\lceil\sqrt{n}\rceil-1}\Big(\frac{1}{\ln (n-m^2)}\Big)$$

Due to my calculations:

$P_{10}\approx 2.54007092542113\cdot 10^{-1}$
$P_{100}\approx 3.20233617274630\cdot 10^{-6}$
$P_{1000}\approx 7.55006999135314\cdot 10^{-25}$
$P_{10000}\approx 3.81090059510128\cdot 10^{-93}$

For me it isn't impossible that it exist a really large exception, but it is counter intuitive that there exist arbitrary large exceptions.

• Why do you think this conjecture is "obviously" true? – 5xum Jul 31 '17 at 13:25
• I'm guessing you looked up to 100000 ? – user451844 Jul 31 '17 at 13:32
• @5xum. I explained that. In my opinion it would be absurd if there was arbitrary big integers $n$ such that for all $m>0$, $n-m^2$ is a primepower $p^i, \: i\in \mathbb N$. – Lehs Jul 31 '17 at 13:37
• @Lehs And in my opinion, it would be absurd if there existed an integer solution for the equation $x^n+y^n=z^n$ where $n\geq 3$... That doesn't mean it's obvious that there are no such solutions... – 5xum Jul 31 '17 at 13:38
• @Lehs My point is that things that are "obvious" are things that can be quickly proven. So your conjecture is anything but obvious. – 5xum Jul 31 '17 at 13:44

Suppose $n-m^2$ is a prime power for every integer $m$ with $0<m<\sqrt{n}$. Then the differences $$(n-m^2)-(n-(m+1)^2)=2m+1,$$ are odd, so precisely one of the differences is a positive power of $2$. That means $n-m^2$ is a positive power of $2$ either for all odd $m$, or for all even $m$. Neither $$(n-3^2)-(n-7^2)=40\qquad\text{ nor }\qquad(n-4^2)-(n-6^2)=20,$$ is a difference of two positive powers of $2$, so $n\leq49$.
• I don't follow. Why are you supposing $n-m^2$ is a prime power? One of OP's conditions is that $n-m^2$ is a composite with at least two different prime factors, i.e., not a prime power. – tilper Jul 31 '17 at 13:54
• A nice argument! @Lehs The argument was that if $n$ is a counterexample then $n-m^2$ is a power of two either for all odd $m$ or for all even $m$, all depending on which half of choices for $m$ yields even values for $n-m^2$. So if $n>49$ is an odd counterexample both $n-9$ and $n-49$ must be powers of two. Similarly, if $n>36$ is an even counterexample both $n-16$ and $n-36$ must be powers of two. But both of those are impossible. – Jyrki Lahtonen Jul 31 '17 at 19:40
• $21=3^2+12.$ And for $22\leq n\leq 49$ we have $n=1^2+m$ or $n=2^2+m$ for some $m$ that meets the hypothesis. So $n=20$ is indeed the largest exception..... Excellent answer. – DanielWainfleet Aug 1 '17 at 3:29