Divisor Chains

Call a nonempty subset of $S(n)$ satisfying the condition a divisor chain.

For a positive integer $m$, let $g(m)$ be the number of divisor chains whose largest element is exactly $m$. Every element of such a chain divides $m$.

If we remove $m$, the remaining chain is either empty or a divisor chain whose largest element is some proper divisor $d$ of $m$. Conversely, adding $m$ to any such chain yields a chain with largest element $m$. Therefore,

$$g(m)=1+\sum_{\substack{d\mid m\\d<m}}g(d).$$

The initial $1$ represents the singleton chain consisting only of $m$.

Each divisor chain selected from $S(n)$ has exactly one largest element $d$, and $d$ divides $n$. Hence

$$f(n)=\sum_{d\mid n}g(d).$$

Compute $g(1),g(2),\cdots,g(N)$ in increasing order. Initialize every $g(m)$ to $1$. Once is known, add it to for every proper multiple of . Since , all contributions from proper divisors are already known when is processed.

The recurrence implies $\sum_{d\mid n,d<n}g(d)=g(n)-1$, so

$$f(n)=2g(n)-1.$$

Iterating over multiples as in the sieve of Eratosthenes gives time complexity $O(N\log N)$ and space complexity $O(N)$. Over $1\le n\le 100\,000$, the maximum answer is , which fits in signed -bit integers.

Solution written by GPT6