２０１５東大数学問題をPHPで解く（しかし、どはまる）

2015年東京大学（理科）数学 問5

mを2015以下の正の整数とする
2015 C m が偶数となる最小のmを求めよ
http://www.yomiuri.co.jp/nyushi/15/sokuho/1222243_2080.html

というわけで、Cをまずつくろう。

nCk = n!/k!(n-k)! なので、階乗を求める関数factorialを

function factorial($n) {
    if ($n === 0) {
        return 1;
    }

    return $n * factorial($n - 1);
}

と定義して、

function combination($n, $k) {
    return factorial($n) / (factorial($k) * factorial($n - $k));
} 

combination(4,2) -> 6 うん。OK.

これをループして、最初に偶数になるものだから
こんな感じかな？ターンッ

for ($i = 0; $i < 2015; $i++) {
    if (combination(2015, $i) % 2 === 0) {
        echo $i;
        break;
    }
}

ファッ？！

PHP Fatal error:  Maximum function nesting level of '1000' reached, aborting! in /home/vagrant/201504.php on line 9
PHP Stack trace:
PHP   1. {main}() /home/vagrant/201504.php:0
PHP   2. combination() /home/vagrant/201504.php:16
PHP   3. factorial() /home/vagrant/201504.php:12

最近では再帰の量に制限があるのか！初めて知ったわ！

xdebugがある場合は変更できるらしいよ。

ini_set('xdebug.max_nesting_level', 2000000);

どんくらいまで計算できるのかな？

var_dump(factorial(20));
var_dump(factorial(21));

int(2432902008176640000)
double(5.1090942171709E+19)

アウツ。
PHPの場合にはgmp_factを使いなさいってことですね・・・orz

Pythonで書いてみよう

同様に再帰の制限にかかってしまったので

import sys
sys.setrecursionlimit(1000000000)

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

def comb(n,k):
    return fact(n) / (fact(k) * fact(n-k))

for i in range(0, 2015):
    if comb(2015, i) % 2 == 0:
        print i
        sys.exit()

$ python 201504.py 
32

よし。解けました。