The other day I was reading something on Hackernews and someone posted a link to a Sexy Primes wikipedia article. I looked at that and then decided to do this in SQL Server because.. why not?
From that wikipedia link: https://en.wikipedia.org/wiki/Sexy_prime
In mathematics, sexy primes are prime numbers that differ from each other by six. For example, the numbers 5 and 11 are both sexy primes, because 11 minus 5 is 6.
The term "sexy prime" is a pun stemming from the Latin word for six: sex.
If p + 2 or p + 4 (where p is the lower prime) is also prime, then the sexy prime is part of a prime triplet.
Ok I did a couple of versions of this over the weekend, I also did a PostgreSQL version: Calculating Sexy Primes, Prime Triplets and Sexy Prime Triplets in PostgreSQL
So first we need a table that will just have the prime numbers
I decided to populate a table with numbers from 2 till 500 and then use the sieve of Eratosthenes method to delete the non primes
This will look like this
CREATE TABLE #PrimeNumbers(n int) INSERT INTO #PrimeNumbers SELECT number FROM master..spt_values WHERE type = 'P' AND number between 2 and 500 --Sieve method DECLARE @i INT SET @I = 2 WHILE @I <= SQRT(500) BEGIN DELETE FROM #PrimeNumbers WHERE N % @I = 0 AND N > @I SET @I = @I + 1 END SELECT * FROM #PrimeNumbers
Thinking about it a little more I decided to do it with a CTE instead of a loop with delete statements, if your tables will be big then the delete method is probably better... it's for you to test that out :-)
What we are doing is a NOT EXISTS query against the same cte and we are filtering out numbers that are greater than the number in the current row and are not divisible by the current number
IF OBJECT_ID('tempdb..#PrimeNumbers') IS NOT NULL DROP TABLE #PrimeNumbers CREATE TABLE #PrimeNumbers(n int) ;WITH cte AS ( SELECT number n FROM master..spt_values WHERE type = 'P' AND number between 2 and 500 ), PrimeNumbers as ( SELECT n FROM cte WHERE NOT EXISTS ( SELECT n FROM cte as cte2 WHERE cte.n > cte2.n AND cte.n % cte2.n = 0) ) INSERT #PrimeNumbers SELECT * FROM PrimeNumbers SELECT * FROM #PrimeNumbers
If we run that last select statement, we should have 95 rows
2
3
5
7
.....
.....
463
467
479
487
491
499
Now that we have our table filled with prime numbers till 500, it's time to run the queries
Sexy prime pairs
The sexy primes (sequences OEIS: A023201 and OEIS: A046117 in OEIS) below 500 are:
(5,11), (7,13), (11,17), (13,19), (17,23), (23,29), (31,37), (37,43), (41,47), (47,53), (53,59), (61,67), (67,73), (73,79), (83,89), (97,103), (101,107), (103,109), (107,113), (131,137), (151,157), (157,163), (167,173), (173,179), (191,197), (193,199), (223,229), (227,233), (233,239), (251,257), (257,263), (263,269), (271,277), (277,283), (307,313), (311,317), (331,337), (347,353), (353,359), (367,373), (373,379), (383,389), (433,439), (443,449), (457,463), (461,467).
Here is that query for the sexy prime pairs
-- 46 rows.. sexy primes SELECT t1.N,t2.N FROM #PrimeNumbers t1 join #PrimeNumbers t2 on t2.N - t1.N = 6 order by 1
It's very simple.. a self join that returns rows where the number from one table alias and the number from the other table alias differ by 6Prime triplets
The first prime triplets below 500 (sequence A098420 in the OEIS) are
(5, 7, 11), (7, 11, 13), (11, 13, 17), (13, 17, 19), (17, 19, 23), (37, 41, 43), (41, 43, 47), (67, 71, 73), (97, 101, 103), (101, 103, 107), (103, 107, 109), (107, 109, 113), (191, 193, 197), (193, 197, 199), (223, 227, 229), (227, 229, 233), (277, 281, 283), (307, 311, 313), (311, 313, 317), (347, 349, 353), (457, 461, 463), (461, 463, 467)
A prime triplet contains a pair of twin primes (p and p + 2, or p + 4 and p + 6), a pair of cousin primes (p and p + 4, or p + 2 and p + 6), and a pair of sexy primes (p and p + 6).
So we need to check that the 1st and 3rd number have a difference of 6, we also check that that difference between number 1 and 2 is 2 or 4. That query looks like this
-- 22 rows.. Prime Triplets SELECT t1.N AS N1,t2.N AS N2, t3.N AS N3 FROM #PrimeNumbers t1 join #PrimeNumbers t2 on t2.N > t1.N join #PrimeNumbers t3 on t3.N - t1.N = 6 and t3.N > t2.N and t2.n - t1.n IN (2,4) order by 1
Sexy prime triplets
Triplets of primes (p, p + 6, p + 12) such that p + 18 is composite are called sexy prime. p p, p+6 and p+12 are all prime, but p+18 is not
Those below 500 (sequence OEIS: A046118) are:
(7,13,19), (17,23,29), (31,37,43), (47,53,59), (67,73,79), (97,103,109), (101,107,113), (151,157,163), (167,173,179), (227,233,239), (257,263,269), (271,277,283), (347,353,359), (367,373,379)
The query looks like this.. instead of a self join, we do a triple self join, we also check that p + 18 is not a prime number in the line before the order by
-- 14 rows.. Sexy prime triplets SELECT t1.N AS N1,t2.N AS N2, t3.N AS N3 FROM #PrimeNumbers t1 join #PrimeNumbers t2 on t2.n - t1.n = 6 join #PrimeNumbers t3 on t3.N - t1.N = 12 and t3.N > t2.N AND NOT EXISTS( SELECT null FROM #PrimeNumbers p WHERE p.n = t1.n +18) order by 1
And that's it for this post.
1 comment:
I wonder if replacing:
t2.N - t1.N = 6
with:
tn.N + 6 = t1.N
would let the query use an index?
Post a Comment