Post date: Jun 28, 2014 1:13:55 AM
"For the quadratic equation n**2 + an + b = prime, what are the values of a and b that produce the greatest number of consecutive prime numbers for values of n from 0 ... max, if the absolute values of a and b are under 1000. Get a * b so it can be typed into the web form."
"Solving quadratic equations" would be a perfect example of "things SQL was not designed for." So this is a groovy problem. The key here is that the equation must produce a prime for n = 0, which means 0 + 0 + b = prime, or b = prime. Because all prime numbers are greater than 1, this also means b is not negative number.
-- The number of primes here is so small that I probably could have used a simple exists clause without adding too many seconds on to the time. But I already have this code sitting around, so...
CREATE TABLE #Primes (i INT PRIMARY KEY NOT NULL)
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
; WITH Ten(i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Ten
WHERE i < 9
)
INSERT INTO #Integers
SELECT 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM Ten o
CROSS JOIN Ten t
CROSS JOIN Ten h
CROSS JOIN Ten k
-- Smaller divisors table
CREATE TABLE #Divisors (i int not null primary key clustered)
INSERT INTO #Divisors
SELECT i
FROM #Integers
WHERE i % 2 != 0
AND i > 2
AND i < SQRT(9999) + 1
;WITH NotPrimes(i) AS
(
-- Numbers divisible by 2 (other than 2)
SELECT i.i
FROM #Integers i
WHERE i.i > 2
AND i % 2 = 0
UNION
-- Numbers divisible by any number
SELECT i.i
FROM #Integers i
CROSS APPLY
(
SELECT 1 AS notprime
FROM #Divisors d
WHERE i.i % d.i = 0
AND d.i <= SQRT(i.i) + 1
) notprime
WHERE i.i > 2
),
Primes (i) AS
(
SELECT i
FROM #Integers
WHERE i >= 2
EXCEPT
SELECT i
FROM NotPrimes
WHERE i > 3
)
INSERT INTO #Primes
SELECT i
FROM Primes
-- These were only there to calculate the primes so delete them. The problem is not concerned with numbers over 1000.
DELETE FROM #Integers
WHERE i >= 1000
-- Add negatives, for a
INSERT INTO #Integers
SELECT -1 * i
FROM #Integers
WHERE i > 0
-- Find solutions with a basic where clause.
-- Include an incrementing row number. When this becomes different from n, the variable, a prime has been skipped.
; WITH Stats (b, c, n, ctr) AS
(
SELECT b.i, c.i, n.i, ROW_NUMBER() OVER (PARTITION BY b.i, c.i ORDER BY n.i) - 1
FROM #Primes p
CROSS JOIN #Integers n
CROSS JOIN #Integers b
CROSS JOIN #Integers c
WHERE SQUARE(n.i) + b.i * n.i + c.i = p.i -- Equation
AND n.i >= 0 -- n from 0 to max
AND c.i > 1 -- c is not negative
AND EXISTS (SELECT 1 FROM #Primes p2 WHERE p2.i = c.i) -- c is prime
)
SELECT b, c, COUNT(*) AS cnt
INTO #Solutions
FROM Stats
WHERE n = ctr
GROUP BY b, c
SELECT TOP (1) b, c, b * c
FROM #Solutions
ORDER BY cnt DESC
DROP TABLE #Integers
DROP TABLE #Primes
DROP TABLE #Solutions
DROP TABLE #Divisors