プロジェクト・オイラーを考え詰め

昨晩は夕食後早々と寝てしまい、午前二時前に起きる。
音楽を聴く。■マーラー：交響曲第五番（グスターボ・ドゥダメル）。バランスの取れた、細部までよく整えられた小ぎれいな演奏。こういう端正な演奏で聴いてみると、自分はポピュラーソングであるアダージェットが好きなのだなあと思った。この楽章が映画「ヴェニスに死す」の全編で効果的に使われていることは有名であるが、トーマス・マンとマーラーの結合というのはいかにも十九世紀末を彷彿とさせる感じで、コロンブスの卵的なアイデアであった。このデカダンスぶりはちょっと魅力的なのである。

Symphony 5

■ショパン：マズルカ ロ長調 op.56-1、ハ長調 op.56-2、ハ短調 op.56-3、イ短調 op.59-1、変イ長調 op.59-2、嬰ヘ短調 op.59-3 (ルービンシュタイン、参照）。■オンスロウ：弦楽四重奏曲ヘ短調 op.9-3 (マンデルリングQ、参照）。
＃
一日中プロジェクト・オイラーの問66と問76を考えていたのだが、ついに両方とも解けなかった。頭がぼーっとしてきて考えられなくなってきたので、もう止める。阿呆ですなあ。（PM11:24）
問76は一応下の Ruby コードで解ける筈だが、計算時間がかかりすぎて求められない。うーむ。

require 'set'

N = 100
s = Set.new
for i in 1...N
  (1...N).to_a.combination(i) do |ar|
    ar1 = [0] + ar + [N]
    a = []
    (ar1.size - 1).times {|i| a << ar1[i + 1] - ar1[i]}
    s << a.sort
  end
end
puts s.size

諦めてぐぐりました。分割数というのかあ（参照）。これを独力で発見するのはむずかしい。で、その上でのコード。

N = 100
h = {}
(1..N).each {|i| h[[i, 1]] = h[[i, i]] = 1}
for n in 2..N
  for r in 2..n
    a = (n - r >= r) ? h[[n - r, r]] : 0
    h[[n, r]] = h[[n - 1, r - 1]] + a
  end
end
ans = 0
(1..N).each {|i| ans += h[[N, i]]}
puts ans - 1

こんなにあっさり出るとは（0.08秒）。まいりました。
なお、やはり上のやり方でも正しい答えが出るようだが、だいたい N = 23 くらいが限度（これで約25秒）。これでもよく思いついたと思うのですけれど。