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

calc.go

package main

import "fmt"
import "math/big"

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

mを2015以下の正の整数とする
2015 C m が偶数となる最小のmを求めよ

http://www.yomiuri.co.jp/nyushi/15/sokuho/1222243_2080.html
*/

var (
	n      = big.NewInt(2015)
	one    = big.NewInt(1)
	two    = big.NewInt(2)
	zero   = big.NewInt(0)
	lookup = make(map[int]*big.Int, 2015)
)

func main() {

	for i := 1; i < 2015/2; i++ {
		x := combination(n, big.NewInt(int64(i)))
		if x.Mod(x, two).Cmp(zero) == 0 {
			fmt.Println("Answer:", i)
			break
		}
	}

}

func factorial(n *big.Int) (result *big.Int) {

	if n.Cmp(one) < 1 {
		return one
	}

	if m, ok := lookup[int(n.Int64())]; ok {
		return m
	}

	result = new(big.Int).Set(n)
	result = new(big.Int).Mul(result, factorial(n.Sub(n, one)))

	lookup[int(n.Int64())] = result

	return
}

func combination(n, k *big.Int) *big.Int {

	a := factorial(new(big.Int).Set(k))
	b := factorial(new(big.Int).Sub(n, k))

	c := new(big.Int).Mul(a, b)
	d := factorial(new(big.Int).Set(n))

	return d.Div(d, c)
}

calc_test.go

package main

import (
	"math/big"
	"testing"
)

func TestFactorial(t *testing.T) {

	t1 := factorial(big.NewInt(4))
	if t1.Cmp(big.NewInt(24)) != 0 {
		t.Errorf("4! should be 24. it is %v", t1)
	}

	t2 := factorial(big.NewInt(10))
	if t2.Cmp(big.NewInt(3628800)) != 0 {
		t.Errorf("10! should be 3628800. it is %v", t2)
	}

}

func TestCombination(t *testing.T) {

	t1 := combination(big.NewInt(4), big.NewInt(2))
	if t1.Cmp(big.NewInt(6)) != 0 {
		t.Errorf("4 C 2 not equal 6.it is %v", t1)
	}

	t2 := combination(big.NewInt(2015), big.NewInt(32))
	expect := new(big.Int)
	expect.SetString("16186954748025166046263663997642430244064006144786443959701793710268550", 10)

	if t2.Cmp(expect) != 0 {
		t.Errorf("2015 C 32 not equal 16186954748025166046263663997642430244064006144786443959701793710268550. it is %v", t2)
	}

}

func BenchmarkFactorial(b *testing.B) {

	for i := 0; i < b.N; i++ {
		factorial(big.NewInt(10))
	}

}

func BenchmarkCombination(b *testing.B) {

	for i := 0; i < b.N; i++ {
		combination(big.NewInt(2015), big.NewInt(32))
	}

}