Problem26

Perl 30分プログラム

30分プログラム、その297。Problem26 via Project Euler。

単位分数とは分子が1の分数である。分母が2から10の単位分数を10進数で表記すると次のようになる。

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

0.1(6) 0.166666... という数字であり、6が循環節であることを表している。1/7 循環節は6桁ある。
d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。

実際に割り算をして、正規表現で循環節を取り出す戦略でいったら、失敗した。やっぱり精度が足りてない気がするなぁ。

使い方

$ perl 297-problem26.pl
1/3=0.3333333333333 (333333):6
1/6=0.1666666666666 (666666):6
...
1/189=0.005291005291005 (005291):6
1/231=0.004329004329004 (004329):6
1/239=0.004184100418410 (0041841):7
1/717=0.001394700139470 (0013947):7

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# problem26.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/05/02 16:49:48
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
use strict;
use warnings;

my $max = 0;
for $i(1..1000){
    my $num = 1.0/$i;
    $num = substr($num,0,length($num)-2);
    if($num =~ /(\d+)\1/){
	if($max <= length($1)){
	    $max = length($1);
	    print "1/$i=$num ($1):$max\n";
	}
    }
}

参考