Явная формула функции распределения простых чисел

[ifedorovich]

Приводится формула функции распределения простых чисел в явном виде,
т.е. без рекурсии, без величин, определение которых связано с самой функцией,
конечная по сумме.

Вот она:

\pi(n)=n-1-\sum_{i=2}^{\left[\sqrt{n}\right]}\left(\left[\frac{n}{i}\right]-i+1\right)+\sum_{s=2}^{\left[\sqrt{n}\right]}(-1)^{s}\sum_{1<i_1<i_2<\ldots<i_s\le\left[\sqrt{n}\right]}\left(\left[\frac{n}{HOK(i_1,i_2,\ldots,i_s)}\right]-\left[\frac{i_s^2-1}{HOK(i_1,i_2,\ldots,i_s)}\right]\right).


Где \pi(n) - число простых чисел, меньших или равных {n} (функция распределения простых чисел),
\left[x\right] - целая часть числа {x},
HOK(i_1,i_2,\ldots,i_s) - наименьшее общее кратное набора целых чисел i_1,i_2,\ldots,i_s.

Проблема древняя, решение новое. Предлагается проверить.

[venco]

Если я не ошибся, это тривиальное применение формулы включений-исключений. Практического смысла не имеет, т.к. объём суммирования очень большой. Кстати, во второй сумме верхний предел можно существенно уменьшить.

[maxal]

ifedorovich
Еще немного и вы переоткроете формулу Лежандра:
http://mathworld.wolfram.com/LegendresFormula.html

Ранее у нас уже была подобная попытка: post235983.html

[venco]

Не совсем понятно, зачем в суммируемых выражениях лишние $i$ и $i_s^2-1$. Можно и без них.

[ifedorovich]

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

ifedorovich
Еще немного и вы переоткроете формулу Лежандра:
http://mathworld.wolfram.com/LegendresFormula.html

Ранее у нас уже была подобная попытка: post235983.html

В процессе доказательства, здесь также была получена формула с рекурсией, похожая на приведенную Вами.
Как мне кажется, это нормально, объект исседований - один и тот же.

-- Сб июл 24, 2010 07:38:50 --

venco в сообщении #340244 писал(а):

Если я не ошибся, это тривиальное применение формулы включений-исключений. Практического смысла не имеет, т.к. объём суммирования очень большой. Кстати, во второй сумме верхний предел можно существенно уменьшить.

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

[venco]

ifedorovich в сообщении #340596 писал(а):

Формула дает наглядное понимание детерминированности этого ряда,
глубины зависимости, нелинейности и ассимптотики внутри него.

Ну и какую ассимптотику Вы увидели?

[ifedorovich]

venco в сообщении #340248 писал(а):

Не совсем понятно, зачем в суммируемых выражениях лишние $i$ и $i_s^2-1$. Можно и без них.

Данные части формулы не лишние, можете убедиться в этом,
запрограммировав вычисление формулы.

-- Сб июл 24, 2010 08:20:31 --

venco в сообщении #340597 писал(а):

ifedorovich в сообщении #340596 писал(а):

Формула дает наглядное понимание детерминированности этого ряда,
глубины зависимости, нелинейности и ассимптотики внутри него.

Ну и какую ассимптотику Вы увидели?

Самым простым первым шагом может быть следующий.

Откинув последнюю двойную сумму (она неотрицательна) имеем:

\pi(n)\geqslant n-1-\sum_{i=2}^{\left[\sqrt{n}\right]}\left(\left[\frac{n}{i}\right]-i+1\right)= n-1+\sum_{i=1}^{\left[\sqrt{n}\right]-1}i-\sum_{i=2}^{\left[\sqrt{n}\right]}\left[\frac{n}{i}\right]\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{n}{i}\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-n\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{1}{i}

Последняя сумма, как Вы знаете, ассимптотически эквивалентна $\frac{1}{2}ln(n)$.

[hurtsy]

ifedorovich в сообщении #340596 писал(а):

Формула дает наглядное понимание детерминированности этого ряда,
глубины зависимости, нелинейности и ассимптотики внутри него.

В интервале $(1,4) $ детерминированность видна невооруженным глазом, все простые
$ \begin {array} {c} 2 $ 3 \end {array} $ .

Глубины зависимости - очень хочется увидеть в нескольких слова, что это значит.

Нелинейностью у которой рост меньший роста прямой линии (логарифмическая), наверное не на dxdy потрясать воображение.

ifedorovich в сообщении #340598 писал(а):

Последняя сумма, как Вы знаете, ассимптотически эквивалентна .

Перед помянутой суммой есть множитель $n$.

С уважением,

[venco]

ifedorovich в сообщении #340598 писал(а):

Откинув последнюю двойную сумму (она неотрицательна) имеем:

\pi(n)\geqslant n-1-\sum_{i=2}^{\left[\sqrt{n}\right]}\left(\left[\frac{n}{i}\right]-i+1\right)= n-1+\sum_{i=1}^{\left[\sqrt{n}\right]-1}i-\sum_{i=2}^{\left[\sqrt{n}\right]}\left[\frac{n}{i}\right]\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{n}{i}\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-n\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{1}{i}

Последняя сумма, как Вы знаете, ассимптотически эквивалентна $\frac{1}{2}ln(n)$.

Т.е. $\pi(n) > 0$, т.к. выражение справа - отрицательно при $n>31$.

[ifedorovich]

