Project Euler - Problem 26

問題

• 原文

  Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

• 日本語訳

  d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。

解答

筆算の過程から類推できるように、この問題は同じ余りが出るまでの間隔を調べる問題に置き替えることができます。

#!/usr/bin/perl

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

sub rec_cycle_period($$) {
  my ($deno, $upper_lim) = @_;
  my %appeared_rems;
  my $remainder = 10;
  my $i = 0;
  do {
    return 0 if $remainder == 0;
    return -1 if $i >= $upper_lim;
    $appeared_rems{$remainder} = $i++;
    $remainder %= $deno;
    $remainder *= 10;
  } until exists $appeared_rems{$remainder};
  return $i - $appeared_rems{$remainder};
}

say
  map { $_->[0] }
  reduce { $a->[1] > $b->[1] ? $a : $b }
  map { [$_, rec_cycle_period($_, 1000)] } 1 .. 1000;