Число чисел от 1 до n, делящихся только на p=4k+1

[Sonic86]

Найти главный член асимптотики числа чисел от 1 до $n$, которые делятся только на простые вида $p=4k+1$.
Можно какую-нибудь идею или ссылку или книжку.
Пробовал считать отдельно число чисел вида $p_1^{a_1}$, $p_1^{a_1}p_2^{a_2}$,... и потом складывать. Оценки получаются довольно трудоемкими, да и вообще я до конца не довел. М.б. можно проще?

[ИСН]

По-моему, надо обратить взоры в сторону чисел, представимых в виде суммы двух квадратов. Их оценить легче, а эти с ними в родстве.

[Sonic86]

ИСН писал(а):

По-моему, надо обратить взоры в сторону чисел, представимых в виде суммы двух квадратов. Их оценить легче, а эти с ними в родстве.

Думаете? Ладно, попробую, м.б. все-таки это легче. Что-то я про них и забыл

[Хорхе]

(Почерпнуто из этой статьи)

Теорема Вирсинга (тут $p$ обозначает простые числа):
Если $f$ -- мультипликативная функция, причем $f(p^r)\le c_1 c_2^r$, $c_2<2$ и

$$ \sum_{p\le x} f(p) = (\tau + o(1))\frac{x}{\ln x}, x\to\infty. $$

Тогда

$$ \sum_{n\le x} f(n) \sim \frac{e^{-\gamma \tau} }{\Gamma(\tau)}\frac{x}{\ln x}\prod_{p\le x}\Big(\sum_{k\ge 0} \frac{f(p^k)}{p^k}\Big). $$

Ну и вроде кагбе можно посчитать.

[Хорхе]

Если почитать указанную статью чуть дальше, то там явно указана нужная Вам асимптотика. Но из теоремы Вирсинга и теоремы о распределении простых в арифметических прогрессиях главный член асимптотики получается довольно легко (сужу по тому, что даже моему тупому уму это удалось), так что можете попробовать сами.

-- Вт апр 20, 2010 12:23:35 --

Лично у меня как-то слабо в голове укладывается, что этих чисел лишь ненамного меньше, чем сумм двух квадратов.

То есть чуть менее, чем половина чисел, представимых в виде суммы двух квадратов, вообще не делится на простые вида $4k+3$.

[RIP]

А есть ещё более классическая теорема Ландау, которая утверждает примерно следующее.

Пусть $q$ --- натуральное число, $a_1,\ldots,a_r$ --- целые числа, взаимно простые с $q$ и попарно несравнимые по модулю $q$. Тогда количество натуральных чисел $\le x$, которые делятся только на простые, сравнимые с одним из $a_\nu\pmod q$, есть $\sim\frac{Cx}{(\ln x)^{1-r/\varphi(q)}}$ для некоторой постоянной $C=C(q,a_1,\ldots,a_r)>0$.

Есть мнение, что док-во можно найти в книге: E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd. II, Leipzig, Teubner, 1909. У меня книжки нет, поэтому не скажу, какая там оценка остаточного члена. Также док-во (и ещё кучу всякого вкусного; в частности, теорема Вирзинга там тоже есть) можно найти, например, в книжке А.Г. Постникова "Введение в аналитическую теорию чисел" (взять можно здесь). (Особенно порекомендую почитать пункт 4.11, где, в частности, выводится асимптотическое разложение для сумм двух квадратов.)

[Sonic86]

Спасибо большое всем ! Я и не знал, что такие результаты есть, буду читать.