94問目
http://projecteuler.net/index.php?section=problems&id=94
辺の長さも面積も整数となるような正三角形は存在しないが、5-5-6 のような似非正三角形であれば、面積は 12 で整数となる。
このように辺の長さが1つだけ(長さ 1 以内で)異なる似非正三角形のうち条件を満たすものを、周の長さが十億を超えない範囲で全て求め、その周の長さの合計を答える。
brute force だと結構つらいので、ピタゴラス数を生成する式を使います。そのまま使うと結局 brute force になってしまいますが、11 行目の制約条件がポイントで、条件を満たすピタゴラス数の後続だけを調べることにより、探索範囲がぐっと小さくなります。
main = print $ euler094 1000000000 euler094 :: Integer -> Integer euler094 m = sum $ map perim $ pytha m (3,4,5) pytha :: Integer -> (Integer, Integer, Integer) -> [(Integer, Integer, Integer)] pytha m (a, b, c) = (a, b, c) : concat [ pytha m (a', b', c') | (a', b', c') <- [(a-2*b+2*c, 2*a-b+2*c, 2*a-2*b+3*c), -- (a+2*b+2*c, 2*a+b+2*c, 2*a+2*b+3*c), (-a+2*b+2*c, -2*a+b+2*c, -2*a+2*b+3*c)], abs (c' - 2 * min a' b') == 1, perim (a', b', c') <= m ] perim :: (Integer, Integer, Integer) -> Integer perim (a, b, c) = 2 * (min a b + c)
で、もう一つ、この問題は不定方程式と捉えることもできます。直角三角形 a-b-c について c=2a±1 を満たすものを求めればよいので、
a2+b2 = (2a±1)2
x=3a±2, y=b とおくと
x2-3y2 = 1 でペル方程式そのものになります。
最小解 (x1, y1) = (2, 1) で、
xn+yn√3 = (2+√3)n なので、
(xn+1, yn+1) = (2x1+3y1, x1+2y1)
最小解のときは三角形が成立しないので除いて、あとは辺の長さに直すだけです。
main = print $ euler094 1000000000 euler094 :: Integer -> Integer euler094 m = sum $ takeWhile (<= m) $ map (perim . pytha) $ iterate pell (7, 4) perim :: (Integer, Integer, Integer) -> Integer perim (a, b, c) = 2 * (a + c) pytha :: (Integer, Integer) -> (Integer, Integer, Integer) pytha (x, y) = (a, b, c) where a = div (if mod x 3 == 2 then x-2 else x+2) 3 b = y c = div x 3 * 2 + 1 pell :: (Integer, Integer) -> (Integer, Integer) pell (x, y) = (2*x+3*y, x+2*y)