A horrendous sieve with potentially terrific consequences

295 Views Asked by At

Sieves are useful when you can't concisely formulate what something is, but you can readily denote what it is not. For example, there is no concise formula that generates every prime number, but there are sieves that eliminate every composite number, accomplishing the desired result by indirection.

The sieve of Sundaram is premised on the fact that no odd prime number can be expressed as the product of two odd factors. $$\forall (a,b,m) \in \mathbb N, \ (2m+1) \in \mathbb P:\ 2m+1 \ne (2a+1)(2b+1) \Rightarrow m \ne 2ab+a+b$$ Simply discard natural numbers of the form $2ab+a+b$ and the remaining whole numbers can be multiplied by $2$ and incremented by $1$ to yield every odd prime.

There is no reason this logic cannot be extended to provide a sieve for odd semiprimes, which are simply odd composites that cannot be expressed as the product of three odd factors. $$\forall (a,b,m) \in \mathbb N, \ (2m+1) \not\in \mathbb P:\ 2m+1 \ne (2a+1)(2b+1)(2c+1) \Rightarrow m \ne 4abc+2(ab+bc+ac)+a+b+c$$ This sieve might be implemented by first performing the sieve of Sundaram, but keeping only those numbers of the form $2ab+a+b$ (i.e. values of $m$ that will generate composite $2m+1$), and then sieving a second time, discarding numbers of the form $4abc+2(ab+bc+ac)+a+b+c$. I think that this approach is sufficiently obvious that it likely has been thought of before. Perhaps others who have conceived of it, like me, were impressed with the horrendous explosion of possibilities that flow from a complicated term in three variables.

The ability to identify semiprimes has relevance to the twin prime conjecture (the product of twin primes is a semiprime) and to Goldbach's conjecture, which posits every sufficiently large even number can be separated into one or more pairs of two prime addends; the product of such addends would be a semiprime. The objective would be to prove that there are always products of twin numbers (i.e. $d$ and $d+2$) or odd addends of even numbers that could not have the form $(2a+1)(2b+1)(2c+1)$, by showing that when such products are stated in the form $2m+1$, the resulting expression for $m$ cannot be expressed as $4abc+2(ab+bc+ac)+a+b+c$. As I said in the title, horrendous sieve, but potentially very significant consequences.

I have been thinking about this for some time, without much progress. It might be that the unwieldiness of the sieve defeats my limited skills, or, that the approach is doomed in light of deeper considerations. Perhaps others might be spurred to some insight that as yet eludes me.

My questions are: Is this sieve for semiprimes an old idea? Are there other known sieving methods that yield semiprimes (all or only odd)?