content: {- 
   - Solution to Project Euler problem 218
   - Copyright (c) Project Nayuki. All rights reserved.
   - 
   - https://www.nayuki.io/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
  