CodeIQ の「今週のアルゴリズム：ピタゴラス数」について

この記事は、結城浩（@hyuki）氏著の「数学ガール フェルマーの最終定理」↓を読んでいれば既知の内容ばかりなので、興味の無い方は読み飛ばしていただいて構いません。

数学ガール フェルマーの最終定理 (数学ガールシリーズ 2)

CodeIQ のアルゴリズム問題「今週のアルゴリズム：ピタゴラス数（先日締切）」を解いたのですが、その解説記事（「第1回「今週のアルゴリズム：ピタゴラス数」解説 #ruby #javascript｜CodeIQ MAGAZINE」）の一部に、なんか「極めてないな感」を覚えてしまったのでカッとなって記事を書きます。
ポイントは、「互いに素の判定」。

最後に、私の提出した解答コードも掲載ます。

原始ピタゴラス数

そもそも元の問題文に

ピタゴラス数はa²+b²=c², a < b < cを満たす自然数で互いに素である組とし…

とか書いてる時点で違和感を感じていたんです。

数学的には普通、ピタゴラス数と言えば
「a²+b²=c² を満たす自然数」
という定義です。
定義中に「互いに素」は含まれません（ついでに「a＜b＜c」も定義には含まれていません）。つまり「6, 8, 10」や「25, 60, 65」などのように、3つの数に公約数（＞1）が存在する（＝互いに素ではない）組合せも数学的にはピタゴラス数です。
「ピタゴラス数は互いに素なものである」と言うのは、例えるなら「法律で定められた休日は国民の祝日だけである」と言っているようなモノです（実際には振替休日や国民の休日（祝日と祝日に挟まれた日など）も法律で定められています）。

それと区別するために、特に互いに素なものを対象としたい場合には、「互いに素なピタゴラス数」と言っていただければまだ許せます。
でも（これは知識がなければ知らなくても仕方ありませんが）互いに素なピタゴラス数には特別な呼び方があります。
その一つが「原始ピタゴラス数」です。
（その意味は ピタゴラス数|Wikipedia にも載っているのでここでは割愛します）

だから個人的には元の問題文は、

ピタゴラス数はa²+b²=c² を満たす自然数（ただし本問では、a＜b＜c とし、互いに素である組のみを対象とします）とし…

とか

対象となるピタゴラス数は 原始ピタゴラス数（すなわち a²+b²=c² を満たす自然数で互いに素である組）で、a＜b＜c とし…

とかっていう風に書いて欲しかったです。

数学では定義が大事ですから。既にある定義を勝手に拡張したり制限したりしちゃダメです。

互いに素の判定

解説記事に、こんな風に書かれています。

また、今回は3つの数が互いに素かどうかを判定する必要がありますが、これは2つの数の最大公約数と、残りの1つの数との最大公約数を求めればOKです。

はい、普通のその辺に転がっている3つの数の組なら、これで間違いではありません。でも実はこれ、ピタゴラス数が相手だと少し無駄があります。なぜなら
「ピタゴラス数の3つの数のうち、2つが互いに素ならば、3つの数は互いに素（＝原始ピタゴラス数）である」
だからです。
記憶に間違いが無ければこの内容も、先述の「数学ガール フェルマーの最終定理」に載っていたと思います。
私の記憶違いで載っていなかったとしても、簡単に証明できます。
概要（というか厳密でない証明）を示すと、こんな感じ。

1. ピタゴラス数 a, b, c（a＜b＜c）のうち、aとbが互いに素でない（2以上の公約数 d が存在する）と仮定する。
2. a=a₀×d、b=b₀×d とする。
3. → c²=a²+b²
   　=(a₀×d)²+(b₀×d)²
   　=a₀²×d²+b₀²×d²
   　=(a₀²+b₀²)×d²
4. c²がd²の倍数ということなので、cはdの倍数
5. よって a, b, c が公約数 d（＞1）を持つと言うことなので、原始ピタゴラス数ではない。
6. （⇒a, b, c が互いに素となり得るのは、そのうちの2つの最大公約数が1（＝互いに素）の時に限る）

この証明から分かる通り、実は
「原始ピタゴラス数以外のピタゴラス数は、ある原始ピタゴラス数を整数倍（＞2）したもの」
だったりします（だから「原始」ピタゴラス数、という名前がついているのです）。
その辺のことも分かっていれば、解説記事のサンプルコードにあるような、

if ((gcd(gcd(a, b), c) == 1) && 〜《略》){

なんていうコードは無駄で、

if ((gcd(a, b) == 1) && 〜《略》){

だけで充分、ってことが分かると思います。

アルゴリズムの手前の数学。最適化の手前の数学。大事です。

ピタゴラジュースメーカー

もう1点。

ピタゴラス数は、2つの自然数 m, ｎ（m＞n＞0）を使って、[m²-n², 2×m×n, m²+n²] の組合せで生成できる、ということは解説記事にも載っています。
出題者の解答サンプルコードは、これを利用してまず a, b, c の3つの数を算出してから、互いに素かどうかを見て処理をしています*1。
これも間違いではないのですが、実は m, n に条件を加えると、初めから互いに素な組合せ（つまり原始ピタゴラス数）しか生成しないように出来ます。
Wikipedia にもちゃんと載っているし「数学ガール フェルマーの最終定理」にも『ピタゴラジュースメーカー』という愛称で紹介されています。

整数 m, n を、m＞n＞0、m と n は互いに素、かつ m-n は奇数（⇔m と n はいずれか一方が奇数で他方は偶数）とすると、
[m²-n², 2×m×n, m²+n²] は原始ピタゴラス数となる。
（また a, b, c の3つの数の組が原始ピタゴラス数ならば、それに対応する m, n（で上記の条件を満たすもの）がただ1組存在する）

つまり、整数 m, n を初めから↑の条件で生成すれば、すべての原始ピタゴラス数を「漏れなくダブりなく」生成することが出来る、ということ。それだけで検索すべき数の組合せは約半分になります（m＞n の2数の組 で m-n が奇数のものは約半分なので）。
（より厳密性を増すために、随所に『整数』という言葉を追記しました）

以上を踏まえて

というか他にもツッコミどころはあった*2のですがそれはうっちゃっておいて、実際に提出した私の解答コードを示します。

うん、スッキリしてますよね♪
このコードで、「正解者一番乗り☆」をいただきました♪（「第1回「今週のアルゴリズム：ピタゴラス数」正解者発表｜CodeIQ MAGAZINE」参照）

まとめ

数学的考察、って、こういう「数式や（前提や与えられている条件からの）理詰めで最適解向けてアプローチする」ことだと、私は思っています。

コードの記述ミス（ヒューマンエラー）によるアルゴリズムのミスはそれはもちろんあってはならないこと*3ですが、動くけれど無駄のあるアルゴリズムよりは、動くし無駄が少ないアルゴリズムの方がより良い、と私は思います。

アルゴリズムの手前の数学。最適化の手前の数学。大事です*4。

*1:ただこれが、すべてのピタゴラス数を「漏れなくダブりなく」生成するかどうかは、きちんと検証が必要だと思うのですが

*2:「どこまで検索すれば良いのか」の判定とか「m=n だったら m²-n²=0 だからピタゴラス数の定義に反するから排除しようね」とかとか

*3:恥ずかしながら第2回のアルゴリズム問題はコードの記述ミスで間違った答えを導出してしまい不正解・再提出中です＞＜

*4:大事なことなので、2度言いました