3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Obviously a minimizer $P$ must have the property that all its elements are primes or prime powers. $\endgroup$
    – user35593
    Jun 22, 2015 at 9:00
  • 3
    $\begingroup$ I think taking the first few primes is the asymptotically cheapest way to get large products. I'd be interested to see precise bounds, as this also comes up in a problem I have on the back burner. $\endgroup$
    – Ben Barber
    Jun 22, 2015 at 10:05
  • $\begingroup$ So if we really take 2*3*5*7*... until we exceed n, can we get we get an estimate of the sum in terms of n (log(n)?) from some prime number distribution estimate? $\endgroup$ Jun 22, 2015 at 11:27
  • 3
    $\begingroup$ Wikipedia asserts that the primorial grows like $e^{(1+o(1))k\log k}$, and the sum of the first $k$ primes looks like $k^2 \log k / 2$, so $f(n) =O( (\log n)^2/(\log \log n))$. $\endgroup$
    – Ben Barber
    Jun 22, 2015 at 12:28
  • $\begingroup$ Ben's suggestion gives a good starting approximation. You will need to use prime powers at some point; the answer I give tells you what to look for for a more precise answer. $\endgroup$ Jun 22, 2015 at 16:21

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ As a search term, you could try "Landau's function" . $\endgroup$ Jun 22, 2015 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.