# Why does this sequence converges to $\pi$?

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!

• I suppose $4$ in the right-hand side of the first line of the example was supposed to be cancelled, too? – Seva Jan 14 '15 at 18:09
• 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. – mathcounterexamples.net Jan 14 '15 at 18:12
• Fixed (easy does it). – Włodzimierz Holsztyński Jan 15 '15 at 7:22
• You don't need any integers in your sequence. Instead, you may have simply, say, $n$ stars $\ (*\ *\ \ldots\ *),\$ etc. – Włodzimierz Holsztyński Jan 15 '15 at 7:26
• 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. – Włodzimierz Holsztyński Jan 15 '15 at 7:32

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.