スキップしてメイン コンテンツに移動

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];

コメント

このブログの人気の投稿

部分継続チュートリアル

この文書についてこれはCommunity Scheme Wikiで公開されているcomposable-continuations-tutorial(2010年09月30日版)の日本語訳です。誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。本訳は原文のライセンスに基づきCreative Commons Attribution-ShareAlike 2.0 Genericの下で公開されます。Original text: Copyright© 2006-2010 Community Scheme WikiJapanese translation: Copyright© 2011 SATOH Koichi本文部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。resetとshiftという2つのスペシャルフォームを導入するところから始めましょう[1]。 (reset expression)は特別な継続を作るなりスタックに目印を付けるなりしてからexpressionを評価します。簡単に言えば、expressionが評価されるとき、あとから参照できる評価中の情報が存在するということです。 実際にはshiftがこの情報を参照します。(shift variable expression)は目印のついた場所、つまりresetを使った場所にジャンプし、その場所からshiftを呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きにvariableを束縛してからexpressionを評価します。組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。 Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partial continuation)もありますが、ここでは一貫して「組み合わせ可能」という用語を使います(訳注: …

多分週刊チラシの裏 (Sep 21-27, 2020)

Killed by MozillaMozilla がディスコンにした製品およびサービスのリスト。COVID-19 パンデミックで収入が激減し全社の四分の一にあたる従業員の解雇と収益を得られる製品への集中に踏み切った Mozilla Corp. の最初の犠牲はノートアプリ Firefox Notes とファイル送信サービス Firefox Send となった。過去には第三のモバイル OS を目指した Firefox OS とか Mac ネイティブな Gecko ベースブラウザ Camino など懐かしい名前も見られる。ちなみに元ネタは Google が終了したサービスをリストしている Killed by Google で、こちらは 2020 年 9 月 26 日現在 205 個の製品とサービスが挙がっている。Firefox 81.0 リリースノートMozilla Firefox 81.0 が Release チャンネルに公開された。最大の新機能はメディア再生のキーボードないしヘッドセットからの制御である。要はバックグランドで再生している YouTube タブを AirPods から一時停止できるようになった。Developer Tools における色覚異常シミュレーションの改善やブラウザ標準 audio/video 要素のアクセシビリティ改善なども含まれている。Facebook が自社プラットフォーム上での複数国による組織的政治工作を認識しながら放置していたFacebook が大量の偽アカウントを動員した政治工作を認識していながら、特に小国のそれに対して対策を放棄していたという内部告発。元 Facebook のデータ科学者である Sophie Zhang 氏の告発によれば、ホンジュラスで大統領派の工作が行われていることを氏が報告してから実際に対策が為されるまでに 9 ヶ月、アゼルバイジャンでの与党の工作を同様に報告してから組織的な調査が始まるまでに実に 1 年を要したという。本来この手の濫用に対応するはずの専任チームは濫用の圧倒的な割合を占めるスパム対応にかかりきりで、政治工作については対象が合衆国か西欧である場合を除いて積極的に行動せず、小国の民主主義は Zhang 氏の空き時間を利用した片手間の対応にかかっていたとのこと。Rust じゃダメな理由近年人気が出てい…

多分週刊チラシの裏 (Sep 14-20, 2020)

自分にとってのニュースは自らまとめるしかないと思い至ったので興味深かったものをまとめる。Moment.js 開発終了JavaScript における日時処理の定番であった Moment.js の開発がメンテナンスモードへの移行を宣言した。歴史のあるライブラリであり、オブジェクトが可変で flux アーキテクチャと相性が悪いとか、自前の国際化リソースが全部バンドルされているので昨今の Dead Code Elimination (a.k.a. Tree-Shaking) を伴うバンドラでもサイズが縮まらないといった問題が指摘されていた。 互換性を保ったまま問題を解決できる見込みがなく、非互換な新バージョンをリリースして移行の混乱を生むよりは設計段階で問題を解決している別ライブラリに移行せよとのこと。参考に個人的な見解を述べると、代替候補として挙げられている dayjs はお勧めしない。タイムゾーンのサポートなど多くの場合に必要な機能がプラグインで実現されており、それらプラグインは dayjs オブジェクトにメソッドを実行時に追加したり差し替えたりするので TypeScript や flow の型定義と一致しなくなるためである。結局利用するプラグインを適用したバージョンの型定義ファイルを自分で作る羽目になるのだ。dayjs に限らず TypeScript や flow はプラグイン機構を持った JavaScript ライブラリと相性が悪いので、オールインワンなモジュールを採用する方が良い。代替候補の中では最初に挙がっている Luxon が無難である。20年来の銀英伝ファンからみた今回の揉め事「銀河英雄伝説」という古いスペースオペラ小説を原作とするアニメについて以下のツイートが炎上した件: 銀河英雄伝説のリメイク。3期以降も続くのかな。もしそうなら、男女役割分業の描き方は変更せざるをえない気がする。旧アニメのままだと、さすがに時代にそぐわない。作品として大変に面白いのは踏まえたうえで。…なんてことを書いたら炎上するかな。 — Shotaro TSUDA (@brighthelmer) September 11, 2020どう読んでもただの感想だが、話題がジェンダーかつ発言者の津田正太郎教授の所属が「社会学部」ということで表現の自由戦士の標的にされたもの。「社会学者1が『…