1 / 1

386 : 反鎖の最大長(**)

$n$ を整数とし、 $n$ の約数の集合を $S(n)$ としよう。

$S(n)$ の部分集合 $A$ が一つの要素のみを含むか、あるいは $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 \leq n \leq 10^8$ に対する $\sum N(n)$ を求めよ。

(** 説明「互いに素」ではいけないのかしら。集合に「長さ」はない。en.wikipediaでは、antichainとはもっと一般化した内容で、widthという属性とともに説明されている。 https://en.wikipedia.org/wiki/Antichain )

$n$ を整数とし、 $n$ の約数の集合を $S(n)$ としよう。

例えば： $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 \leq n \leq 10^8$ に対する $\sum N(n)$ を求めよ。