Post date: Apr 29, 2018 2:16:3 PM
It's been a while. I've been distracted by javascript so haven't been doing SQL so much. Here's a bit of SQL in JS, though, for fun:
const parent = this.Table.First(q => q.Code == code);
return this.Related
.InnerJoin(
parent.Children,
(r, c) => r.ChildId == c.ChildId,
(r, c) => r)
.Select((q, idx) => { return { Record: q, Index: idx || 0 }; })
.ToArray();
So anyway, problem 94, "Find the sum of the perimeters of all triangles with integral sides where two sides are equal and the third side differs from the other two by exactly one unit, where the perimeters and 1,000,000 or less and the area is an integer."
A triangle with integer sides and integer area is called a Heronian triangle. A Heronian triangle with two sides of the same length is an Isosceles Heronian triangle.
Heron's Formula states that the area is SQRT( s * (s - a) * (s - b) * (s - c) ) or SQRT ( 0.5 (a+b+c) * (0.5 (a+b+c) - a) * (0.5 (a+b+c) - b) * (0.5 (a+b+c) - c) )
It's possible to use this by itself to get several answers, but perimeters up to 1 billion means checking 666 million triangles, which takes too far too long.
Plus, while working on this, I discovered a new SQL server bug, which makes that even harder (but interesting). But it's pointless at these numbers.
An Isosceles Heronian triangle follows these rules:
a = A rational multiple of 2(u*u - v*v)
b = c = A rational multiple of u*u + v*v
u and v are coprime and u > v
We know that the difference between the sides is 1, which gives this equation:
The difference of 2 sides = m * (2u**2 - 2v**2 - u**2 - v**2) = m * (u**2 - 3v**2) = +1 or -1 -> u**2 - 3v**2 = +1/m or -1/m
We know that the eventual difference is plus/minus one but the "multiple of" words break what otherwise would be a simple answer. We know that the multiple is a fraction, and this means that very large numbers could still have a difference of 1, when divided by (say) 1 billion. On research, I found that apparently the only multiples that work are 1 and 0.5. I don't know why. I was unable to come up with justification for skipping 1/n where n is 3 or greater, but I'll use it. It gives Project Euler's correct answer so it seems correct.
It bothers me to continue without finding an explanation (even if it's over my head), but I have limited free time. I'll consider it to be part of the specification.
Because I only need to test two iterations of the Heronian equations, this is pretty short.
-- Perimeter = m * (2u**2 - 2v**2 + 2u**2 + 2v**2) = 4mu**2. This means that u is around the square root of 500 million (m = 0.5). Let's say 25k. That's a much nicer range to work with.
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
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
WHERE k10.i <= 3
)
INSERT INTO #Integers
SELECT i
FROM Integers
WHERE i BETWEEN 10 AND 25000
SELECT u.i AS u, v.i AS v, 1.0 AS m
INTO #Iso
FROM #Integers u, #Integers v
WHERE ABS(u.i * u.i - 3 * v.i * v.i) = 1
AND 4 * u.i * u.i <= 1000000000
INSERT INTO #Iso (u, v, m)
SELECT u.i AS u, v.i AS v, 0.5 AS m
FROM #Integers u, #Integers v
WHERE ABS(u.i * u.i - 3 * v.i * v.i) = 2
AND 2 * u.i * u.i <= 1000000000
-- In this case, the answers happen to be all coprime without me checking them, so I don't need to pull out that function from several problems back.
-- There are less than 20 rows in the table, so it doesn't save us time to filter them out. This makes my answer easier to read.
; WITH Triangles as
(
SELECT a = 2 * m * u * u - 2 * m * v * v, bc = m * u * u + m * v * v
FROM #Iso
)
SELECT SUM(a + bc + bc)
FROM Triangles
WHERE NOT (a = 2 and bc = 1) -- This case is not counted because the angles are either 0 or 180. One side is equal to the other sides put together
AND a > 0
AND bc > 0
DROP TABLE #Iso
DROP TABLE #Integers