Post date: Aug 03, 2014 9:32:10 PM
"How many primes are there below 1 million where all rotations (where you shift the number right and add numbers shifted out onto the left, until you have restored the original number) are also prime?"
CREATE TABLE #Primes (i int not null primary key)
; WITH Ten(i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Ten
WHERE i < 9
),
Integers(i) AS
(
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i) + 1
FROM Ten o
CROSS JOIN Ten d
CROSS JOIN Ten h
CROSS JOIN Ten k
CROSS JOIN Ten k10
CROSS JOIN Ten k100
)
INSERT INTO #Primes (i)
SELECT i
FROM Integers
WHERE i < 1000000
CREATE TABLE #Rotations (
i INT PRIMARY KEY NOT NULL,
i2 INT NOT NULL,
i3 INT NOT NULL,
i4 INT NOT NULL,
i5 INT NOT NULL,
i6 INT NOT NULL
)
-- At this point in time, the #Primes table is just a store of integers.
-- The way we rotate is simple and not that fancy. Just repeat the number a bunch of times, and take a substring at whatever point you need.
-- The end of the string will have the beginning of the number, because it was replicated.
INSERT INTO #Rotations
SELECT i
, SUBSTRING(REPLICATE(CONVERT(varchar(6),i),6),2,LEN(CONVERT(varchar(6),i)))
, SUBSTRING(REPLICATE(CONVERT(varchar(6),i),6),3,LEN(CONVERT(varchar(6),i)))
, SUBSTRING(REPLICATE(CONVERT(varchar(6),i),6),4,LEN(CONVERT(varchar(6),i)))
, SUBSTRING(REPLICATE(CONVERT(varchar(6),i),6),5,LEN(CONVERT(varchar(6),i)))
, SUBSTRING(REPLICATE(CONVERT(varchar(6),i),6),6,LEN(CONVERT(varchar(6),i)))
FROM #Primes
-- Use the Sieve of Eratosthenes to get a table with all the primes.
DELETE FROM #Primes WHERE i < 2
DECLARE @num int = 1
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(1000000)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While Sieve
-- A circular prime is one where each rotation is in the prime table. To make the query easy, I check all six rotations of six digit numbers.
-- Much of this is redundant, because the shorter numbers are rotated back to their original values. That doesn't hurt performance enough to notice.
SELECT COUNT(*)
FROM #Rotations r
INNER JOIN #Primes p1 ON p1.i = r.i
INNER JOIN #Primes p2 ON p2.i = r.i2
INNER JOIN #Primes p3 ON p3.i = r.i3
INNER JOIN #Primes p4 ON p4.i = r.i4
INNER JOIN #Primes p5 ON p5.i = r.i5
INNER JOIN #Primes p6 ON p6.i = r.i6
DROP TABLE #Primes
DROP TABLE #Rotations