Meertens数
Posted feedbacks - Perl
10進10桁で1時間16分23秒掛かりました。(PentiumM1.6GHz)1桁毎に3倍ずつ増えるとして計算すると，20桁では8～10年程掛かる事になります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #! /usr/bin/perl
use strict;
use bigint;
package Prime;
sub checkPrime {
my ($pkg,$primes,$forCheck) = @_;
!scalar(grep { $forCheck % $_ == 0 } @$primes);
}
sub getNext {
my ($pkg,$primes,$from) = @_;
my $next = $from;
$next++ until ($pkg->checkPrime($primes,$next));
$next;
}
sub primes {
my ($pkg,$count) = @_;
my $next = 1;
my $primes = [];
for(1..$count) {
$next = $pkg->getNext($primes,$next+1);
push(@$primes,$next);
}
$primes;
}
package Meertens;
sub meertenses {
my ($pkg,$max,$primes,$meertenses,$place,$baseNumber,$baseGoedel) = @_;
my $prime = $primes->[$place];
for (0..9) {
my $number = $baseNumber * 10 + $_;
my $goedel;
last if ($number > $max);
$goedel = $baseGoedel * $prime ** $_;
push(@$meertenses,$goedel) if ($goedel == $number);
if ($place < length($max) && $goedel < $max) {
$pkg->meertenses($max,$primes,$meertenses,$place + 1,$number,$goedel);
}
}
$meertenses;
}
package main;
sub timestamp {
my ($second, $minute, $hour, $day, $month, $year) = @_;
$year += 1900;
$month++;
sprintf("%04d/%02d/%02d %02d:%02d:%02d",$year,$month,$day,$hour,$minute,$second);
}
print "start:".timestamp(localtime)."\n";
print join("\n",@{Meertens->meertenses(9999999999,Prime->primes(10),[],0,0,1)})."\n";
print "end:".timestamp(localtime)."\n";
1;
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]