36
$\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!

Improve this question
$\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$
    – mathcounterexamples.net
    Jan 14, 2015 at 18:12
  • $\begingroup$ Fixed (easy does it). $\endgroup$
    – Włodzimierz Holsztyński
    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$
    – Włodzimierz Holsztyński
    Jan 15, 2015 at 7:26
  • 4
    $\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, 2015 at 7:32

2 Answers 2

Reset to default
34
$\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.

Improve this answer
$\endgroup$
1
5
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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