p218.hs

{- 
 - Solution to Project Euler problem 218
 - By Nayuki Minase
 - 
 - http://nayuki.eigenstate.org/page/project-euler-solutions
 - https://github.com/nayuki/Project-Euler-solutions
 -}


{- 
 - == Primitive Pythagorean triples ==
 - 
 - Each valid pair generates a PPT:
 - 
 -   For each pair of positive integers (s,t) such that s > t, they are coprime, and one of them
 -   is odd and one of them is even: Let a = s^2 - t^2 (odd), b = 2st (even), and c = s^2 + t^2 (odd).
 -   Then (a,b,c) is a primitive Pythagorean triple (PPT).
 - 
 -   Proof: The fact that a^2 + b^2 = c^2 can be readily verified. Now for the sake of contradiction,
 -   suppose some prime p divides each of {a,b,c} (which would make the Pythagorean triple non-primitive).
 -   Since p divides b = 2st and p is prime, p must divide at least one of {2,s,t}. a is odd, so 2 doesn't
 -   divide a, so p != 2. Hence p > 2, and p must divide at least one of {s,t}. p divides c = s^2 + t^2.
 -   WLOG if p divides s, then p divides the difference c - s^2 = t^2, thus p divides t.
 -   Therefore p divides {s,t}, contradicting that {s,t} are coprime.
 - 
 - Each PPT can be generated from some valid pair:
 - 
 -   Conversely, for each PPT (a,b,c) there exists an (s,t), satisfying the restrictions above,
 -   that generates it using the relations above.
 - 
 -   Proof: WLOG assume that a is odd (otherwise swap the roles of a and b). Knowing that a^2 + b^2 = c^2
 -   and b is even, rearrange it to get (b/2)^2 = (c^2 - a^2)/4 = [(c-a)/2][(c+a)/2]. The claim is that
 -   (c-a)/2 and (c+a)/2 are both perfect squares. For any prime p, if it divides both (c-a)/2 and (c+a)/2,
 -   then it divides the sum (which is c) and the difference (which is a), so it would also divide c^2 - a^2 = b^2,
 -   contradicting the primitiveness. Thus each prime power (i.e. p^k) in the factorization of (b/2)^2 appears
 -   in either the factor (c-a)/2 or the factor (c+a)/2. Since (b/2)^2 is a perfect square, each prime power
 -   in it is a perfect square, and it would contribute to either (c-a)/2 or (c+a)/2, making both of them
 -   perfect squares as well.
 - 
 -   With this setup, let s = sqrt((c+a)/2) and t = sqrt((c-a)/2), which are both positive integers.
 -   It's easy to verify that a = s^2 - t^2, b = 2st, and c = s^2 + t^2. Clearly s > t, since a is added in s
 -   while a is subtracted in t. {s,t} cannot both be even or both be odd, otherwise 2 divides all of {a,b,c},
 -   contradicting primitiveness. {s,t} must be coprime, otherwise some p divides {s,t}, so p^2 divides s^2 = (c+a)/2
 -   and p^2 divides t^2 = (c-a)^2, which contradicts {a,c} being coprime using the argument above.
 - 
 - 
 - == Perfect triangles ==
 - 
 - A perfect right-angled triangle (a,b,c) has c = r^2 for some integer r. We use the PPT theorem converse
 - to find (s,t). The area of the triangle (a,b,c) is ab/2 = (s^2 - t^2)(2st)/2 = st(s^2 - t^2).
 - Curiously, we have c = s^2 + t^2 = r^2, which means (s,t,r) is itself a Pythagorean triple, and in fact
 - a primitive one because (s,t) are coprime. Use the PPT theorem converse on (s,t,r) (or (t,s,r), depending on
 - which of s or t is odd) to find (u,v), i.e. s = u^2 - v^2, t = 2uv, and r = u^2 + v^2.
 - So the area is also expressible as (u^2 - v^2)(2uv)[(u^2 - v^2)^2 - (2uv)^2].
 - 
 - The area is divisible by 6 and 28 (super-perfectness) iff it is divisible by lcm(6, 28) = 84
 - = 3 * 4 * 7 (coprime factorization) iff it is divisible by 3, 4, and 7.
 - Now, the area is divisible by 4 because in the factor 2uv, either u or v is even.
 - The area is divisible by 3 because st is a factor in one of the area formulas, and with (s,t,r) being
 - a Pythagorean triple, at least one of {s,t} must be 0 mod 3 (see footnote 0).
 - Similarly, since (s,t,r) is a Pythagorean triple, 7 divides at least one of {s,t} (so 7 divides
 - the area factor of st), or s^2 = t^2 mod 7 (so 7 divides the area factor s^2 - t^2) (see footnote 1).
 - 
 - In conclusion, every perfect right-angled triangle is also super-perfect.
 - There is no perfect triangle that isn't super-perfect.
 - 
 - Footnote 0: This can be proven by brute force over the 3^3 cases of values of s,t,r mod 3.
 - Or alternatively: If s or t is 0 mod 3, then we're done. Otherwise, s is either 1 or 2 mod 3,
 - and t is either 1 or 2 mod 3. s^2 = 1 mod 3, and t^2 = 1 mod 3. s^2 + t^2 = 2 = r^2 mod 3,
 - but no r can satisfy r^2 = 2 mod 3. So this "otherwise" case is impossible.
 - 
 - Footnote 1: This can also be proven by brute force over all 7^3 cases of values of s,t,r mod 7.
 - Or alternatively: If s or t is 0 mod 7, then we're done. Otherwise, notice that for k != 0 mod 7,
 - we have that k^2 mod 7 is in the set {1,2,4} (quadratic residues). If s^2 != t^2 mod 7,
 - then their sum mod 7 is not a residue, so r^2 != s^2 + t^2. Therefore it must be that s^2 = t^2 mod 7
 - (e.g. s = 3 mod 7, t = 4, r = 2 mod 7).
 -}
main = putStrLn (show ans)
ans = 0