Post date: Jul 19, 2015 1:22:12 AM
"Of all right triangles with integer sides and where the total length of all sides is 1.5 million or less, how many total lengths can be formed by only a configuration of sides?"
These triads of numbers are called Pythagorean triples. Euclid's formula generates all primitive pythagorean triples from pairs of integers m and n.
a = m**2 - n**2
b = 2*m*n
c = m**2 + n**2
* A pythagorean triple is made up of either 3 even numbers or 2 odd numbers and 1 even number. Number b is even, so the other two must either be both odd or both even. This means that a and c are either both even or both odd.
* m and n must be coprime, which means that both cannot be even. In addition, m-n must be odd, which means they both cannot be odd. One is even and one is odd.
* We also need to pull out one of our GCD calculations, IsProper, to pull out the few records that are multiples of other records in the list.
CREATE FUNCTION dbo.IsProper(@a int, @b int)
RETURNS BIT
AS
BEGIN
IF @a = 1 OR @b = 1
RETURN 1
ELSE IF @a % @b = 0
RETURN 0
ELSE IF @b % @a = 0
RETURN 0
WHILE 1 = 1
BEGIN
IF @a = 1 OR @b = 1
RETURN 1
ELSE IF @a = @b
RETURN 0
ELSE IF @a % 2 = 0 AND @b % 2 = 0
RETURN 0
ELSE IF @a % 2 = 0
SELECT @a = @a/2
ELSE IF @b % 2 = 0
SELECT @b = @b/2
ELSE IF @b > @a
SELECT @b = (@b - @a)/2
ELSE IF @a > @b
SELECT @a = (@a - @b)/2
END
RETURN 1
END
GO
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers (i) AS
(
SELECT o.i +
10 * d.i +
100 * h.i +
1000 * k.i +
10000 * k10.i +
100000 * k100.i
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
WHERE k100.i <= 1
)
INSERT INTO #Integers
SELECT i
FROM Integers
WHERE i BETWEEN 10 AND 124000
DELETE FROM #Integers WHERE i = 0
-- In Euclid's equation, we find out that the hypotenuse is m**2 + n**2. All sides must be under 1.5 million, which means of course that no single side can be over 1.5 million.
-- If one value is 1, then the other value squared is almost 1.5 million. If we limit the table to 1225 (roughly the square root of 1.5 million), we can cover the biggest value allowed.
CREATE TABLE #Evens (i BIGINT NOT NULL, s BIGINT PRIMARY KEY NOT NULL)
CREATE TABLE #Odds (i BIGINT NOT NULL, s BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Evens
SELECT i, SQUARE(i)
FROM #Integers
WHERE i % 2 = 0
AND i <= 1225
INSERT INTO #Odds
SELECT i, SQUARE(i)
FROM #Integers
WHERE i % 2 != 0
AND i <= 1225
-- Generate our list of primitive triangles (sides are the smallest possible, not multiples of other triangles).
CREATE TABLE #Triangles (a BIGINT NOT NULL, b BIGINT NOT NULL, c BIGINT NOT NULL, s INT NOT NULL)
CREATE INDEX IX_Triangle_S ON #Triangles (s)
; WITH Triangles (a, b, c, m, n) AS
(
SELECT m.s - n.s AS a, 2 * m.i * n.i AS b, m.s + n.s AS c, m.i, n.i
FROM #Evens m
INNER JOIN #Odds n
ON m.s > n.s
WHERE 2 * m.i * n.i <= 1500000
AND m.s + n.s <= 1500000
AND 2 * m.s + 2 * m.i * n.i <= 1500000 -- Sum of all sides <= 1.5 million, simplified from m - n + m + n + 2mn
AND (m.s - n.s) % 2 = (m.s + n.s) % 2 -- Both even or both odd
UNION
SELECT m.s - n.s AS a, 2 * m.i * n.i AS b, m.s + n.s AS c, m.i, n.i
FROM #Odds m
INNER JOIN #Evens n
ON m.s > n.s
WHERE 2 * m.i * n.i <= 1500000
AND m.s + n.s <= 1500000
AND 2 * m.s + 2 * m.i * n.i <= 1500000 -- Sum of all sides <= 1.5 million, simplified from m - n + m + n + 2mn
AND (m.s - n.s) % 2 = (m.s + n.s) % 2 -- Both even or both odd
)
INSERT INTO #Triangles (a, b, c, s)
SELECT a, b, c, a + b + c
FROM Triangles
WHERE dbo.IsProper(m, n) = 1
DROP TABLE #Evens
DROP TABLE #Odds
-- Then we need to worry amount multiples of the primitives. The smallest total is 12, so we need to fill the table up with that one up to 125000 * 12
-- This is time-consuming and there is no shortcut to avoid doing it. However, no items in the list are currently multiples of others.
-- This means we can consider only the sums. For every multiple where the sum is under 1.5 million, that's another length to count for the final answer.
-- Even though the number of rows is almost the same, not keeping track of the a, b, and c values saves a fair amount of time.
-- It is still too big a query to run at once on my machine, which chokes on joining 100k to 100k (10 billion records). So I am still required to step through at a time.
-- This is something that's very fast in C code but which is terrible on SQL. But, as the size of the triangles goes up, the number of multiples whose totals fit under 1.5 million goes down.
-- So after a certain point, a batch query can fill in the rest of the result.
-- The number of primitive triangles where sum times multiplier is under 1.5 million is 100 when the multiplier is over 1000 and a single query is easily able to handle 10 million records.
CREATE TABLE #Sums (s INT PRIMARY KEY NOT NULL, cnt INT NOT NULL)
CREATE TABLE #TempSums (s INT PRIMARY KEY NOT NULL, cnt INT NOT NULL)
DECLARE @b BIGINT = 1
-- Do them one by one for the first 1000
WHILE @b <= 1000
BEGIN
TRUNCATE TABLE #TempSums
-- Not using merge because there are known bugs with temp tables and merge
; WITH Sums (s, cnt) AS
(
SELECT @b * t.s, COUNT(*)
FROM #Triangles t
WHERE @b * t.s <= 1500000
GROUP BY t.s
)
INSERT INTO #TempSums
SELECT *
FROM Sums
UPDATE t
SET cnt = t.cnt + s.cnt
FROM #Sums t
INNER JOIN #TempSums s
ON s.s = t.s
INSERT INTO #Sums
SELECT s, cnt
FROM #TempSums s
WHERE s NOT IN (SELECT s FROM #Sums)
SET @b = @b + 1
-- We can also delete records where the sum times our multiplier is over 1500000. The query itself is fast but not seeing the records at all is even faster.
DELETE FROM #Triangles
WHERE @b * s > 1500000
END
-- Do the rest
SET @b = 1000
TRUNCATE TABLE #TempSums
-- Not using merge because there are known bugs with temp tables and merge
; WITH Sums (s, cnt) AS
(
SELECT (@b + i.i) * t.s, COUNT(*)
FROM #Triangles t
INNER JOIN #Integers i
ON (@b + i.i) * t.s <= 1500000
GROUP BY (@b + i.i) * t.s
)
INSERT INTO #TempSums
SELECT *
FROM Sums
UPDATE t
SET cnt = t.cnt + s.cnt
FROM #Sums t
INNER JOIN #TempSums s
ON s.s = t.s
INSERT INTO #Sums
SELECT s, cnt
FROM #TempSums s
WHERE s NOT IN (SELECT s FROM #Sums)
SELECT COUNT(*) FROM #Sums
WHERE cnt = 1
DROP TABLE #Integers
DROP TABLE #Triangles
DROP TABLE #Sums
DROP TABLE #TempSums
GO
DROP FUNCTION dbo.IsProper
GO