Project Euler 25

フィボナッチ数列は以下の漸化式で定義される:

Fn = Fn-1 + Fn-2, ただし F_1 = 1, F_2 = 1.
最初の12項は以下である.

F_1 = 1
F_2 = 1
F_3 = 2
F_4 = 3
F_5 = 5
F_6 = 8
F_7 = 13
F_8 = 21
F_9 = 34
F_10 = 55
F_11 = 89
F_12 = 144
12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

Mathematica

i = 1;
While[
  True,
  tmp1 = Length[IntegerDigits[Fibonacci[i]]];
  If[tmp1 >= 1000, Break[], {}]
  i++;
]
i

1000桁になったらループを終了、というだけですね。

C/C++

#pragma comment(lib,"mpir.lib")
#include <iostream>
#include <mpir.h>
using namespace std;

// n番目のフィボナッチ数を返す。(mpir版)
/*
void fibonacci(mpz_t* num, int n){
	
	if(n>2){
		mpz_t a,b;
		fibonacci(&a, n-1);
		fibonacci(&b, n-2);
		
		//a = a+b;
		mpz_add(a, a, b);
		mpz_init_set(*num, a);
	}

	else mpz_init_set_ui(*num, 1);
}
*/

// mpz_t型の桁数を返す。
int mpz_digit(mpz_t* num){
	mpz_t a;
	mpz_init_set(a, *num);
	int count = 0;

	while(mpz_cmp_si(a,0)!=0){
		// a = a/10;
		mpz_div_ui(a, a, 10);
		count++;
	}
	return count;
}

int main(){
	//old1 -> n-1番目, old2 -> n-2番目
	mpz_t old1, old2, n;

	mpz_init_set_ui(old1, 1);
	mpz_init_set_ui(old2, 1);
	mpz_init_set_ui(n, 0);

	int dig, order = 3;

	while(1){
		//n = old1+old2;
		mpz_add(n, old1, old2);
		dig = mpz_digit(&n);

		/*
		cout << order << "th -> ";
		mpz_out_str(stdout, 10, n);
		cout << ", digit -> " << dig << endl;
		*/

		if(dig >= 1000) break;

		order++;
		mpz_set(old2, old1);
		mpz_set(old1, n);		
	}

	cout << order << "th -> ";
	mpz_out_str(stdout, 10, n);
	cout << ", digit -> " << dig << endl;

	return 0;
}

最初にフィボナッチ数列の関数を再起で作ったんですが、これがもう糞のように遅かった。(当たり前)