最終更新: 2011-03-14T23:14+0900
昨日(20110312p01)の延長。Problem 72の解答と同じ部分より違う部分を見つける方が難しい。
LIMIT = 12000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
print d,"\r"
d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
n_min, n_max = d/3, (d-1)/2 # (n_min, n_max]
next unless n_min < n_max
count += n_max - n_min # 1) とりあえず一通りの分子を計上し、
# 2) 8分の6など通分可能なものを差し引きする。
(1..(pfs[d].size)).each{|r|
cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
count -= (-1)**(r%2+1) * cms.map{|cm| n_max/cm - n_min/cm }.inject(&:+)
}
}
p count
問題文のヒントを最大限に利用したが数分かかる。総当たりでなく組み合わせ単位でテストしてその順列を計上したらマシになるかも。順列を考えるときに先頭の桁に 0を置くようなミスを犯しそうだがね。
factorial = [1,1] # [0!,1!,...]
factorial.push(factorial.size*factorial.last) until 9 < factorial.size
chain_length = lambda{
memo = {
169 => 3, 363601 => 3, 1454 => 3,
871 => 2, 45361 => 2,
872 => 2, 45362 => 2
}
f = lambda{|start|
return memo[start] if memo.has_key?(start)
next_ = start.to_s.chars.map{|c| factorial[c[0]-?0] }.inject(&:+)
return memo[start] = 1 + (start == next_ ? 0 : f.call(next_))
}
}.call
p (1...1_000_000).inject(0){|sum,n| sum += 1 if chain_length.call(n) == 60; sum }