Post date: Nov 04, 2014 1:32:59 AM
"Find the lowest number in a group of numbers where, if you replace the same static positions in every string with a single digit, produces eight numbers that are all prime."
So here we have string masking and replacement being joined with a list of primes. There weren't any clues to the maximum size of the results, so I took a guess that it would be under 9 digits. If I hadn't come up with any results, I would have had to try again with more.
I'll define my masks as strings of 1s and NULLs. 1 multiplied by a digit is the digit, while NULL multiplied by the digit is NULL. Put an ISNULL around that and you have a simple replacement.
CREATE TABLE #Mask (
k100 int null
, k10 int null
, k int null
, h int null
, d int null
, o int null
)
; WITH Bits (b) AS
(
SELECT 0 UNION SELECT 1
)
INSERT INTO #Mask (k100, k10, k, h, d, o)
SELECT CASE k100.b WHEN 1 THEN NULL ELSE 1 END AS k100
, CASE k10.b WHEN 1 THEN NULL ELSE 1 END AS k10
, CASE k.b WHEN 1 THEN NULL ELSE 1 END AS k
, CASE h.b WHEN 1 THEN NULL ELSE 1 END AS h
, CASE d.b WHEN 1 THEN NULL ELSE 1 END AS d
, CASE o.b WHEN 1 THEN NULL ELSE 1 END AS o
FROM Bits o
CROSS JOIN Bits d
CROSS JOIN Bits h
CROSS JOIN Bits k
CROSS JOIN Bits k10
CROSS JOIN Bits k100
-- In addition to calculating primes, we store their digits separately. Quicker to do it now than in the main query.
CREATE TABLE #Primes (i int not null primary key
, k100 int not null default 0
, k10 int not null default 0
, k int not null default 0
, h int not null default 0
, d int not null default 0
, o int not null default 0
)
INSERT INTO #Primes (i, o) VALUES (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)
; WITH Integers AS
(
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i) AS i
, k100.i AS k100
, k10.i AS k10
, k.i AS k
, h.i AS h
, d.i AS d
, o.i AS o
FROM #Primes o
CROSS JOIN #Primes d
CROSS JOIN #Primes h
CROSS JOIN #Primes k
CROSS JOIN #Primes k10
CROSS JOIN #Primes k100
)
INSERT INTO #Primes (i, k100, k10, k, h, d, o)
SELECT i, k100, k10, k, h, d, o
FROM Integers
WHERE i >= 10
-- Delete 1 and 0
DELETE FROM #Primes WHERE i < 2
DECLARE @max int
SELECT @max = MAX(i) FROM #Primes
DECLARE @num int = 1
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(@max)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
CREATE TABLE #Digit (d int not null primary key)
INSERT INTO #Digit (d) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH MaskedPrimes AS
(
SELECT p.i AS prime
-- These columns are just here for grouping.
-- It makes sure that all the numbers we count have the same result for "56nn3" for example, for whatever value of n.
, p.k100 * m.k100 AS k100
, p.k10 * m.k10 AS k10
, p.k * m.k AS k
, p.h * m.h AS h
, p.d * m.d AS d
, p.o * m.o AS o
FROM #Primes p
-- Join to the mask, but make sure you aren't masking digits to the left of the number (zeros).
-- Otherwise, you will get false positives.
INNER JOIN #Mask m
ON (LEN(p.i) >= 6 OR m.k100 IS NOT NULL)
AND (LEN(p.i) >= 5 OR m.k10 IS NOT NULL)
AND (LEN(p.i) >= 4 OR m.k IS NOT NULL)
AND (LEN(p.i) >= 3 OR m.h IS NOT NULL)
AND (LEN(p.i) >= 2 OR m.d IS NOT NULL)
-- Filter the list to get only numbers where the replaced part is always the same digit.
-- Only include results where, if you replace NULL with the same digit from #Digit, it matches a prime
INNER JOIN #Digit d
ON 100000 * ISNULL(p.k100 * m.k100,d.d) +
10000 * ISNULL(p.k10 * m.k10,d.d) +
1000 * ISNULL(p.k * m.k,d.d) +
100 * ISNULL(p.h * m.h,d.d) +
10 * ISNULL(p.d * m.d,d.d) +
ISNULL(p.o * m.o,d.d) = p.i
)
SELECT MIN(prime)
FROM MaskedPrimes
GROUP BY k100, k10, k, h, d, o
HAVING COUNT(DISTINCT prime) = 8
DROP TABLE #Primes
DROP TABLE #Mask
DROP TABLE #Digit