フィボナッチ数列

プログラミングネタ

フィボナッチ数列のうち、各桁の数字を足した数で割り切れる数を以下の例に続けて小さいほうから5個求めてください。

2 → 2 ÷ 2
3 → 3 ÷ 3
5 → 5 ÷ 5
8 → 8 ÷ 8
21 → 21 ÷ 3・・・2 + 1= 3で割る
144 → 144 ÷ 9・・・1 + 4 + 4 = 9で割る

これはメモ化と大きな桁を扱う事についての問題です。
perlであれば、use bignum;を使うことで対処出来ます。
このbignum初めて知った。

use strict;
use warnings;

use bignum;

my $before = 0;
my $cnt = 0;
my @memo;
my $n = 1;
while(1){
    my $fibona = fibo($n);
    my $fibo_div = $fibona / sp($fibona);
    if($fibo_div ==  int($fibo_div)){
        $cnt++;
        if($cnt > 7){
            print "$fibona\n";
        }
        if($cnt > 11){
            last;
        }
    }
    $n++;

}

sub fibo{
    my $num = shift;
    unless (defined $memo[$num]){
        if(($num == 0) || ($num == 1)){
            $memo[$num] = 1;
        }else{
            $memo[$num] = fibo($num - 2) + fibo($num - 1);
        }
    }
    return $memo[$num];
}

sub sp{
    my @ret = 0;
    my $n = shift;
    @ret = split(//,$n);
    my $total = 0;
    foreach my $sum (@ret){
        $total += $sum;
    }
    return $total;

}

perl q11.pl 
2584
14930352
86267571272
498454011879264
160500643816367088