脳log[20110203] Q45

最終更新: 2011-02-05T05:33+0900

♪ [ProjectEuler] Q45

 Q45

無駄にこったねえ。一瞬 JavaScriptで書こうとしたしたせいか、lambda多用。

generators = [
	lambda {
		n, tn = 1, 1
		lambda { n+=1; tn+=n; tn } # triangle numbers generator
	}.call,
	lambda {
		n, pn = 1, 1
		lambda { pn+=3*n+1; n+=1; pn } # pentagonal numbers generator
	}.call,
	lambda {
		n, hn = 1, 1
		lambda { hn+=4*n+1; n+=1; hn } # hexagonal numbers generator
	}.call
]
numbers = [1, 1, 1] # Ti, Pj, Hk
relations = "===" # Ti?Pj, Pj?Hk, Hk?Ti
actions = lambda {
	relation = lambda {|a,b|
		a==b ? '=' : a>b ? '>' : '<'
	}
	when_Nth_is_the_smallest = lambda {|i|
		lambda {
			numbers[i] = generators[i].call
			relations[i] = relation.call(numbers[i], numbers[(i+1)%numbers.size])
			j = (i-1) % relations.size
			relations[j] = relation.call(numbers[j], numbers[(j+1)%numbers.size])
			print "#{numbers[i]}\r"
		}
	}
	(0..2).map{|i| when_Nth_is_the_smallest.call(i) }
}.call
action_table = Hash.new {|h,rel|
	raise "missing action for '#{rel}'"
}
[
	["<<>", "<>>", "<=>", "=<>", "<>="], # when Ti is the smallest
	["><<", "><>", ">=<", "><="], # when Pj is the smallest (and Ti not)
	[">><", "<><", "=><"], # when Hk is the smallest (and the other not)
].each_with_index {|rels, i|
	rels.each {|rel| action_table[rel] = actions[i] }
}
action_table["==="] = lambda {
	puts numbers[0] # answer
	actions[0].call
}
loop {
	action_table[relations].call
}

相当な時間をかけて(求められていない)三番目の数字が出た。>57722156241751

六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。

それがわからない。

チート。

Hn = n(2n-1) = (2n-1)(2n)/2 = m(m+1)/2 = Tm (m = 2n-1)

nは自然数だから、mは正の奇数になる。Triangle Numbersの奇数番目が Hexagonal Numbers.(逆も真) 言われたらそうかもね。それぞれの数列を眺めてたら気付くかもね。(それが無理なのはわかってる)