脳log[20110310] 65, 66, 67, 68, 69

最終更新: 2011-03-12T02:24+0900

♪ [ProjectEuler] 65, 66, 67, 68, 69

 Problem 65

分母を一番深いところから順番に計算していく。

a = ([2] + (1..33).map{|k| [1,2*k,1] }.inject(&:+)).reverse
denom, numer = *a.inject([0,1]){|nd, x| [nd[1], x*nd[1]+nd[0]] }
require 'rational'
p Rational(numer, denom).numerator.to_s.chars.inject(0){|sum,c| sum - ?0 + c[0] }

 Problem 66

xを増やしながらの総当たりで、最後に見つかった Dが答え。と思ったんだけど Dが見つかるペースがどんどこ落ちていく。一日以上かけても 969個の Dのうち 270個が残ってる。

 Problem 67

Problem 18の延長で以前解いた。

 Problem 68

1. 16桁だから 10は一回しか使わない。10は external node.
2. 先頭の桁(外側のノードの最小値)を最大にするために、external nodeに 10,9,8,7,6を配置する。
3. そうすると一辺の和はとりうる値の中で最小の 14。
4. 二桁目を最大にする 6-5-3からスタートして考えよう。次は 10-3-1しかない。
5. ってなかんじで穴埋め。

 Problem 69

前問に引き続いて、数学でもプログラミングでもなく、オラクルで。

1. n/φ(n)を最大にするために……
2. 分母を小さくするために、nはたくさんの素数を因数に持っている方がいい。⇒すべて異なる素数の積からなる数。
3. 分子を大きくするために、nは上限の 100万に近い方がいい。
4. 分子と分母のバランスの取り方は勘で。