Число простых делителей всех нечетных чисел до заданного n

[Батороев]

Интересно, какие существуют методы решения следующей задачи:
Рассчитать общее число простых делителей всех нечетных чисел до $n=1000$.

[maxal]

Если с учетом кратности, то это будет количество простых делителей (опять же с учетом кратности) числа $n!! = \frac{n!}{2^{(n-1)/2}((n-1)/2)!}$ ($n$ - нечетно).

[Батороев]

Рассматривая сначала учетом кратности, нельзя затем как-то прийти к общему числу делителей?

[ИСН]

"C учётом кратности" может быть понимаемо двояко. 1000 - это очень много, возьмём для простоты 4. Здесь их два (2 и 3), или три (2, 3, и опять 2), или четыре (2, 3 и ещё 2 раза 2). Вы что из этого хотите?

[Батороев]

Возьму для пояснения числа до 10. Рассмотрим нечетные числа:
у числа 1 - 0 простых делителей, у 3 - 1 делитель, у 5 - 1 делитель, у 7 - 1 делитель, у 9 - 2 делителя.
Итого: у нечетных чисел до 10 в сумме 0+1+1+1+2=5 простых делителей.
Вот это "итого" я и хотел бы получить, но для бОльших чисел.

-- Пн сен 21, 2009 21:25:52 --

maxal в сообщении #245209 писал(а):

Если с учетом кратности, то это будет количество простых делителей (опять же с учетом кратности) числа $n!! = \frac{n!}{2^{(n-1)/2}((n-1)/2)!}$ ($n$ - нечетно).

У Вас $n!!$ - это, вроде бы, двойной факториал нечетных чисел, т.е. их произведение. А мне б как-нибудь узнать, сколько в нем простых делителей?
Под словами "с учетом кратности" что подразумевается? Или это все же "с учетом четности"?

[maxal]

Батороев в сообщении #245248 писал(а):

у 9 - 2 делителя.

Вот это и значит с учетом кратности.
Без учета кратности - у 9 один простой делитель: 3.

Степень простого $p$ в разложении $m!$ равна

$$\lfloor m/p\rfloor + \lfloor m/p^2\rfloor + \lfloor m/p^3\rfloor + \dots$$

Отсюда легко получить, что вам требуется...

[Батороев]

Спасибо, maxal!
Покрутил предложенное Вами выражение и получил то, что хотел.
Правда, записать полученное оказалось сложнее.

$$ k(m)=\sum \limits_{p_i<m; p\ne 2}\left(\sum\limits_{l_i=1}^{r_i}\lfloor m/p_i^{l_i}\rfloor - \sum\limits_{t_i=1}^{s_i}\lfloor m/2p_i^{t_i}\rfloor\right) $$

где $k(m)$ - количество всех простых делителей нечетных чисел до $m$,

$r_i=\lfloor\log_{p_i} m\rfloor$, $s_i = \lfloor\log_{p_i}{\frac {m}{2}}\rfloor$.

И возник другой интересный вопрос:
Существует ли предел отношения $\dfrac {2k(m)}{m}$ и чему равен, если существует?

[ИСН]

Плюсбесконечности. Потому что, грубо говоря, $\sum{1\over p_i}$ расходится, только очень-очень медленно.

[Батороев]

Что-то уж больно медленно он растет!
Я пока к $2$ никак приблизиться не могу ($ m<10^{13}$). Может, я все же не правильно считаю? Помогите, кто чем может!

Упомянутый показатель (отношение) - это среднее количество простых, приходящееся на одно нечетное число, не превышающее $m$.

-- Вт сен 22, 2009 13:07:49 --

Как представлю себе плюсбесконечность делителей, приходящихся на одно нечетное число, жутко становится! Где же там место для простых чисел?

-- Вт сен 22, 2009 13:36:34 --

"Застрял" на $ \dfrac {2\cdot k(m)}{m} = 1,865388703 $.

-- Вт сен 22, 2009 13:55:21 --

"Застрял" из-за того, что в одной командной строке не переключил значения.
Да! Видать медленно-медленно, но будет расти, как и обещал ИСН.

-- Вт сен 22, 2009 16:36:33 --

Вывел формулу для расчета количества всех делителей нечетных чисел, не кратных 3:

$$ k(m)_{2,3}=\sum \limits_{p_i<m; p\ne 2}\left(\left(\sum\limits_{l_i=1}^{r_i}\lfloor m/p_i^{l_i}\rfloor - \sum\limits_{t_i=1}^{s_i}\lfloor m/2p_i^{t_i}\rfloor\right) -\left(\sum\limits_{a_i=1}^{b_i}\lfloor m/3p_i^{a_i}\rfloor - \sum\limits_{c_i=1}^{d_i}\lfloor m/6p_i^{c_i}\rfloor\right) - \lfloor \dfrac {m}{6}\rfloor\right)$$

где $k(m)_{2,3}$ - количество всех простых делителей чисел до $m$, не кратных 2 и 3.

$r_i=\lfloor\log_{p_i} m\rfloor$, $s_i = \lfloor\log_{p_i}{\frac {m}{2}}\rfloor$, $b_i = \lfloor\log_{p_i}{\frac {m}{3}}\rfloor$, $d_i = \lfloor\log_{p_i}{\frac {m}{6}}\rfloor$

Хочется в оконцовке проверить:
при исключении некоторого набора простых чисел (на данный момент исключены 2, 3), всегда ли по мере увеличения m будет расти указанное выше отношение?