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
    Commented 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
    Commented Jan 14, 2015 at 18:12
  • $\begingroup$ Fixed (easy does it). $\endgroup$
    – Włodzimierz Holsztyński
    Commented 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
    Commented 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
    Commented 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$ See also OEIS sequence A000960 ( oeis.org/A000960 ) and references there. $\endgroup$
    – Robert Israel
    Commented Jan 14, 2015 at 18:42
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .