35
$\begingroup$

One of my daughters was having a small programming exercise.

Let's consider following algorithm:

  • Take a list of length $n$: $\ (1\,\ 2\,\ \ldots\,\ n)$.
  • Remove every $2$nd number.
  • From the resulting list, remove every $3$rd number.
  • From the resulting list, remove every $4$th number.
  • ... Follow on until the list remains unchanged and let $u_n$ be the number of remaining elements.

Example with $n=11$

  • $(\ 1\,\ 2\,\ 3\,\ 4\,\ 5\,\ 6\,\ 7\,\ 8\,\ 9\,\ 10\,\ 11\ )\quad \Rightarrow\quad (\ 1\ *\ 3\ *\ 5\ *\ 7\ *\ 9 \ *\ 11\ )$
  • $(\ 1\,\ 3\,\ 5\,\ 7\,\ 9\,\ 11\ )\quad \Rightarrow\quad (\ 1\,\ 3\ *\ 7\,\ 9\ *\ )$
  • $(\ 1\, 3\,\ 7\,\ 9\ )\quad \Rightarrow\quad (\ 1\,\ 3\,\ 7\ *\ )$
  • $(\ 1\,\ 3\,\ 7\ )\ $ -- will not be modified anymore, and therefore $u_n=3$.

QUESTION:   why do we have $\lim\limits_{n \to +\infty} \frac{n}{u_n^2}=\frac{\pi}{4}$ ?

Thanks!

$\endgroup$
  • $\begingroup$ I suppose $4$ in the right-hand side of the first line of the example was supposed to be cancelled, too? $\endgroup$ – Seva Jan 14 '15 at 18:09
  • 3
    $\begingroup$ Yes and it is... the issue is that the strikethrough bar is just on the bar of the $4$ number, leading to a poor readability. $\endgroup$ – mathcounterexamples.net Jan 14 '15 at 18:12
  • $\begingroup$ Fixed (easy does it). $\endgroup$ – Włodzimierz Holsztyński Jan 15 '15 at 7:22
  • 1
    $\begingroup$ You don't need any integers in your sequence. Instead, you may have simply, say, $n$ stars $\ (*\ *\ \ldots\ *),\ $ etc. $\endgroup$ – Włodzimierz Holsztyński Jan 15 '15 at 7:26
  • 3
    $\begingroup$ Thus you do not need even any stars. You start with $\ c(n\ 1) := n.\ $ Then you define $\ c(n\ k) := c(n\ k\!-\!1)-\lfloor\frac {c(n\ k\!-\!1)}k\rfloor.\ $ Etc. $\endgroup$ – Włodzimierz Holsztyński Jan 15 '15 at 7:32
32
$\begingroup$

This problem was studied first by the founder of sieve theory, Brun himself, who proved this asymptotic. For a fairly recent paper on this subject look at Andersson who gives more precise estimates for $u_n$. The MO question Sequences with integral means is also closely related, and see also my answer there.

$\endgroup$
4
$\begingroup$

This is an extended comment: Interestingly enough, displaying the differences of consecutive terms of A000960 shows an amazing degree of fluctuation.enter image description here

$\endgroup$

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.