Project Euler - Problem 33

問題

• 原文

  The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

  We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

  There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

  If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

• 日本語訳

  49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.

  我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

  1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.

  その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

解答

どうも「自明でない分数」の基準がよく分かりませんが、「分子・分母に共通する数字を取り除いたとき、元の分数と同じ値になるような分数(ただし分子・分母が10の倍数である場合を除く)」みたいです。

分数を(numerator, denominator)というリストの形で扱うことにして、「共通する数字を取り除いた1桁/1桁の分数で、通分した結果が元の分数のそれと等しい」という長ったらしい述語is_non_trivialを作りました。

#!/usr/bin/env perl

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

sub gcd {
  my ($m, $n) = @_;
  ($m, $n) = ($n, $m) if $m < $n;
  my $r = $m % $n;
  $r == 0 ? $n : gcd($n, $r);
}

sub reduce_fraction {
  my ($num, $den) = @_;
  my $gcd = gcd($num, $den);
  map { $_ / $gcd } ($num, $den);
}

sub is_non_trivial {
  my ($num, $den) = @_;
  return 0 if $num % 10 == 0 or $den % 10 == 0;

  my @ns = split //, $num;
  my @ds = split //, $den;
  my @uns = grep { my $n = $_; none { $_ == $n } @ds } @ns;
  my @uds = grep { my $d = $_; none { $_ == $d } @ns } @ds;
  return 0 unless @uns == 1 and @uds == 1;

  my ($rn, $rd) = reduce_fraction($num, $den);
  my ($urn, $urd) = reduce_fraction(@uns, @uds);
  $rn == $urn and $rd == $urd;
}

my @product = @{
  reduce {
    [ $a->[0] * $b->[0], $a->[1] * $b->[1] ]
  } map {
    my $den = $_;
    map { [$_, $den] } grep { is_non_trivial($_, $den) } 10 .. $den - 1;
  } 11 .. 99
};
say +(reduce_fraction(@product))[1];