E

[vorvalm]

Апис в сообщении #791651 писал(а):

vorvalm Я понимаю вовлекать в свою работу (за просто так) посторонних неприлично, потому и предлагаю в порядке дискуссии опровергнуть мои рассуждения. Но если в ходе дискуссии, кто докажет неравенство, тогда: Здесь сейчас и везде дальше обязательное об этом сообщение.

Это вы о чем?

[Апис]

Так, подумалось, меня уже раз обвинил один из Германии, что сообщения в моём блоге, что то вроде деньги зарабатывать на рекламе. Забудь.

[vorvalm]

Что означает выражение

$n\prod_{i=1}^n\frac{p_i-1}{p_i}$

[Апис]

vorvalm в сообщении #791664 писал(а):

Что означает выражение

Я кратко не могу ответить. Почему пришлось вставить (n) объяснил выше, а потом просто открывал скобки и это выражение вылезло. Тут такое дело, один раз подумаю вроде правильно, другой раз не правильно. Путём рассуждений трудно прийти к истине, вот может неравенство поможет проверить истинность рассуждений. Хотя может быть и случайное попадание в истину. Это самое плохое.

[Апис]

$\frac{1}{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }} - 1 > \frac{x}{{\pi \left( x \right) - n}} > \frac{1}{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}$

$p_n^2 \le x < p_{n + 1}^2$

Это неравенство эквивалентно

Апис в сообщении #791651 писал(а):

$x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - x{\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)^2} - n\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}} + n} < \pi (x) < x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} + n$

[Апис]

Или такое неравенство

$\frac{x}{{x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}} + n} }} - 1 > \frac{x}{{\pi \left( x \right)}} > \frac{x}{{x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}} + n} }}$

Но кажется это пустое, значение (Е) надо искать исходя из внутренних возможностей формулы алгоритма. А сравнивать, трудно сравнить, когда одна формула для интервала (0,x), а другая для интервала $\left( {{p_n},x} \right)$
Хотя если взять результат суммирования количества простых чисел между квадратами простых соседних чисел. То можно убрать значение (n).

И получим $\frac{1}{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }} - 1 > \frac{x}{{\pi \left( x \right)}} > \frac{1}{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}$
Вроде бы с этим неравенством можно работать

[Апис]

$\frac{1}{{\left( {1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)}} > \frac{x}{{\pi \left( x \right)}} > \frac{1}{{\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)}}$

Поспешил всё надо проверить вроде бы такой вид неравенства

[Апис]

Что бы уменьшить погрешность вычисления достаточно разделить формулу алгоритма решета Эратосфена $\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ на две части.

$x\left( {\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} - 1 - \frac{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}{{\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} }}} \right)$ количество простых чисел на интервале $\left( {{p_{n,}}x} \right)$

$p_n^2 \le x < p_{n + 1}^2$

Например: n=133 x=564001 $x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ = 47537,67242237884
Количество по таблице – 46236.
Погрешность вычисления (Е) - 1301,672422378837

Возьмём произвольно значение (t) = 3 (n-t) =130

$x\left( {\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} - 1 - \frac{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}{{\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} }}} \right)$ = 564001(0,0846271466812175 – 1 - 0,9959747798718989) =564001(0,0806019265531164)= 45459,56717788421

Е=-776,4328221157914

Или ещё пример, возьмём значение (t) =1

$x\left( {\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} - 1 - \frac{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}{{\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} }}} \right)$ =564001(0,0843988857920619-1- 0,9986684420772298) = 564001*0,0830673278692917= 46850,05598560837
Е = 614,05598560837
Значит направление поиска выбрано правильно. Деление формулы алгоритма на две части.

[Апис]

Прежде чем искать ответ на вопрос, решил показать, как возник вопрос. Если будет найден изъян в рассуждениях, вопрос отпадёт сам собой.
Определения:

$\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ - Формула алгоритма простых чисел, решета Эратосфена.

$1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ - Формула алгоритма. Для составных чисел

$x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ - Формула для вычисления количества простых чисел на интервале, $\left( {{p_{n,}}x} \right)$. $p_n^2 \le x < p_{n + 1}^2$

Q – Количество простых чисел на интервале, $\left( {{p_{n,}}x} \right)$. (Табличное значение).

E – Погрешность вычисления количества простых чисел, $x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - Q = E$

