# Is it possible to use partitions of an odd integer to generate primes in a given interval?

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

• 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. :) – Thomas Andrews Apr 2 '18 at 15:10
• 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.$ – Thomas Andrews Apr 2 '18 at 15:15
• 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\}$. – Hagen von Eitzen Apr 2 '18 at 15:40
• Yes, but we don't get all the primes in that interval as Thomas Andrews proved in his answer below. – 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:

$$(p-2)^2+2,(p-2)^2+4,(p-1)^2+1$$

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: $$(p-2)^2+2,\\(p-2)^2+4,\\(p-2)^2+6,\\(p-2)^2+8,\\(p-2)^2+10,\\(p-2)^2+16.$$ 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. • Can you please give the name or a link to the unsolved problem you referred to. – user25406 Apr 2 '18 at 23:27 • 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.$– Thomas Andrews Apr 2 '18 at 23:34 • link.springer.com/article/10.1007/s000130050469 This link says it is a very hard problem. – Thomas Andrews Apr 2 '18 at 23:36 • 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$– user25406 Apr 2 '18 at 23:38 • Right, I said$31$and$33\$ won’t give the value 853. Your example doesn’t disprove that. – Thomas Andrews Apr 2 '18 at 23:41