Пентадекатлон мечты

[EUgeneUS]

VAL в сообщении #1551929 писал(а):

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

Да, ладно.
Мы досчитаем 38-значные числа (по всем паттернам) через неделю-полторы.
А оценка вероятности найти её там, вроде как получается от $0.7$ до $0.8$. То есть с этим розовым единорогом, как в том анекдоте про динозавров - то ли встретится, то ли нет.
Что касается, сколько разбираться. Я разобрался за один вечер, при этом PARI/GP видел первый раз
Так что, переходите на светлую строну силы

Кстати, как-то можете прокомментировать вот этот вопрос:

EUgeneUS в сообщении #1551831 писал(а):

Становится интересно: а сойдется ли к единице вероятность найти пятнашку когда-нибудь.

[VAL]

EUgeneUS в сообщении #1551932 писал(а):

Кстати, как-то можете прокомментировать вот этот вопрос:
EUgeneUS в сообщении #1551831

писал(а):
Становится интересно: а сойдется ли к единице вероятность найти пятнашку когда-нибудь.

Я уверен, что пятнашка найдется.
А вероятность?..
Как известно, нулевая вероятность какого-либо события не делает его невозможным.
Не исключено, что и здесь такая же картина.

[Dmitriy40]

На самом деле вероятность пятнашки до 1e38 где-то 85% ($1-1/\exp(\frac{10^{38}}{5.13\cdot10^{37}})$). Но это как минимум в предположении что вероятности по каждому месту независимы и одинаковы, что может быть не совсем так, вот например первую треть 5e37 цепочки ALL валились чуть чаще чем каждый 1e35, хотя в среднем должно быть всего 0.76e35, а в интервале 560-590e35 их найдено всего 14, меньше даже 0.5e35, разница частот больше двух раз (даже думаю выборочно перепроверить, вдруг это ошибка).
Или вот например если паттерны побить на 4 одинаковых группы (причём в каком-то случайном порядке, но точно без деления по группам N2/S2/N9/S9 и двум цифрам далее), то за 10e35 в них найдено цепочек ALL: 6,2,0,1 (аж втрое чаще!). А с начала 5e37 по тем же группам: 15,10,8,2, ещё неравномернее. При делении на 5 групп неравномерность тоже просматривается.
Плюс оценки $P_2$ заметно расходятся по $P_{11}$ и по $P_{12},P_{13},P_{14}$:
$P_2(P_{11})\approx0.2247$
$P_2(P_{12})\approx \{0.1506;0.3713\}$
$P_2(P_{13})\approx \{0.2651;0.7349\}$
$P_2(P_{14})\approx \{0.2397;0.9892\}$
Привожу по два значения так как уравнение 4-й степени от $P_2$ имеет до 4-х корней, но остальные или равны им, или <0, или >1. Разумеется руками его не решал, напряг wolframalpha (пример для $P_{13}$, остальные формулы выводил парой страниц выше).
Это по всему интервалу 0-5e37, а вот по интервалу 2-3e37 было забавно, мало того что $N_{12}$ постоянно куда-то сильно убегает, так в этом интервале решений уравнения вообще нет, максимум функции от $P_2$ (который точно в $P_2=0.25$) не дотягивается до количества реально найденных на 1.3 штуки! Вроде мало, но почти во всех остальных случаях реально найденные количества вовсе не в максимуме (скажем максимум для $P_{13}$ всегда в $P_2=0.5$, а для $P_{14}$ максимум всегда в $P_2=0.75$).

Т.е. неравномерности явно присутствуют, значит могут быть и например в распределении по местам. Так что 85% это оптимистичная оценка, для более реальной интервал лучше бы удвоить ...

[Yadryara]

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

Но это как минимум в предположении что вероятности по каждому месту независимы и одинаковы, что может быть не совсем так,

?? Это совсем не так. И было неоднократно показано выше :

Yadryara в сообщении #1551801 писал(а):

А при подъёме ровно на 1 порядок(с 4е37 до 4е38) средняя частотность искомой 15-шки упала менее чем в полтора раза.

Yadryara в сообщении #1551731 писал(а):

при подъёме на 8 порядков вероятность искомой 15-шки упала раз в 20.

$$1,454^8\approx20$$