(-E) - Погрешность вычисления количества составных чисел.


Перемножив, две формулы алгоритма, для простых чисел и для составных чисел получим: $\left( {1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} = \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - {\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)^2}$

Формула для вычисления количества простых чисел на интервале, $\left( {{p_{n,}}x} \right)$. Будет иметь вид, $x \cdot \left[ {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - {{\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)}^2}} \right]$. соответственно погрешность вычисления, $x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - Q = E$, уменьшится на величину, $\x{\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)^2}$, и будет равна, $E - x{\left( {\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)^2}$

Замена обозначения формулы алгоритма не букву (а), $\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} = a$, упростит дальнейшие выкладки.

$1)E$

$\begin{array}{l} 2)a(1 - a) = a - {a^2} \\ xa - x{a^2} \\ E - x{a^2} = {E_1} \\ \end{array}$

$\begin{array}{l} 3)a - {a^2} = {a_1} \\ {a_1}(1 - {a_1}) = {a_1} - a_1^2 \\ x{a_1} - xa_1^2 \\ {E_1} - xa_1^2 = {E_2} \\ \end{array}$

$\begin{array}{l} 4){a_1} - a_1^2 = {a_2} \\ {a_2}(1 - {a_2}) = {a_2} - a_2^2 \\ x{a_2} - xa_2^2 \\ {E_2} - xa_2^2 = {E_3} \\ \end{array}$

.......

Доказать:

$E - {E_1} - {E_2} - {E_3} - ... - {E_t} \ge 0$

Сомнительный момент, какое значение (t) брать.
(t)=n. Или (t)→∞.
И начинать доказательство с простых чисел, с которых (Е) постоянно растёт по величине. Это где то на первом или втором десятке.

[Апис]

Доказать, $E - {E_1} - {E_2} - {E_3} - ... - {E_t} \ge 0$, Не корректно поставлен вопрос. Дело в том, что значение (Е) неизвестно.
А вот доказать что сумма ряда, ${E_1} + {E_2} + {E_3} + ... + {E_t}$, не превышает некое число.
Это было бы полезно для проблемы определения погрешности

[Апис]

Сомнительное место в рассуждениях легко объясняется. Если интервал, на котором, вычисляем количество простых чисел, находится в рамках интервала (вообще то так и должно быть) $\left( {p_n^2,p_{n + 1}^2} \right)$, и он равен $x - p_n^2 = 1$, Значение (t) можно найти по формуле $\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} = {E_1} + {E_2} + {E_3} + ... + {E_t}$

[Апис]

Как можно найти простое решение?

