Project Euler - Problem 39

問題

• 原文

  If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

  {20,48,52}, {24,45,51}, {30,40,50}

  For which value of p ≤ 1000, is the number of solutions maximised?

• 日本語訳

  辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする. p = 120のときには3つの解が存在する:

  {20,48,52}, {24,45,51}, {30,40,50}

  p < 1000 で解の数が最大になる p を求めよ.

解答

問題の前提からp = a + b + cです。

三平方の定理よりa² + b² = c²で、p = a + b + c ⇒ c = p - (a + b)なので、cを消去して：

a² + b² = (p - (a + b))² = p² - 2p(a + b) + a² + 2ab + b²

よってp² - 2p(a + b) + 2ab = 0であり、a、bが解のときpは偶数であることが分かります。 またこれをbについて解くとb = (2ap - p²) / 2(a - p)なので、aの値を定めればbの値は一意に決まることが分かります。 結局各pについてa > bとなるまでaを一通り試すだけで良いことになります。

実のところ答えの3つ組を計算する必要はなかったりしますが、答えを出力した上でその数を数える形にしています。

#!/usr/bin/perl

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/reduce/;

sub solutions($) {
  my $p = shift;
  return () unless $p % 2 == 0;

  my @solutions;
  for my $i (1 .. $p - 1) {
    my $j = ($p * (2 * $i - $p)) / (2 * ($i - $p));
    last unless $i <= $j;
    push @solutions, [ $i, $j, sqrt($i ** 2 + $j ** 2) ] if $j == int $j;
  }
  return @solutions;
}

say map { $_->{p} } reduce {
  $a->{num_sols} > $b->{num_sols} ? $a : $b
} map { { p => $_, num_sols => 0 + grep 1, solutions $_ } } 1 .. 999;