Причём это падение, примерно в полтора раза на порядок было предварительно оценено давно, ещё на примере 15 одиночных простых:

Yadryara в сообщении #1551325 писал(а):

вероятность падает примерно в полтора раза с каждым подъёмом на порядок. Начиная от 1e37:

$(\frac{125663}{122129})^{15}\approx 1.534$

$(\frac{122129}{118788})^{15}\approx 1.516$

$(\frac{118788}{115625})^{15}\approx 1.499$

$(\frac{115625}{112626})^{15}\approx 1.483$

$(\frac{112626}{109778})^{15}\approx 1.468$

Для других вариантов посчитать сложнее.

А сейчас как раз более сложный вариант посчитан. Можно ещё посчитать на самых низинах. Хотя прмерно понятно как себя будет вести этот кэф для 15-шки:

$1,48\to1,42$

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

Какие вероятности(средние частотности) брать для проверяемого сейчас диапазона, я показал чуть выше:

Yadryara в сообщении #1551801 писал(а):

1 к 43-м $\to$ 1 к 63-м ярдам.

[EUgeneUS]

Поясню свой вопрос на примерах.

1. Пусть мы ищем среди натуральных чисел суслика. И нам удалось поделить натуральные числа на кучки конечного размера так, что вероятность найти суслика в каждой кучке $p_1=1/2$.

Тогда вероятность найти хотя бы одного суслика: $p_N = 1-(1/2)^N$, где $N$ - количество проверенных кучек. С ростом $N$ эта вероятность быстро сходится к $1$. Суслик найдется.

2. Пусть мы ищем среди натуральных чисел дронта. И нам удалось поделить натуральные числа на кучки конечного размера так, что вероятность найти дронта в каждой кучке $p_n=1/(n+1)$. Где $n$ - номер кучки

Тогда вероятность найти хотя бы одного дронта, проверяя кучки в порядке номеров: $p_N = 1-1/N$, где $N$ - количество проверенных кучек. С ростом $N$ эта вероятность растет уже не быстро, но таки сходится к $1$. Дронт найдется, но не так быстро как суслик.

3. Пусть мы ищем среди натуральных чисел единорога. И нам удалось поделить натуральные числа на кучки конечного размера так, что вероятность найти единорога в каждой кучке $p_n=1/(n+1)^2$. Где $n$ - номер кучки

Тогда вероятность найти хотя бы одного единорога среди всех натуральных чисел всего лишь $1/2$. То ли найдется, то ли нет.

Вот и возникает вопрос - как быстро падает вероятность найти 15-ку?

[Yadryara]

EUgeneUS в сообщении #1551967 писал(а):

Вот и возникает вопрос - как быстро падает вероятность найти 15-ку?

Ну так примерный ответ я только что ещё раз дал в посте выше:

Примерно в $1.46$ раза на порядок.

То есть при увеличении первого проверяемого числа $n$ в $10$ раз вероятность найти 15-ку уменьшается в $1.46$ раза. А при увеличении первого проверяемого числа $n$ в $100\,000\,000$ раз вероятность найти 15-ку уменьшается в $20$ раз.

Сам этот кэф $1.46$ при увеличении первого проверяемого числа $n$(при подъёме в гору) плавно снижается. Чуть более плавно чем обратный логарифм.

Для A226945 кэф должен снижаться как обратный логарифм.

А для количества Squarefree semiprimes A036351 кэф снижается более плавно чем обратный логарифм.

И наша 15-шка(в рамках КМК37-11) это симбиоз из 11 чисел количество которых указано в A226945 и 4-х чисел количество которых указано в A036351.

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

[Dmitriy40]

Yadryara в сообщении #1551966 писал(а):

?? Это совсем не так. И было неоднократно показано выше :

Простите, я говорил о вероятности между разными местами в одном и том же диапазоне и интервале. То что они падают с ростом чисел довольно очевидно и Вы прекрасно показали как именно падают.

Yadryara в сообщении #1551966 писал(а):

Какие вероятности(средние частотности) брать для проверяемого сейчас диапазона, я показал чуть выше:

Опять же простите, но я предпочту брать вероятности (частотности) из реальной насчитанной статистики: $P_1\approx0.1844, P_2\approx0.2246, P_{15}\approx0.2133\cdot10^{-10}$ (от попыток) на интервале 0-5e37.

