Problem 386 「反鎖の最大長」

ある整数を n とし, n の約数の集合を S(n) としよう.

S(n) の部分集合 A が一つの要素のみを含むか, あるいは A のいかなる要素もその他全ての要素によって割り切ることができないとき, それを S(n) の反鎖 (antichain) と呼ぼう.

例えば : S(30) = {1, 2, 3, 5, 6, 10, 15, 30}
{2, 5, 6} は S(30) の反鎖ではない.
{2, 3, 5} は S(30) の反鎖である.

S(n) の反鎖のうち最大の長さとなるもののその長さを N(n) で表すとしよう.

1 ≤ n ≤ 10&sup{8}; のときの ΣN(n) を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS