[Python][Julia]Project euler9 (プロジェクトオイラー9)

Project euler Ploblem 9 (プロジェクトオイラー9)

Special Pythagorean Triplet

備忘のために残しておく。

問題

問題文 (意訳)

ピタゴラスの三つ組数は　3つの自然数のセットであり、a<b<cの場合、

\begin{align}
a^2 + b^2 &= c^2 \ \\
\end{align}

となる。
a + b + c = 1000　となるピタゴラスの三つ組数は一つ存在する。
積abcを求めよ。

原文

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

\begin{align}
a^2 + b^2 &= c^2 \ \\
\end{align}

For example,

\begin{align}
3^2 + 4^2 = 9 + 16 = 25 =  5^2 .
\end{align}

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

解答

答え

31875000

解答の方針

式変形して、cを消去してから、a,bの成り立つ組を求める。

\begin{align}
a^2 + b^2 &= c^2 \ \\
a + b + c &= 1000 \\
\end{align}

なので、

(a + b)^2 = (1000 - c)^2 \ \\

となって、式変形すると

\begin{align}
a^2 + b^2 + 2ab&= 10^6 - 2000c + c^2 \ \\
0 &= - ab - 1000×(1000- a - b) + 5×10^5  \\
0 &= ab - 1000×(a + b) + 5×10^5  \\

\end{align}

この式が成り立つa,bを探し、a×b×(1000-a-b)を計算する。

Pythonのコード

Python Ploblem9

def formula(a, b):
    return a*b-1000*(a + b)+500000

def seek_ans():
    ans = 1
    for a in range(1,1000):
        for b in range(a + 1, 1000):
            if formula(a, b) == 0:
                ans = a * b * (1000 - (a + b))
                break
        else: continue
        break
    return ans

print(seek_ans())

Juliaのコード

Julia Ploblem9

function formula(a, b)
    return a*b-1000*(a + b)+500000
end

function seek_ans()
    ans = 1
    flg = false
    for a in range(1,1000)
        for b in range(a + 1, 1000)
            if formula(a, b) == 0
                ans = a * b * (1000 - (a + b))
                flg = true
                break
            end
        end
        if flg
            return ans
        end
    end
end
print(seek_ans())