Lehs conjectured here that $\forall \ n>2\in \mathbb N,\exists\ a,b\in \mathbb N$ such that $a+b=n\land (a+ab+b)\in \mathbb P$. In comments, Crostul restated this as $\forall \ n\ge 4\in \mathbb N, \exists \ A,B\ge 2\in \mathbb N$ such that $A+B=n\land (AB-1)\in \mathbb P$. I found the Crostul formulation more amenable to computation.

It is apparent that as $n$ increases in size, the number of ways to partition $n$ into two addends also increases, and for some values of $n$, there may be multiple ways to choose addends whose product is $1$ greater than a prime. It should be noted that if $n$ is odd, the two addends will be of different parity, whereas if $n$ is even, the two addends will be of the same parity.

I computed the number of ways that $AB-1$ can be prime for $4\le n\le 24$. Note that in general, at least one of $A,B$ must be even to ensure $AB-1$ will be odd. However, in the sole case of $4$, we see that $1\cdot 3-1=2$, the sole even prime. The number of different $A,B$ pairs that provide primes by the formula $AB-1$ for each value of $n$ starting with $4$ are: $$2,2,1,2,1,4,1,3,2,3,2,3,2,4,3,5,1,10,1,5,5$$ This sequence is found at OEIS 109909, and Crostul's formulation of Lehs' conjecture is stated in the comments to that sequence.

Interestingly, $4,\ 5\ \text{and}\ 21$ yield a prime for every possible set of addends.

First question: Are there larger numbers which similarly exhaust every possibility? There are none others in the $93$ terms listed in OEIS 109909. If any exist, they cannot be even, as even numbers can be partitioned into two odd addends, whose product less one would be even and hence not prime.

It also seems that certain numbers only provide a single partition yielding a prime. The largest number giving a single partition in OEIS 109909 is $40$: $16\cdot 24-1=383$.

Second question: Is there a $n_0$ above which there will always be more than one prime-yielding partition?

A plot of the number of obtainable primes versus $n$ might yield a comet-like graph (such as is seen with respect to the number of Goldbach partitions of $2n$). Such a graph might reveal or suggest interesting or important behaviors of this relationship.

Third question: Does anyone in the community have the programming and graphing skills (and of course, interest) to generate such a plot? If so, would you put it in an answer to this question, please?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.