Среднее количество множителей в числе

[proba]

Подскажите, известен ли следующий результат.

Берем отрезок $[1, N]$ натурального ряда и фиксируем простое число $p$. Сколько раз в среднем на данном отрезке встречается это $p$ в качестве множителя (с учетом его кратности) в пределе по $N$? Получается, что $1/(p - 1)$ раза.

[nnosipov]

proba в сообщении #830744 писал(а):

Получается, что 1/(p - 1) раза.

Сказано неаккуратно, но в целом правильно. Посмотрите, например, здесь http://oeis.org/wiki/De_Polignac%E2%80% ... re_formula

[proba]

Спасибо. Т.е. искомое количество есть сумма геометрической прогрессии со знаменателем $1/p$. А как избавиться при этом от скобок $\lfloor\rfloor$? А иначе это не вполне очевидно.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

proba
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[whitefox]

proba в сообщении #830754 писал(а):

А как избавиться при этом от скобок $\lfloor\rfloor$?

$\lfloor x \rfloor=x+O(1)$

[nnosipov]

proba в сообщении #830754 писал(а):

А как избавиться при этом от скобок $\lfloor\rfloor$? А иначе это не вполне очевидно.

Нужно оценить

$$ \nu_p(N!)=\sum_{k \geqslant 1} [N/p^k] $$

сверху и снизу. Оценка сверху: просто убираем квадратные скобки. Оценка снизу: заменяем $[N/p^k]$ на $N/p^k-1$ и пользуемся тем, что в сумме относительно мало слагаемых (тоже следует оценить). Вот асимптотически и получится $N/(p-1)$.

[Sonic86]

Можно также вспомнить явную формулу $v_p(n!)=\frac{n-s_p(n)}{p-1},$ где $s_p(n)$ - сумма цифр числа $n$ в $p$-ичной системе счисления. Из нее следуют точные оценки.

[proba]

Хорошо. Теперь мне нужно посчитать две суммы на отрезке $[1, N]$: сумму этих $\frac{1}{p - 1}$ по каждому третьему простому p, начиная с двойки, т.е. по $p = 2, 7, 17, 29, 41, 53, 67, 79, ...,$ и сумму этих $\frac{1}{p - 1}$ по всем простым $p$, чтобы поделить первую сумму на вторую и устремить $N$ к бесконечности.

Обе суммы неограниченно возрастают, хотя и очень-очень медленно, но их отношение вроде бы сходится, вроде бы к $\frac{1}{3}$. Я проверил это на компьютере для $N = 1 000 000 000$. Но поскольку сходимость крайне медленная, никакой уверенности в $\frac{1}{3}$ нет. В принципе асимптота может быть и другой, у меня есть важный аргумент за это. Как бы это проверить без компьютера?

[ИСН]

Грубо говоря, дела такие: как Вы отметили, обе суммы растут неограниченно, так что начало можно отбросить (они всё равно его перерастут и перестанут замечать). А чем дальше - тем ближе будет $1\over p_i-1$ к ${1\over3}\left({1\over p_{i-1}-1}+{1\over p_i-1}+{1\over p_{i+1}-1}\right)$.

[Sonic86]

proba в сообщении #830837 писал(а):

Хорошо. Теперь мне нужно посчитать две суммы на отрезке $[1, N]$: сумму этих $\frac{1}{p - 1}$ по каждому третьему простому p, начиная с двойки, т.е. по $p = 2, 7, 17, 29, 41, 53, 67, 79, ...,$ и сумму этих $\frac{1}{p - 1}$ по всем простым $p$, чтобы поделить первую сумму на вторую и устремить $N$ к бесконечности.

2-я сумма находится через известную формулу
$\sum\limits_{p\leqslant n}\frac{1}{p}=\ln\ln n + B +O(\frac{\ln\ln n}{\ln n}), $, $B$ - постоянная Мертенса (гуглабельно)
1-я сумма может быть оценена аналогично через асимптотику $k$-го простого числа, но член $O(1)$ вряд ли известен и вряд ли представляет интерес (не гуглабельно, короче).

(Оффтоп)

"Каждое третье простое" - это какой-то немного чудаковатый предикат... Более чудаковаты только ряды от геделевских номеров формул какого-нибудь класса.

proba в сообщении #830837 писал(а):

вроде бы к $\frac{1}{3}$

Да, это несложно доказать.

Непонятно, какое отношение имеет исходная задача к этой.

[proba]

ИСН в сообщении #830846 писал(а):

Грубо говоря, дела такие: как Вы отметили, обе суммы растут неограниченно, так что начало можно отбросить (они всё равно его перерастут и перестанут замечать). А чем дальше - тем ближе будет $1\over p_i-1$ к ${1\over3}\left({1\over p_{i-1}-1}+{1\over p_i-1}+{1\over p_{i+1}-1}\right)$.

Нет, это как-то неочевидно.

-- 26.02.2014, 19:56 --

Sonic86 в сообщении #830849 писал(а):

2-я сумма находится через известную формулу
$\sum\limits_{p\leqslant n}\frac{1}{p}=\ln\ln n + B +O(\frac{\ln\ln n}{\ln n}), $, $B$ - постоянная Мертенса (гуглабельно)
1-я сумма может быть оценена аналогично через асимптотику $k$-го простого числа, но член $O(1)$ вряд ли известен и вряд ли представляет интерес (не гуглабельно, короче).

Но ведь у меня слагаемые не $\frac{1}{p}$, а $\frac{1} {p-1}$. Почему суммы одинаковы?

[ИСН]

proba в сообщении #830867 писал(а):

Нет, это как-то неочевидно.

Я и не говорил, что очевидно. Потому это и "грубо говоря". Чтобы стало точно - ещё копать надо.

proba в сообщении #830867 писал(а):

Но ведь у меня слагаемые не $\frac{1}{p}$, а $\frac{1} {p-1}$. Почему суммы одинаковы?

Потому что разница той и этой сумм - конечное число.

[proba]

ИСН в сообщении #830871 писал(а):

Потому что разница той и этой сумм - конечное число.

Не соображу сразу, почему?

-- 26.02.2014, 20:08 --

Sonic86 в сообщении #830849 писал(а):

"Каждое третье простое" - это какой-то немного чудаковатый предикат... Более чудаковаты только ряды от геделевских номеров формул какого-нибудь класса.

Нет, попросту я разбил последовательность простых чисел на три части. Это одна из них. Есть еще две похожие: одна начинается с тройки, другая - с пятерки.

[Sonic86]

proba в сообщении #830874 писал(а):

Не соображу сразу, почему?

Выпишите разницу, преобразуйте, посмотрите на нее, подумайте.

[ИСН]

proba в сообщении #830874 писал(а):

Нет, попросту я разбил последовательность простых чисел на три части. Это одна из них.

Есть бесчисленное количество способов разбить последовательность простых чисел на части, но именно этот встречается исключительно редко.