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$
6
  • $\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, 2015 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$ Jan 14, 2015 at 18:12
  • $\begingroup$ Fixed (easy does it). $\endgroup$ Jan 15, 2015 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$ Jan 15, 2015 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$ Jan 15, 2015 at 7:32

2 Answers 2

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$
1
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.