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$?

$\endgroup$
  • 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 Nov 15 '15 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 Nov 15 '15 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 Nov 15 '15 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 Nov 15 '15 at 21:33
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.

$\endgroup$
  • 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 Nov 15 '15 at 15:15
  • $\begingroup$ Very clever reformulation of the problem! $\endgroup$ – Joseph O'Rourke Nov 16 '15 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.

$\endgroup$
  • 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 Nov 15 '15 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 Nov 15 '15 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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