問題

本家：Problem 9 - Project Euler
翻訳：Problem 9 - PukiWiki

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは$a < b < c$で以下の式を満たす数の組である.

$$a^2 + b^2 = c^2$$
例えば, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$ である.

$a + b + c = 1000$となるピタゴラスの三つ組が一つだけ存在する.
これらの積$abc$を計算しなさい.

素直に

1000 |
    % {$_} -pv n |
    % { 1..$n} -pv a |
    % {$a..$n} -pv b |
    % {$n - $a - $b} -pv c |
    ? {$a * $a + $b * $b -eq $c * $c} |
    % {$a * $b * $c} |
    select -f 1

原始ピタゴラス数の性質を使って

1000 |
    ? {$_ % 2 -eq 0} |
    % {
        # 入力値を2で割った値の約数を求める
        $x = $_ / 2
        $divisor = 1..[Math]::Floor([Math]::Sqrt($x)) | ? {$x % $_ -eq 0} | % {$_, ($x / $_)} | sort

        # 約数の一つを m と仮定
        foreach ($i in 0..($divisor.length - 1))
        {
            $m = $divisor[$i]

            # n < m を満たす m + n を約数の中から取り、 n の値を仮定
            for ($j = $i + 1; $divisor[$j] -lt 2 * $m -and $i -lt $divisor.length; $j++)
            {
                $n = $divisor[$j] - $m

                # m - n が奇数でない場合、条件に合わないので次の組を探索
                if (($m - $n) % 2 -eq 0)
                    {continue}

                # ユークリッドの互除法により m, n の最大公約数を求める
                $min, $max = $n, $m
                while ($min -gt 0) {$min, $max = ($max % $min), $min}

                # 互いに素であれば、ピタゴラス数を生成し解答を出力
                if ($max -eq 1)
                {
                    $k = $x / ($m * ($m + $n))
                    $a = $k * ($m * $m - $n * $n)
                    $b = $k * (2 * $m * $n)
                    $c = $k * ($m * $m + $n * $n)

                    return $a * $b * $c
                }
            }
        }
    }

ピタゴラス数の性質 - Wikipediaを利用すると上記のプログラムになる。

問題では$a < b$と指定されているが、積$abc$を求めるのにこの大小関係は不要なので無視する。
求めるピタゴラス数の最大公約数を$k$とする。$k = \gcd(a, b, c) \ne 0$。
$a = k a', b = k b', c = k c'$と置くと、 $a^2 + b^2 = c^2$より、$(k a')^2 + (k b')^2 = (k c')^2$なので、両辺$k^2 (\ne 0)$で割れば$a'^2 + b'^2 = c'^2$で、組$(a', b', c')$もやはりピタゴラス数となる。
定義より、$(a', b', c')$は互いに素なので、原始ピタゴラス数である。
原始ピタゴラス数の性質から、$(a', b', c') = (m^2 - n^2, 2 m n, m^2 + n^2)$となる、自然数$m, n$が存在し、$m, n$は下記条件を満たす。
1. $m > n$
2. $m - n$ は奇数
3. $m, n$は互いに素
ここで、$a + b + c = k(m^2 - n^2) + k (2 m n) + k (m^2 + n^2) = 2 k m (m + n)$であるから、$a + b + c = 1000$ より、$k m (m + n) = 500$である。
1. $m, m + n$ は $500$の約数
2. $k = \frac{500}{m (m + n)}$
以上の考察を踏まえて、条件を満たす$m, n$を探索すれば良い。

PowerShell で Project Euler 9

問題

素直に

原始ピタゴラス数の性質を使って