EUgeneUS в сообщении #1551967 писал(а):

Вот и возникает вопрос - как быстро падает вероятность найти 15-ку?

Попробую прикинуть.
Если $P_{15}$ падает в $1.46$ раза на порядок, то на октаву (вдвое) она падает в $1.46^{2/10}\approx1.08$ раза. Т.е. примем что для 0-1e38 она станет $P_{15}\approx1.4\cdot10^{-11}$ (от попыток). Тогда вероятность её нахождения в 0-1e38: $P(15)\approx1-1/\exp(1.4\cdot10^{-11}\times91\cdot10^9)\approx0.72$. Для 0-1e39 вероятность понизится до $P_{15}\approx0.96\cdot10^{-11}$, а вероятность нахождения: $P(15)\approx1-1/\exp(0.96\cdot10^{-11}\times910\cdot10^9)\approx0.9998$. А уже для 0-1e40 вероятность нахождения пятнашки увеличится до: $P(15)\approx1-1/\exp(1.4\cdot10^{-11}/1.46^2\times91\cdot10^9\times10^{40}/10^{38})\approx1-1.1\cdot10^{-26}$.
Собственно сходимость очевидна из соотношения под экспонентой: увеличение на порядок уменьшает выражение в $1.46$ раза из-за падения вероятности и увеличивает в $10$ раз из-за увеличения интервала, т.е. аргумент экспоненты растёт со скоростью в $6.85$ раза на каждый порядок, или вероятность ненахождения пятнашки падает в $943$ раза на каждый порядок.

[EUgeneUS]

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

вероятность ненахождения пятнашки падает в $943$ раза на каждый порядок.

А значит получим три девятки ($ > 0.999$), обсчитав полностью 0е39 (39-значные числа). Вот и хорошо.

[Yadryara]

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

Т.е. примем что в 1e38 она станет $P_{15}\approx1.4\cdot10^{-11}$ (от попыток).

А откуда взялось это число?

Это слишком мало: всего 1 раз на 71 ярд. А по моим вычислениям(основанных на данных именно в этом месте) только в 4e38 она станет 1 раз на 63 ярда.

А в 1e38 она станет никак не ниже чем 1 раз на 47 ярдов, то есть никак не ниже чем $2.1\cdot10^{-11}$

[Dmitriy40]

Yadryara в сообщении #1551982 писал(а):

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

Т.е. примем что в 1e38 она станет $P_{15}\approx1.4\cdot10^{-11}$ (от попыток).

А откуда взялось это число?

"в 1e38" не совсем правильно, я там поправил, должно быть "в 0-1e38".
Соответственно Вы правы, я снова не совсем то посчитал, спутал функцию и интеграл от неё.
Но тогда выходит все формулы выше используют и дают лишь "мгновенные" вероятности, в точке, а для получения полной вероятности в диапазоне (особенно большом или от нуля) надо брать честный интеграл ...

[Yadryara]

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

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

увеличение на порядок уменьшает выражение в $1.46$ раза из-за падения вероятности и увеличивает в $10$ раз из-за увеличения интервала, т.е. аргумент экспоненты растёт со скоростью в $6.85$ раза на каждый порядок, или вероятность ненахождения пятнашки падает в $943$ раза на каждый порядок.

Увеличение интервала всё-таки в $9$ раз.

[Dmitriy40]

Оценки выше забываем, они походу неверные. Попытаюсь оценить честно.

Уменьшению вероятности в $1.46$ раз на порядок отвечает функция $1.46^{-\lg{x}}C$, её интеграл от $1$ до $x$ равен $\int\limits_1^x 1.46^{-\lg{x}}C dx= 1.1967(x^{1/1.1967}-1)C$, а "средняя" вероятность на всём интервале $(1;x)$ будет в $x$ раз меньше $1.1967(x^{1/1.1967}-1)C/x=1.1967(x^{1/1.1967-1}-1/x)C$, где $C$ — вероятность в точке $x=1$.

