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

244 Views Asked by At

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

1

There are 1 best solutions below

6
On BEST ANSWER

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.