hurtsy в сообщении #340622 писал(а):

ifedorovich в сообщении #340596 писал(а):

Формула дает наглядное понимание детерминированности этого ряда,
глубины зависимости, нелинейности и ассимптотики внутри него.

В интервале $(1,4) $ детерминированность видна невооруженным глазом, все простые
$ \begin {array} {c} 2 $ 3 \end {array} $ .

Глубины зависимости - очень хочется увидеть в нескольких слова, что это значит.

Нелинейностью у которой рост меньший роста прямой линии (логарифмическая), наверное не на dxdy потрясать воображение.

ifedorovich в сообщении #340598 писал(а):

Последняя сумма, как Вы знаете, ассимптотически эквивалентна .

Перед помянутой суммой есть множитель $n$.

С уважением,

Детерминированность ряда простых чисел следует уже из существования такой формулы, которая приведена)
Если у Вас есть другая формула, которая не содержит в правой части неопределенных заранее величин
(или рекурсивно связанных величин) для $\pi(n)$, поделитесь, пожалуйста.

Глубина зависимости $\left[\sqrt{n}\right]$.

Именно поэтому пишу: "последняя сумма", а не последнее слагаемое.

-- Вс июл 25, 2010 05:33:36 --

venco в сообщении #340636 писал(а):

ifedorovich в сообщении #340598 писал(а):

Откинув последнюю двойную сумму (она неотрицательна) имеем:

\pi(n)\geqslant n-1-\sum_{i=2}^{\left[\sqrt{n}\right]}\left(\left[\frac{n}{i}\right]-i+1\right)= n-1+\sum_{i=1}^{\left[\sqrt{n}\right]-1}i-\sum_{i=2}^{\left[\sqrt{n}\right]}\left[\frac{n}{i}\right]\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{n}{i}\geqslant n-1+\frac{\left(\left[\sqrt{n}\right]-1\right)\left[\sqrt{n}\right]}{2}-n\sum_{i=2}^{\left[\sqrt{n}\right]}\frac{1}{i}

Последняя сумма, как Вы знаете, ассимптотически эквивалентна $\frac{1}{2}ln(n)$.

Т.е. $\pi(n) > 0$, т.к. выражение справа - отрицательно при $n>31$.

Совершенно верно, более того, начиная с $n=16$ появляются значимые слагаемые в отброшенной сумме.
Поэтому первый шаг к ассимптотической оценке работает хорошо для первых 15 чисел, для следующих - нужно оценивать части оставшейся суммы.

[gris]

Хорошо звучит: асимптотика для первых 16 чисел работает!

ЗЫ Уберу, раз это Вас раздражает. Я цветом обозначаю оффтоп. Я же без всякой иронии. Просто понравилось выражение. Может быть и правда там смысл, который мне не понятен.

[ifedorovich]

Спасибо за орфографические правки.

Специально Вам для понимания - асимптотика описывает поведение функции в особых точках,
чаще всего (но не обязательно) при стремлении аргумента или функции к бесконечности.

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

Для меня первые числа $\pi(n)$ ничуть не менее важны, чем остальные.
Если Вы знаете более простое арифметическое выражение через элементарные составляющие -
приводите, будет интересно посмотреть.

[hurtsy]

1984 г. ноябрь —декабрь т. 39, вып. 6(240)
УСПЕХИ МАТЕМАТИЧЕСКИХ НАУК
ПЕРВЫЕ 50 МИЛЛИОНОВ ПРОСТЫХ ЧИСЕЛ
Д о н Ц а г ер

Цитата:

наконец, в последнее время специалисты в области математической
логики стали определять простые числа как положительные значения
полинома (2)

$ F (a, b, c, d, e, f, g, h, i, j,k, l, m , n, o, p, q, r, s, t, u, v, w, x, y, z) = $ $ (k + 2)(1 - (wz + h + j - q)^2 - (2n + p + q + z - e)^2 - $
$(a^2y^2 - y^2 + 1 - x^2)^2 - ((e^4 + 2e^3) (a + 1)^2 + 1 - o^2)^2 - $ $ (16 (k + 1)^3(k + 2 ) (n + 1 )^2 + 1 - f^2 )^2 -$
$ (((a + u^4 - u^2a)^2 - 1 ) (n + 4dy)^2 + 1 - (x+ cu)^2)^2 - (ai + k +1 - l - i)^2 -$
$- ((gk + 2g + k+ 1) (h + j) + h - z)^2 - (16r^2y^4 (a^2 - 1) + 1 - u^2)^2 -$
$ - (p - m + l (a - n - 1) + b (2an + 2a - n^2 - 2n - 2))^ 2 - $
$ - (z - pm +pla- p^2l +t (2ap - p^2 - 1))^2 - (q - x +y(a - p - $
$ - 1) + s (2ap + 2a - p^2 - 2p - 2))^2 - (a^2l^2 - l^2 + 1 - m^2)^2 -$
$- (n+l+v-y)^2). $

(2) J. P. J o n e s . Diophantine representation of the set of prime numbers.— Notices
of the AMS, 1975, 22, p. A-326.

Не знаю то ли это что Вы хотели. С уважением,

[hurtsy]

Поищите в Google Matijasevic's polynomial
С уважением,

[serval]

А формула "распределения простых чисел" заявленная автором дает возможность вычисления следующего простого по известным предыдущим? Если нет - какой в ней прок?