Распределение взаимнопростых чисел в примориалах.

[Батороев]

vicvolf в сообщении #1696112 писал(а):

Однако это частный случай.

Наверное - это частныый случай какой-то другой системы, которой Вы руководствуетесь. Для моей системы расчетов - это ОСНОВНОЙ случай.

-- 02 авг 2025 14:37 --

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

Я должен был записать первый интервал точнее: $0..7,5$.

И здесь поправлю:

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

Только у меня было желание для расчета числа простых, разбить примориал до интервала от $1$ до $p_{i}^2$

Следует читать: "от $0$ до $p_{i}^2$".

[vicvolf]

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

Следует читать: "от $0$ до $p_{i}^2$".

Ну здесь Ваш основной вариант не проходит. Надо оценивать ошибку. Посмотрим, для каких $j$ выполняется оценка.

Неравенство $ L = p_j^2 > N^{\ln 2 + \epsilon} $, где $ N = p_j\# $ (примориал, произведение первых $ j $ простых чисел), выполняется для некоторого $ \epsilon > 0 $.

Ключевое условие равносильно $ p_j^2 > (p_j\#)^{\ln 2 + \epsilon} $. Поскольку $ \epsilon > 0 $ можно выбрать сколь угодно малым, неравенство выполняется для некоторого $ \epsilon > 0 $ тогда и только тогда, когда $ p_j^2 > (p_j\#)^{\ln 2} $ (так как если $ p_j^2 > (p_j\#)^{\ln 2} $, то существует достаточно малое $ \epsilon > 0 $, обеспечивающее строгое неравенство с показателем $ \ln 2 + \epsilon $).

Вычислим значения для малых $ j $:
- $ j = 1 $:
- $ p_1 = 2 $, $ N = 2\# = 2 $, $ L = 2^2 = 4 $,
- $ N^{\ln 2} = 2^{\ln 2} \approx 1.62 $,
- $ 4 > 1.62 $ — выполняется.
- $ j = 2 $:
- $ p_2 = 3 $, $ N = 2 \times 3 = 6 $, $ L = 3^2 = 9 $,
- $ N^{\ln 2} = 6^{\ln 2} \approx 3.34 $,
- $ 9 > 3.34 $ — выполняется.
- $ j = 3 $:
- $ p_3 = 5 $, $ N = 2 \times 3 \times 5 = 30 $, $ L = 5^2 = 25 $,
- $ N^{\ln 2} = 30^{\ln 2} \approx 8.20 $,
- $ 25 > 8.20 $ — выполняется.
- $ j = 4 $:
- $ p_4 = 7 $, $ N = 2 \times 3 \times 5 \times 7 = 210 $, $ L = 7^2 = 49 $,
- $ N^{\ln 2} = 210^{\ln 2} \approx 40.72 $,
- $ 49 > 40.72 $ — выполняется.
- $ j = 5 $:
- $ p_5 = 11 $, $ N = 2 \times 3 \times 5 \times 7 \times 11 = 2310 $, $ L = 11^2 = 121 $,
- $ N^{\ln 2} = 2310^{\ln 2} \approx 215.0 $,
- $ 121 < 215.0 $ — **не выполняется**.
- $ j \geq 6 $:
- Например, $ j = 6 $: $ p_6 = 13 $, $ N = 30030 $, $ L = 169 $, $ N^{\ln 2} \approx 1260 $, $ 169 < 1260 $ — не выполняется.
- С ростом $ j $ разрыв увеличивается: $ p_j\# $ растет быстрее $ p_j^2 $, так как примориал эквивалентен $ e^{p_j} $ по асимптотике, а $ p_j^2 $ растет медленнее любой экспоненты.

Неравенство $ p_j^2 > (p_j\#)^{\ln 2} $ асимптотически эквивалентно:
$2 (\ln j + \ln \ln j) > \ln 2 \cdot j \ln j,$
что неверно для больших $ j $, так как правая часть растет быстрее левой.

Неравенство $ L > N^{\ln 2 + \epsilon} $ выполняется для некоторого $ \epsilon > 0 $ только при $ j \leq 4 $. Таким образом, неравенство выполняется для $ j = 1, 2, 3, 4 $. Для $ j \geq 5 $ оно неверно ни при каком $ \epsilon > 0 $. Ну это еще не приговор.

[vicvolf]

vicvolf в сообщении #1696142 писал(а):

Ну это еще не приговор.

Проверка равномерности распределения вычетов для $N = 2310$ (примориал $p_5\#$) с длиной интервала $L = p_j^2 = 11^2 = 121$

Модуль: $N = p_5\# = 2 \times 3 \times 5 \times 7 \times 11 = 2310$.
Функция Эйлера: $\phi(N) = \phi(2310) = 480$ (количество вычетов, взаимно простых с $N$).
- Длина интервала: $L = 121$.
- Ожидаемое количество вычетов в интервале длины $L$:
$ E = L \cdot \frac{\phi(N)}{N} = 121 \cdot \frac{480}{2310} = \frac{121 \times 16}{77} \approx 25.1429. $

Результаты подсчёта для 10 последовательных интервалов длины 121:
Рассмотрены интервалы $[k \cdot 121, (k+1) \cdot 121)$ для $k = 0, 1, \dots, 9$. Фактическое количество вычетов ($\pi$) и отклонение от $E$ (т.е. $|\pi - E|$) подсчитаны программно. Результаты:
| Интервал ($k$) | Границы интервала | Фактическое количество вычетов ($\pi$) | Отклонение ($|\pi - E|$) |
|------------------|-------------------|-----------------------------------------|----------------------------|
| 0 | $[0, 121)$ | 26 | 0.8571 |
| 1 | $[121, 242)$ | 25 | 0.1429 |
| 2 | $[242, 363)$ | 24 | 1.1429 |
| 3 | $[363, 484)$ | 26 | 0.8571 |
| 4 | $[484, 605)$ | 25 | 0.1429 |
| 5 | $[605, 726)$ | 25 | 0.1429 |
| 6 | $[726, 847)$ | 24 | 1.1429 |
| 7 | $[847, 968)$ | 26 | 0.8571 |
| 8 | $[968, 1089)$ | 26 | 0.8571 |
| 9 | $[1089, 1210)$ | 25 | 0.1429 |

Статистика отклонений:
- Минимальное отклонение: $0.1429$.
- Максимальное отклонение: $1.1429$.
- Среднее абсолютное отклонение:
$ \frac{0.8571 + 0.1429 + 1.1429 + 0.8571 + 0.1429 + 0.1429 + 1.1429 + 0.8571 + 0.8571 + 0.1429}{10} \approx 0.632. $
- Стандартное отклонение: $\approx 0.428$.

1. Фактические отклонения:
- Отклонения малы: все $|\pi - E| < 1.15$.
- Среднее отклонение $\approx 0.632$ существенно меньше ожидаемого значения $E \approx 25.1429$ (относительная погрешность $\approx 2.5\%$).

2. Сравнение с асимптотической оценкой Руста:
- Для $N = 2310$, $N^{\ln 2} \approx 215.0$ (где $\ln 2 \approx 0.693$).
- Оценка ошибки: $O(N^{\ln 2 + \epsilon}) \approx 215$ (для малого $\epsilon > 0$).
- Фактические отклонения ($\leq 1.15$) значительно меньше оценки $215$.

3. Причина расхождения:
- Условие $L > N^{\ln 2 + \epsilon}$ не выполняется: $L = 121 < 215$.
- Асимптотическая оценка $O(N^{\ln 2 + \epsilon})$ является верхней границей и может быть пессимистичной для конкретных $N$.
- Фактическое распределение вычетов более равномерно, чем предсказывает оценка, особенно для малых $j$.

Для $N = 2310$ и $L = 121$:
- Распределение вычетов практически равномерно: отклонения не превышают $1.15$.
- Оценка $O(N^{\ln 2 + \epsilon})$ завышена (дает $215$, реальные отклонения в $200$ раз меньше).
- Это подтверждает, что асимптотическая оценка не оптимальна для малых $j$, но остается корректной (так как $1.15 < 215$).

Для больших $j$ (например, $j \geq 10$) условие $L > N^{\ln 2 + \epsilon}$ не выполняется, и оценка становится менее информативной. В таких случаях требуются более точные методы (например, гипотеза Римана).

[Батороев]

vicvolf в сообщении #1696142 писал(а):

Ну здесь Ваш основной вариант не проходит.

Что основной вариант не проходит, я и сам убедился.

-- 04 авг 2025 14:55 --

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

Есть дробь:

$$ \dfrac {\varphi (p_i\#)}{p_{i}\#}=\dfrac {(2-1)\cdot (3-1)\cdot (5-1)...(p_i-1)}{2\cdot 3\cdot 5... p_i}\eqno (1) $$

где $\varphi (p_i\#)$ - функция Эйлера для примориала $p_i\#$
В этой дроби можно сокращать числитель и знаменатель на общие множители, а соответственно - на их произведения.
Например, для примориала $p_{10}\#=29\#$ такими общими множителями являются числа: $2,3,5,7,11$
При сокращении числителя и знаменателя дроби (1) на общие множители мы получаем равные участки примориала с равным количеством чисел, взаимно простых этому примориалу.

Кроме того, существует (так называемая мной) "Теорема Руст'а"
, которая утверждает, что числитель и знаменатель дроби (1) можно делить на $2^{i-1}$.

Пусть тогда это сообщение носит информативный характер: как можно разбить примориал на интевалы с равным числом вычетов.
Единственное, что можно разбивать либо сокращением числителя и знаменателя на общие множители, либо по теореме Руста.

[Батороев]

Теперь прошу оценить погрешность такой формулы приближенного расчета количества простых чисел:

$$ \pi (p_{r}\#)\approx \varphi (p_{r}\#)-p_{s}^2\cdot (K_{r}-K_{s})+r-1$$

где $p_{s}$ - максимальное простое, квадрат которого не превышает $p_{r}\#$

$K_{r}=\dfrac {\varphi (p_{r}\#)}{p_{r}\#}$

$K_{s}=\dfrac {\varphi (p_{s}\#)}{p_{s}\#}$

[Dmitriy40]

$r=15$
$p_r=47$
$p_r\#=614889782588491410$
$\varphi(p_r\#)=85287729364992000$
$p_s=784149077$
$K_r=0.13870409263585035952338821817513035126$
$K_s=0.027414833577626177386780214408039998432$
$\varphi(p_s\#)-p_s^2(K_r-K_s)+r-1=16857101907220754.894763240480578469577$
vs
$\pi(p_r\#)=15397728527812858$
Относительная погрешность составила +9.5%.
Разумеется $+r-1$ никакой роли не играют, смело можно исключить.

При этом оценка по банальной формуле $\pi(x)=x/\ln(x)$ даёт погрешность всего лишь -2.5%. И зачем нужна более сложная первая формула мне непонятно.

[Батороев]

Dmitriy40
Очередной раз: спасибо Вам!

Dmitriy40 в сообщении #1696322 писал(а):

И зачем нужна более сложная первая формула мне непонятно.

Какая первая формула? Если Вы имели в виду формулу (1) из сообщения от 30.07.25, то я пытался проверить, на сколько частей можно разбивать упомянутую в ней дробь. Косвенно это касалось рассмотрения HL2, обсуждавшуюся ранее в одной из тем.
По ходу раздумий над разделением дроби мне пришла одна мысль.

Дробь $\dfrac {\varphi(p_{i}\#)}{p_{i}\#}$ является фактически усредненной плотностью взаимно простых в примориале.
Если расписать, к примеру, для примориала от простого $11$, то получим:

$$\dfrac {\varphi(p_{5}\#)}{p_{5}\#} = \dfrac {(2-1)(3-1)(5-1)(7-1)(11-1)}{2\cdot 3\cdot 5\cdot7\cdot 11} =\dfrac {480}{2310}\eqno (1)$$

Если развернуть выражение (1), то получим:

$$\dfrac {\varphi(p_{5}\#)}{p_{5}\#} = 1-\dfrac{1}{2}-\dfrac{\varphi(2)}{3}-\dfrac{\varphi(3)}{5}-\dfrac{\varphi(5)}{7}-\dfrac{\varphi(7)}{11}\eqno (2)$$

В данном случае $p_{s}=p_{15}=47$. Запишем аналогичное выражение для него:

$$\dfrac {\varphi(p_{15}\#)}{p_{15}\#} = 1-\dfrac{1}{2}-\dfrac{\varphi(2)}{3}-\dfrac{\varphi(3)}{5}-\dfrac{\varphi(5)}{7} -\dfrac{\varphi(7)}{11} -\dfrac{\varphi(11)}{13}-... -\dfrac{\varphi(41)}{47} \eqno (3)$$

Из (1) вычтем (2), т.е. получим разность $(K_r-K_s)$:

$$\dfrac {\varphi(p_{5}\#)}{p_{5}\#}-\dfrac {\varphi(p_{15}\#)}{p_{15}\#}= \dfrac{\varphi(11)}{13}+...+\dfrac{\varphi(41)}{47} \eqno (4)$$

При этом мы посчитали плотность взаимно простых чисел к простым от 13 до 47 (исключив общие части выражений (2) и (3)).
Умножив на $47^2$, мы тем самым попытались выяснить, сколько таких имеется в $11\#$... И получили погрешность, которая не снижается, как я думал ранее, а наоборот растет по Вашим расчетам.

Мой расчет:

$$ \pi (2310)\approx 480 - 2209\cdot (0,207792208-0,138704093) +5-1=331,3843536$$

Фактический $\pi(2310) = 343$
p.s. Погрешность получалась ниже, если вместо $K_{s}$ использовал $K_{s-1}$

[Dmitriy40]

Я по прежнему не понимаю смысла выдумывать формулы приближений $\pi(x)$ для столь малых значений $x$, ведь до $29\#$ точное значение $\pi(x<10^{10})$ легко получить напрямую за секунду решетом Эратосфена, даже не привлекая сложную математику. С привлечением последней легко за секунды получить точное значение $\pi(x)$ до $10^{16}$ (или $43\#$). А уж табличные значения есть для всех примориалов вплоть до $67\#$.
Т.е. выдумываемые формулы должны позволять считать $\pi(x)$ дальше $67\#$, лучше сильно дальше, и с точностью лучшей чем используемые сейчас формулы (ну или сильно проще).

[Батороев]

Dmitriy40
Ну, Вы опять требуете от меня каких-то высших достижений. А я копаюсь в низах и ищу какие-то конкретные зависимости.

[Батороев]

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

А я копаюсь в низах и ищу какие-то конкретные зависимости.

"Накопал" еще одну...

Количество простых чисел до $p_{i}^2$:

$$\pi (p_{i}^2)\approx (K_{i}\cdot p_{i}-K_{i+1})\cdot p_{i}$$

где $p_{i}$ - i-тое простое число в ряду простых чисел;

$K_{i}=\dfrac {\varphi (p_{i}\#)}{p_{i}\#}$.

[Dmitriy40]

Перепишу по человечески:

$$\pi(p_i^2) \approx p_i (p_i K_i - K_{i+1}) = p_i \left(p_i-\dfrac{p_{i+1}-1}{p_{i+1}}\right) \prod\limits_{p \in P}^{p_i} \dfrac{p-1}{p}$$

Отсюда сразу видно что для достаточно больших $p_i$ (когда можно пренебречь отличием $\frac{p_i-1}{p_i}$ от $1$) рост будет $O(p_i^2)$, что существенно хуже известного $O(p_i^2/\ln(p_i))$. То есть чем больше $p_i$, тем хуже относительная погрешность.

-- 13.08.2025, 10:36 --

Для первого миллиона простых погрешность формулы не интересна.

-- 13.08.2025, 10:59 --

Впрочем:
Для $\pi((p_{i=10^6}=15485863)^2) \approx 8132899675401.8578063446549819309354981$ погрешность от точного значения $7476015750742$ (полученного за 0.2 секунды!) составила $+8.78655\%$.
Для $\pi((p_{i=10^7}=179424673)^2) \approx 951056620856946.48822229845808046797341$ погрешность от точного значения $870513411570200$ (полученного за 4 секунды) составила $+9.25238\%$.
И с увеличением $p_i$ погрешность продолжит расти.