$p_{n + 1}^2\left( {1 - \prod\limits_{i = 1}^{n + 1} {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)$ - Количество составных чисел с отрицательной погрешностью вычисления. $p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ - Количество простых чисел с положительной погрешностью вычисления. Складываем, погрешности погашаются. Отнимаем результат от, $p_{n + 1}^2$ и получаем, количество простых чисел на интервале, $\left( {p_n^2,p_{n + 1}^2} \right)$ с минимальной погрешностью.

Например:

$p_{n + 1}^2 - \left[ {p_{n + 1}^2\left( {1 - \prod\limits_{i = 1}^{n + 1} {\frac{{{p_i} - 1}}{{{p_i}}}} } \right) + p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right]$

$\begin{array}{l} {p_n} = 751 \\ {p_{n + 1}} = 757 \\ \end{array}$

$\left( {p_{n + 1}^2 - p_n^2} \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} = {\rm{762}}{\rm{,6242862648891}}$

Табличное значение количества простых чисел на интервале $\left( {p_n^2,p_{n + 1}^2} \right)$=695

$p_{n + 1}^2 - \left[ {p_{n + 1}^2\left( {1 - \prod\limits_{i = 1}^{n + 1} {\frac{{{p_i} - 1}}{{{p_i}}}} } \right) + p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right]$=698,819402898063

Сравниваем. Формула, $p_{n + 1}^2 - \left[ {p_{n + 1}^2\left( {1 - \prod\limits_{i = 1}^{n + 1} {\frac{{{p_i} - 1}}{{{p_i}}}} } \right) + p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right]$, на интервале $\left( {p_n^2,p_{n + 1}^2} \right)$ даёт количество простых чисел точнее, чем формула $\left( {p_{n + 1}^2 - p_n^2} \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $

И вопрос, вынесенный в заголовок сообщения. Как можно найти простое решение?
Ответ. Никак. Решение приходит само по себе, и когда само захочет.

[megamix62]

Апис в сообщении #792938 писал(а):

Что бы уменьшить погрешность вычисления достаточно разделить формулу алгоритма решета Эратосфена $\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ на две части.

$x\left( {\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} - 1 - \frac{{\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} }}{{\prod\limits_{i = 1}^{n - t} {\frac{{{p_i} - 1}}{{{p_i}}}} }}} \right)$ количество простых чисел на интервале $\left( {{p_{n,}}x} \right)$

$p_n^2 \le x < p_{n + 1}^2$

Например: n=133 x=564001 $x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $ = 47537,67242237884
Количество по таблице – 46236.
Погрешность вычисления (Е) - 1301,672422378837

$564001/(\ln(564001)-1.08)=46370,940$
$\pi(564001)=46369$

Погрешность вычисления $E = 1.94$

$\pi(564001)-133=46369-133 = 46236$

И зачем все было это городить

[Апис]

$p_n^2 \le x < p_{n + 1}^2$

Q – Количество простых чисел на интервале, $\left( {{p_{n,}}x} \right)$ (Табличное значение).

E – Погрешность вычисления, $x\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - Q = E$

$x\left( {1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right)$, - Количество составных чисел с отрицательной погрешностью вычисления.

$p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} $, - Количество простых чисел с положительной погрешностью вычисления.

Складываем, погрешности погашаются. Отнимаем результат от, (x) и получаем, количество простых чисел на интервале, $\left( {p_n^2,x} \right)$, с минимальной погрешностью.

$x - \left[ {x\left( {1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right) + p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right]$, - Формула для вычисления количества простых чисел на интервале, $\left( {p_n^2,x} \right)$

При помощи этой формулы можно сократить интервал, $\left( {p_n^2,x} \right)$, до значений одного простого числа на интервале.
То есть эту формулу можно использовать как тест, определения числа на простоту.
Например: 564013 простое число?
(x)=564013

$x - \left[ {x\left( {1 - \prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right) + p_n^2\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} } \right]$==564013-(516474,3161395757+47537,67242237884)= 1,011438045462988

(x)=564012

564012-(516473,4004260795+47537,67242237884)= 0,9271515416541349

564013- простое число, формула даёт результат больше единицы.

megamix62 в сообщении #822972 писал(а):

И зачем все было это городить

Интересно, любопытно, и с удовольствием.

[Апис]

2.
Погрешность вычисления
$p_n^2 \pm a$, (a)<1

На интервалах,

$\begin{array}{l} \left( {\left( {p_n^2 - a} \right),p_n^2} \right) \\ \left( {p_n^2,\left( {p_n^2 + a} \right)} \right) \\ \end{array}$

нет простых чисел, так как интервалы меньше единицы. Воспользуемся формулами, $\begin{array}{l} \left( {p_n^2 - a} \right)\prod\limits_{i = 1}^{n - 1} {\frac{{{p_i} - 1}}{{{p_i}}}} \\ \left( {p_n^2 + a} \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} \\ \end{array}$ при помощи которых вычисляем количество простых чисел на интервалах, $\begin{array}{l} \left( {{p_n},\left( {p_n^2 - a} \right)} \right) \\ \left( {{p_n},\left( {p_n^2 + a} \right)} \right) \\ \end{array}$
Разница, $\left( {p_n^2 + a} \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - \left( {p_n^2 - a} \right)\prod\limits_{i = 1}^{n - 1} {\frac{{{p_i} - 1}}{{{p_i}}}} $ должна быть нулевая так как. На интервалах, $\begin{array}{l} \left( {\left( {p_n^2 - a} \right),p_n^2} \right) \\ \left( {p_n^2,\left( {p_n^2 + a} \right)} \right) \\ \end{array}$, нет простых чисел.

Значит величина разницы, $\left( {p_n^2} \right)\prod\limits_{i = 1}^n {\frac{{{p_i} - 1}}{{{p_i}}}} - \left( {p_n^2} \right)\prod\limits_{i = 1}^{n - 1} {\frac{{{p_i} - 1}}{{{p_i}}}} $есть не что иное, как погрешность вычисления.

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