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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Obviously a minimizer $P$ must have the property that all its elements are primes or prime powers. $\endgroup$
    – user35593
    Commented 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
    Commented 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$
    – J Fabian Meier
    Commented 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
    Commented 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$
    – The Masked Avenger
    Commented Jun 22, 2015 at 16:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As a search term, you could try "Landau's function" . $\endgroup$
    – The Masked Avenger
    Commented Jun 22, 2015 at 16:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .