3
$\begingroup$

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.

$\endgroup$
10
  • 7
    $\begingroup$ Why do you think this conjecture is "obviously" true? $\endgroup$ – 5xum Jul 31 '17 at 13:25
  • $\begingroup$ I'm guessing you looked up to 100000 ? $\endgroup$ – user451844 Jul 31 '17 at 13:32
  • $\begingroup$ @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$. $\endgroup$ – Lehs Jul 31 '17 at 13:37
  • 3
    $\begingroup$ @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... $\endgroup$ – 5xum Jul 31 '17 at 13:38
  • 2
    $\begingroup$ @Lehs My point is that things that are "obvious" are things that can be quickly proven. So your conjecture is anything but obvious. $\endgroup$ – 5xum Jul 31 '17 at 13:44
11
$\begingroup$

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 two 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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – user307169 Jul 31 '17 at 13:54
  • $\begingroup$ Why must precisely one of the differences be a positive power of 2? $\endgroup$ – Lehs Jul 31 '17 at 18:07
  • 3
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 31 '17 at 19:40
  • $\begingroup$ @JyrkiLahtonen, thanks but I don't even understand why any of the differences must be a power of two. $\endgroup$ – Lehs Jul 31 '17 at 19:51
  • 2
    $\begingroup$ $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. $\endgroup$ – DanielWainfleet Aug 1 '17 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.