11
$\begingroup$

Let $S$ be the set of integers $\{2,3,4,\ldots,n\}$. Consider the following process:

  • Select a random element $k \in S$.
  • Remove from $S$ every number divisible by $k$.
  • Repeat with this reduced $S$.

I am interested in the number of repetitions $\sigma(n)$ needed to reduce $S$ to the empty set.

Example, $n=10$: \begin{eqnarray} \# &:& 2,3,4,5,6,7,8,9,10\\ 10 &:& 2,3,4,5,6,7,8,9\\ 9 &:& 2,3,4,5,6,7,8\\ 3 &:& 2,4,5,7,8\\ 4 &:& 2,5,7\\ 5 &:& 2,7\\ 7 &:& 2\\ 2 &:& \varnothing \end{eqnarray} Limited data suggests that the number of sieve operations $\sigma(n)$ needed to decimate the set $S$ might grow approximately linearly with $n$:

          Sieve
          Number of random sieve iterations to decimate the set $\{2,3,\ldots,n\}$.
          Each point plotted is the average of $10$ simulations.
The slope is about $0.28$ (without any careful statistics).

Perhaps it is possible to estimate $\sigma(n)$ for large $n$?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You will need $\pi(n)$ at the absolute minimum, and in the first draw you should expect to knock out on average less than log n entries. My guess is that $C\pi(n)$ tries are needed where $C$ may grow with $n$. Gerhard "Or It Could Be Three" Paseman, 2015.11.15 $\endgroup$
    – Gerhard Paseman
    Commented Nov 15, 2015 at 8:19
  • 3
    $\begingroup$ I did an experiment with $n=1000000$ and found $\sigma(n)=235992$ in my instance. This doesn't appear to agree with the $C\pi(n)$ guess. $\endgroup$
    – Anthony Quas
    Commented Nov 15, 2015 at 12:45
  • $\begingroup$ As $\pi(10^6)=78,498$, I'd say it supports the guess that $C$ is near 3 when $n$ is a million quite well. Gerhard "Is Looking At It Differently" Paseman, 2015.11.15 $\endgroup$
    – Gerhard Paseman
    Commented Nov 15, 2015 at 17:13
  • 1
    $\begingroup$ There may be tree-pruning mathematics which is available. Joseph is essentially pruning a subset of the divisibility lattice, and the answer may apply to posets on which a Moebius function is defined. Gerhard "Ok, Maybe Vine-pruning Mathematics Instead" Paseman, 2015.11.15 $\endgroup$
    – Gerhard Paseman
    Commented Nov 15, 2015 at 21:33

2 Answers 2

Reset to default
12
$\begingroup$

An equivalent way of describing the process: We start with a randomly chosen permutation $\tau$ of $\{2, \dots, n\}$. At each step we choose the first number in $\tau$ which is still in our set $S$, and apply the deletion process with that as our $k$. A key property here:

An integer $x$ is chosen at some point if and only if x appears before all of its divisors in $\tau$

This is simply because if some divisor $y$ of $x$ appears before $x$, then either $y$ itself is chosen, or some divisor of $y$ (which is also a divisor of $x$) is chosen.

In particular, the probability that $x$ is chosen at some point is $\frac{1}{d(x)-1}$, where $d(x)$ is the number of divisors of $x$. This implies that the expected number of steps to decimation is $$\sum_{x=2}^n \frac{1}{d(x)-1}$$

I feel like this sum (or at the very least $\frac{1}{d(x)}$) has to be well-studied, but I don't have any references.

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ That's very nice. A standard argument (Selberg-Delange) will show that $\sum_{k=2}^{n} 1/d(k)$ is about $Cn/\sqrt{\log n}$ for a constant $C$. And your sum is asymptotically the same up to error terms that are smaller. $\endgroup$
    – Lucia
    Commented Nov 15, 2015 at 15:15
  • $\begingroup$ Very clever reformulation of the problem! $\endgroup$
    – Joseph O'Rourke
    Commented Nov 16, 2015 at 1:35
1
$\begingroup$

I think the correct asymptotics should be rather $O(\frac{n}{\log n})$. That's because when you have $n$ numbers in your set and $n$ is large, then you knock out roughly $U^{-1}$ numbers, where $U$ is a Uniform$[0,1]$ random variable (indeed, if $k$ is chosen, then you through out approximately $\frac{n}{k}=\big(\frac{k}{n}\big)^{-1}$ numbers). Now, $\sum_{j=1}^m U_j^{-1}$ grows roughly as $m\log m$, so you need around $O(\frac{n}{\log n})$ steps to "considerably decrease" you set (say, to the size of $\frac{n}{\log n}$, since then it's enough to just decrease linearly).

Hopefully, this heuristics can be turned into proof, since on the "early stages" the "double-erasing attempts" (i.e., when you try to remove a number that was already removed before) shouldn't contribute a lot.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I also thought about this heuristic, but I feel it might not be right. It's true that you delete on average $\log n$ numbers in your first step, but (1) much of this is accounted for by very small divisors - which can only be used once; and (2) once you've used up a small divisor, later removals kill off a lot less. My money is on $\Omega(n)$. (Also in the computer experiment, you see a lot of time where "nothing" is being deleted and $\sigma(n)/n$ decreases from $0.28$ when $n=1000$ to $0.24$ when $n=1000000$.) $\endgroup$
    – Anthony Quas
    Commented Nov 15, 2015 at 19:50
  • 1
    $\begingroup$ Now I think that the other answer ($\Omega(n/\sqrt{\log n})$) may be true, but I'm pretty sure it should be $o(n)$ in any case. Well, just intuitive feeling :) $\endgroup$
    – Serguei Popov
    Commented Nov 15, 2015 at 21:15

You must log in to answer this question.

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