Let $P(n)$ be the set of subsets $P$ of $\mathbb{N}$ with the properties


1. All elements of $P$ are relative prime to each other.
2. The product of all $k \in P$ is greater or equal to $n$.


Now let $f(n) = \min\_{P \in P(n)} \sum\_{k \in P} k$.


What can be said about the size of $f(n)$ (in relation to $n$)?


A straightforward way to construct upper bounds would be to look at some $i$th root of $n$ and pick $i$ relative prime numbers "near" to it. But I wonder if there is some general theorem that gives sharp bounds for this problem.


By the way: I use $f(n)$ in describing the size of a special mixed integer program.



Products of relative prime numbers with least sum
Notice that the product prod P ( bounded below by n) represents the order of a permutation with cycle structure given by P and
sitting in S\_m, where m=f(n). So considering the largest order of elements occurring in finite symmetric groups should give you a good idea of the growth rate of f(n). Ben Barber has given what looks like a good order of growth in a comment, and you can find literature on the maximal order problem to confirm/refine this estimate.


