In this thread:
I posted (re-)discovering an interesting pattern in the distribution of prime numbers…that primes larger than 2 and 3 are of the form 6X+1 and 6X-1.
Of course, not all in those two columns are primes, such as 25 and 49.
Somebody in this forum:
claims to have taken it a step further (if I’m reading his post correctly):
Call 6X+1 AND 6X-1 list A
List A * list A= list B (can also be written as 6XA+A AND 6XA-A)
List A-List B= all primes 5 and larger.
Does this hold true?
I read this quickly, but depending on what he means by “List A * list A” it sure sounds like just the most complicated way I’ve ever heard of specifying the Sieve of Eratosthenes: If you take the list of all numbers > 1, and subtract out all the multiples of each prime you find, in order, all that’s left are the primes.
Which is, if you think about it, pretty much just a straightforward application of the definition of prime numbers.
If, on the other hand, we parse “List A - List B” to mean “Take any given member of List A, and subtract off any given member of List B”, then one counterexample would be (616-1) - ((61+1)(61-1)) = 95 - 35 = 60, which is not prime.
Why would you parse it that way?
That’s not what he means, though – he’s saying remove from list A those items that appear in list B.
It does indeed work. Basically, list A is a list of numbers that aren’t divisible by 2 or 3. Those that aren’t prime can be written as the product of two factors, but those factors also won’t be divisible by 2 or 3. Therefore the non-prime elements of A can be written as the product of two (not necessarily distinct) elements of A, and removing these leaves only the primes.
But just because it works doesn’t mean it’s particularly useful. For one thing, the procedure as stated involves taking all possible products of two elements from an infinite list of numbers. I’m not seeing how this is an improvement on the Sieve of Eratosthenes described in the first reply.
Yep, List A just has all the primes (plus assorted non-primes) >=5. List B is just a brute force way of finding those assorted non-primes. Not particularly any better than the Sieve of Eratosthenes which has the added benefit of being more comprehensible.
Because parsing it the other way is boring and doesn’t actually make it any easier to find primes, as others have noted.
Since Chronos is already bored, I’ll mention that your pattern can be generalized.
Primes larger than 5 are of the form 30N +/-1, 30N +/- 7, 30N +/- 11, or 30N +/- 13. That’s about 26.67 percent of the 30 possibilities, compared with 33.33 percent when using 6N +/- 1 (in case you want to improve the efficiency of your sieve).
Primes larger than 7 are of the form 210 +/- 1, 210 +/- 11, …, 201 +/- 103. About 22 percent of the possibilities.