Тогда для интервала 1-5e37 $x=5$ и коэффициент вероятности на этом интервале $1.1967(5^{1/1.1967-1}-1/5)\approx0.6792$ от вероятности в точке 1e37. На этом интервале было найдено 294 цепочки ALL, из которых 107 с valids=11, т.е. оценка вероятности пятнашки на интервале 1-5e37 составила $\frac{294}{4\times9.1\cdot10^9}(1-\sqrt[4]{107/294})^4\approx 2.008\cdot10^{-11}$, а значит "истинная" вероятность $P_{15}$ в точке 1e37 была $2.008\cdot10^{-11}/0.6792\approx2.956\cdot10^{-11}$ или 1 на 34млрд попыток. В точке 1e38 она должна составить в $1.46$ раз меньше или $2.025\cdot10^{-11}$ или 1 на 49млрд попыток. А в точке 1e45 в $1.46^7$ раз меньше или $1.432\cdot10^{-12}$ или 1 на 700млрд попыток, что не совпадает с тестовым замером:

Yadryara в сообщении #1551731 писал(а):

И для 46-значных составляет примерно 1 раз на 848 миллиардов попыток.

Или может здесь брались числа не около 1e45, а около 5e45?
Пересчитаю обратно, из 1e45 в 1e37, $1/848\cdot10^9\times1.46^7\approx1.67\cdot10^{-11}$, грубо в $2.008/1.67\approx1.2$ раза меньше, т.е. цепочек тоже должно было найтись в $1.2$ раза меньше, погрешность выходит 20%, немало, не думаю что её можно всю списать на неточности оценок и округления.

Предположим ошибка не в оценках или формулах, а просто аномалия в самом числовом ряде, тогда с 1e37 до 1e38 $x=10$ и "средняя" вероятность пятнашки $1.1967(10^{1/1.1967-1}-1/10)\approx0.7$ от вероятности в 1e37 или $2.069\cdot10^{-11}$ (от попыток). И за $9\times9.1\cdot10^9$ попыток в этом интервале должно бы найтись $1.7$ пятнашки.
А с 1e37 до 1e39 $x=100$, "средняя" вероятность пятнашки $1.1967(100^{1/1.1967-1}-1/100)\approx0.55$ от вероятности в 1e37 или $1.624\cdot10^{-11}$ от попыток. За $99\times9.1\cdot10^9$ попыток должно бы найтись $14.6$ пятнашки.
Если я правильно понимаю формулу $1-1/\exp(x)$, то вероятность не найти пятнашку до 1e38 составит $\exp(-1.7)\approx0.18$, до 2e38 примерно $\exp(-3.3)\approx0.037$, а до 1e39 жалкие $\exp(-14.6)\approx4.6\cdot10^{-7}$. И даже если уменьшить количества в 1.2 раза, то до 1e38 вероятность не найти $\exp(-1.7/1.2)\approx0.24$, до 2e38 $\exp(-1.7\cdot2/1.2)\approx0.06$, до 1e39 жалкие $\exp(-14.6/1.2)\approx5.2\cdot10^{-6}$.

[Yadryara]

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

Yadryara в сообщении #1551731 писал(а):

И для 46-значных составляет примерно 1 раз на 848 миллиардов попыток.

Или может здесь брались числа не около 1e45, а около 5e45?

4e45 - ровно в $10^8$ раз больше, чем предыдущий обсчёт 4e37. А затем ровно в 10 раз больше:

Yadryara в сообщении #1551801 писал(а):

А при подъёме ровно на 1 порядок(с 4е37 до 4е38)

[Dmitriy40]

Yadryara в сообщении #1552015 писал(а):

4e45 - ровно в $10^8$ раз больше, чем предыдущий обсчёт 4e37.

Спасибо, да, это указание на точную величину я пропустил, увидел только формулы и оценку.
Тогда в 4e45 у меня получается $P_{15}\approx1.432\cdot10^{-12}/1.46^{4/10}\approx1.231\cdot10^{-12}$ или 1 к 812млрд, отличие от 848млрд чуть больше 4%, столько я уже готов списать на статистические аномалии.

[Yadryara]

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

столько я уже готов списать на статистические аномалии.

Тем более что я обсчитывал 2880 паттернов, а не полный набор. Статистическая неодинаковость отдельных групп была заметна.
По-хорошему то надо все считать. И я хотел загрузить все паттерны, но у меня не получилось быстро их загрузить и сразу распаковать в нужную папку.