Project Euler 4週目 - EchizenBlog-Zwei

Project Euler 4週目。周りの人達の進みが早すぎてあせる。

http://projecteuler.net
http://odz.sakura.ne.jp/projecteuler/　問題の和訳

14:
Find the longest sequence using a starting number 
under one million.

Collatz数の問題。「はじめての数論」で一度出てきていたのでちょっとうれしい気分。普通にやると結構時間かかる。とりあえず500000以下の数は候補から外していいはず。

15:
Starting in the top left corner in a 20 by 20 grid,
 how many routes are there to the bottom right corner?

各地点からゴールまでの分岐数をDPで計算すればOK。こういう問題は好き。

16:
What is the sum of the digits of the number 2^1000?

いい方法が思いつかず多倍長整数型のお世話になった。

17:
How many letters would be needed to write all the 
numbers in words from 1 to 1000?

地道に数える。コード書くのが面倒。40をfourtyだとずっと勘違いしていてハマった。危ない。

18:
Find the maximum sum travelling from the top of the 
triangle to the base.

これは上から順番に上2つのmaxを計算して足していけばいいはず。

19:
How many Sundays fell on the first of the month during 
the twentieth century?

閏年(leap year)の判定が綺麗にかけなくてちょっと考えてしまった。

20:
Find the sum of digits in 100!

これも多倍長整数型のお世話に。。。

21:
Evaluate the sum of all amicable pairs under 10000.

amicable pairsは友愛数の組のこと。proper divisorsは真約数(その数自身以外の約数)。

22:
What is the total of all the name scores in the file 
of first names?

あまりProjectEulerっぽくない問題だなあ、という印象。

数論のすばらしく面白い教科書。オススメ！