We start with the partition of $N=5$.

$$5$$ $$4+1$$ $$3+2$$ $$3+1+1$$ $$2+2+1$$ $$2+1+1+1$$ $$1+1+1+1+1$$

Then we form the sum of squares (no limit on the number of elements) to get:

$$4^2+1^2=17$$ $$3^2+2^2=13$$ $$3^2+1^2+1^2=11$$ $$2^2+2^2+1^2=9$$ $$2^2+1^2+1^2+1^2=7$$ $$1^2+1^2+1^2+1^2+1^2=5$$

In this simple case we see that all primes from $N=5$ to $N=17$ have been generated. This is not true in general. If we consider the partition of $N=7$ and calculate the sum of squares of individual partitions, we will see that the primes $23,31$ weren't generated. If we consider the partition of $N=9$, we will see that the primes $37,43,59,61$ are missing (but not the previous $23,31$).

Is it enough to consider only the partitions of two odd integers $N$ and $N+2$ to find all the primes between $N$ and $(N-1)^2 + 1$, assuming N is a prime? If $N$ is not a prime, the question will apply to the nearest prime above $N$ and $(N-1)^2+1$.

  • 3
    $\begingroup$ The problem is that some non-primes are generated, too - in this case, $9.$ We can easily generate all primes from $a$ to $b$ if we are allowed to generate non-primes as well. :) $\endgroup$ – Thomas Andrews Apr 2 '18 at 15:10
  • 1
    $\begingroup$ For example, if $p\equiv 3,4\pmod 5$ then $1,p-1$ is a partition of $p$ but $1^2+(p-1)^2\equiv 0\pmod 5$, and $1^2+(p-1)^2>5$ for $p>3.$ $\endgroup$ – Thomas Andrews Apr 2 '18 at 15:15
  • 1
    $\begingroup$ So do you mean this? -- Conjecture. Let $N$ be a prime and $p$ a prime with $N\le p\le (N-1)^2+1$; then there exist positive integers $n$ and $a_1,\ldots,a_n$ such that $\sum a_i^2=p$ and $\sum a_i\in\{N, N+2\}$. $\endgroup$ – Hagen von Eitzen Apr 2 '18 at 15:40
  • $\begingroup$ Yes, but we don't get all the primes in that interval as Thomas Andrews proved in his answer below. $\endgroup$ – user25406 Apr 4 '18 at 0:03

One counterexample is when $p=31$ and $q=853.$ No partition of $31$ or $33$ yields the prime $q=853.$

For $p\geq 7,$ the only values greater than $(p-2)^2$ you can get from partitions of $p$ are:


This means that $31$ cannot be gotten from a partition of $p=7$, for example.

(This is actually true for $p=5,$ too, which is the underlying reason why $15=(5-2)^2+6$ cannot be reached in your original example.)

If $p\equiv 1,13\pmod{15}$ then $(p-2)^2+2$ is divisible by $3$ and $(p-2)^2+4$ is divisible by $5$, in whch case, any prime between $(p-2)^2$ and $(p-1)^2$ would be a counterexample.

Thus, for $p=13,$ there is no way to partition $13$ to get any of the primes $127, 131, 137,139.$

Allowing also partitions of $p+2$ gives a bunch more values between $(p-2)^2$ and $(p-1)^2, but still a finite list of values.

If we allow partitions of $p$ and $p+2$, for $p\geq 15$, the only values we get strictly between $(p-2)^2$ and $(p-1)^2$ are:


When $p=31,$ $(p-2)^2+12=853$ is not in this set.

If $p\equiv 1\pmod{3}$ and $(p-2)^2\equiv 1\pmod{\cdot 5\cdot 7\cdot 11\cdot 17}$ then all of the above are composite, and thus, if your conjecture were true, we'd have infinitely many $n=p-2$ with no primes between $n^2$ and $(n+1)^2.$ (At the moment is unknown if there exists any such $n$.)

More generally, for fixed $k,$ if you allow partitions of $p,p+2,\dots,p+2k,$ then you can still get, for $p\geq 2k^2+6k+7,$ finitely many values in the range $(p-2)^2$ and $(p-1)^2.$ If these covered all primes, you could find infinitely many $p$ such that there is no prime in that range. (That doesn't mean that it is impossible to find such $k,$ only that finding such $k$ would solve an unsolved problem with a big set of counterexamples.)

In particular, if $p\equiv 1,3\pmod{q}$ for all primes $q<4(k+1)^2,$ then any prime between $(p-2)^2$ and $(p-1)^2$ would be a counterexample.

  • $\begingroup$ Can you please give the name or a link to the unsolved problem you referred to. $\endgroup$ – user25406 Apr 2 '18 at 23:27
  • $\begingroup$ I don’t have a name or link, but it is the question of whether there is always a prime between $n^2$ and $(n+1)^2$ for any integer $n>0.$ $\endgroup$ – Thomas Andrews Apr 2 '18 at 23:34
  • $\begingroup$ link.springer.com/article/10.1007/s000130050469 This link says it is a very hard problem. $\endgroup$ – Thomas Andrews Apr 2 '18 at 23:36
  • $\begingroup$ I was able to produce p=853 by considering the partition of 35 ( not a prime of course). So if we considered the partition of $33$ and $35$, then one of them will not give 853 but the other one will since $29^2+3^2+1+1+1=853$ $\endgroup$ – user25406 Apr 2 '18 at 23:38
  • $\begingroup$ Right, I said $31$ and $33$ won’t give the value 853. Your example doesn’t disprove that. $\endgroup$ – Thomas Andrews Apr 2 '18 at 23:41

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.