Интересное решето

[Lion]

Выпишем последовательные числа натурального ряда. Потом сотрем все числа. стоящие на четных местах. В оставшемся ряду сотрем все числа. стоящие на местах, номера которых кратны 3, в оставшемся --- числа, номера которых кратны 4, и т.д. В итоге образуется последовательность, начинающаяся числами 1, 3, 7, 13, 19, ... Обозначим ее через ${a_n}$. Докажите, что $\lim\limits_{n\to \infty} \frac{a_n}{n^2}=\frac{\pi}{4}$.

[Руст]

Рассмотрим интервал до a(n) и обозначим число элементов в этом интервале b(k) на k - ом шаге. В первом шаге b(1)=a(n), на втором шаге b(2)=b(1)-[b(1)/2], вообще b(k)=b(k-1)-[b(k-1)/k]. Т.е. n=b(k),k>=n. Так как b(k-1)(k-1)/k+1>b(k)>=(k-1)b(k-1)/k, то n=b(n)>=a(n)/n. Что дает n^2/2<a(n)<=n^2. То, что получается такой чудесный коэффициент, по видимому связано с равномерным распределением остатков.
Да только, указанный предел, скорее всего не существует (думаю это несложно доказать). Речь идёт скорее о пределе $ R(n)=a(n)-\frac{\pi n^2}{4}, \ \lim_{n\to \infty }\frac{R(n)}{n^2}=0$.

[Lion]

Да, Вы правы, сейчас поправлю.
Но, по-моему, в этой задаче интересен именно этот "чудесный коэффициент"...

[maxal]

Это решето носит имя Иосифа Флавия: A000960

[RIP]

Скоро раздел превратится в "запости задачку, на которую maxal не сможет привести ссылку".

[Lion]

Мда... Ну ничего, у меня есть еще задачи, которых, надеюсь, в Сети нет. А вообще-то мне это решето известно под названием "Решето Фабиуса", и, если кому интересно, про него можно прочитать еще и здесь.

[maxal]

Lion писал(а):

А вообще-то мне это решето известно под названием "Решето Фабиуса"

"Фабиус" очень похоже Flavius, возможно, просто неправильное прочтение фамилии Флавия.