Симметричные кортежи из последовательных простых чисел

[Dmitriy40]

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

Но мне пока непонятно, почему формулу нельзя применять.

Применить можно, тоьлко вероятность получите совсем другого события.
Потому что она на количество попыток, а не на диапазон, в котором частотность сильно меняется.
Ну или потому что все эти 1.5e19 попыток не равновероятны! С ростом номера попытки (т.е. величины чисел) её вероятность падает. Именно поэтому в HL1 не произведение вероятности на интервал, а интеграл по интервалу.
Или потому что эти попытки не независимы. В отличие от бросания кубика.
И поиск кортежей это вообще не бросание кубика. Бросание кубика это тыкать наугад в случайное число в полном 67# (или в 293e15 разных чисел) и проверять не попали ли в 19-252. Заметьте, здесь нет гарантии что каждый раз будете попадать в разные числа! Тогда да, за вот примерно столько попыток наткнётесь на решение вот с такой вероятностью. Причём тыкать придётся даже если попали с первого же раза, вероятность для тыканья до первого совпадения вроде бы заметно другая (потому что "за M попыток попали хотя бы однажды" и "попали не более чем за M попыток" и "попали ровно на n попытке" - это всё разные события в теорвере!). Заметьте, раз нет гарантии перебора всех чисел, то можете не обнаружить точно имеющееся решение даже когда тыкнули ровно 293e15 (или 67#) раз - именно об этом и говорит вероятность $P=1-1/e^{n/M}$ ($n$ - количество тыканий, $M$ - количество тыканий для мат.ожидания равного $1$). Вот что значит бросание кубика. А не тотальный перебор всех 293e15 вариантов.
Впрочем пусть математики подробнее объяснят в чём разница событий/исходов и их вероятностей, я недостаточно понимаю теорвер.

[Yadryara]

Статистика по 5-кам пока такая.

  Pattern  Diapazon  Naideno    Razb.   Uskor.

   5-36       0-29#    23726      17#    1.398
   5-48       0-29#    13394      17#    1.479
   5-60-1     0-29#     7157      17#    1.564
   5-60-2     0-29#     7450      17#    1.538

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

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

Для $0-67\#$ бросили сильно многогранный кубик 293 квадриллиона раз, посмотрели, выпал он нужной стороной или нет.

Я имел в виду, что кубик свою форму не меняет и пока бросаем 293 квадриллиона раз, вероятность можно принять постоянной.

А формула никак не связывает разные диапазоны. То, что при увеличении диапазона вероятность падает, конечно прекрасно видно, по матожиданию которое увеличилось не в 52 раза (как количество попыток), а только в 21 раз. Я сам Вас недавно поправил, может помните, насчёт какого-то из кортежей 17-240, сказав, что их ожидается меньше, не 30, а 20.

И ключевой вопрос именно в том, можно ли применять аналогию с кубиком.

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

Заметьте, здесь нет гарантии что каждый раз будете попадать в разные числа!

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

Есть тут конечно разница. Мы бросили кубик 293 квадриллиона раз — не выпал он нужной стороной. А мы взяли и ещё одну серию провели из 293е15 бросков. И он выпал!

Но это не наш случай. Надёжно проверили один раз весь диапазон — другой раз проверять не будем.

То есть это именно аналогия, а не точная модель. Сомнительно, что есть лучшая аналогия.

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

Впрочем пусть математики подробнее объяснят в чём разница событий/исходов и их вероятностей, я недостаточно понимаю теорвер.

Что-то я опять подозреваю, что никто не будет помогать, хотя математиков на форуме полным-полно. Ну может начнут вопросы задавать: А вы определили вероятностное пространство? А какое у вас распределение? Докажите сначала то и это...

[Dmitriy40]

Ну и кроме того Вы неправильно подставили числа в формулу, мат.ожидание для 19-252 равно 1 не на 67#, а в 2.6 раза дальше (нашёл по HL1 подбором верхнего предела интегрирования). Так что надо считать так: $P=1-1/e^{\frac{67\#}{2.6\cdot67\#}}=0.32$ (здесь $n=67\#, M=2.6n$). Т.е. тыкнув 67# раз в случайные числа в 67# мы с вероятностью 32% обнаружим не менее одного раза 19-252 (может и разные если их там больше одной).
А вот если тыкать не в случные числа в полном 67#, а только лишь в допустимые 293e15, то оценка сложнее: надо знать сколько допустимых вариантов до мат.ожидания равного 1, т.е. до 2.6*67#, но это точно подсчитать сложно, проще оценить примерно в предположении что допустимые варианты распределены в 71# равномерно, тогда берём 52/2.6 часть от всех вариантов в 71# и это и будет M в формуле, оно получается в 1.9 раза больше 293e15 и соответственно $P=1-1/e^{\frac{293\cdot10^{15}}{1.9\cdot293\cdot10^{15}}}=0.41$. Превышение над 32% можно считать свидетельством некорректности предположения о равномерности, а можно что тыкать только в допустимые варианты выгоднее. А может верно и то и другое, я не уверен.
В принципе 41% скорее всего Ваши же 40% с точностью до погрешности аргументов. Но это по любому вероятность при случайном тыканьи много-много раз. Мы делаем совершенно не так.

-- 11.11.2024, 16:45 --

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

И ключевой вопрос именно в том, можно ли применять аналогию с кубиком.

По моему нельзя: случайные броски совершенно не то же самое что тотальный перебор. Потому и вероятности разные.

-- 11.11.2024, 16:56 --

Yadryara
Если хотите через бросание кубика, то пространство событий надо совершенно другим: кидаем кубик с 293e15 (точнее в 1.9...2.6 раза большим) гранями, проверяем соответствующее число и запоминаем результат проверки, уничтожаем эту грань кубика чтобы она гарантированно больше никогда не выпадала и вероятности всех прочих граней увеличились для сохранения суммы вероятностей всех граней равной 1, кидаем снова. И так 293e15 раз. Смотрим на результаты проверок, была ли найдена хотя бы одна 190-252.
И разумеется тут вероятность уже не будет столь простой формулой. Какой - не знаю, думать надо, возможно что-то про сумму геометрической прогрессии.
Вот такая аналогия будет равна поиску кортежей. Тут правда не учтён порядок проверки, ну так и мы уже проверяем не подряд.
Отличие в удалении выпавших граней, и это принципиально всё меняет.

Другая более простая аналогия - выемка шаров из урны (293e15 раз вынимаем по одному шару из урны с 293e15 (или в 1.9...2.6 раза больше) шарами и в конце проверяем что вынули хотя бы один нужного цвета), это вообще классическая задача теорвера, для неё и точное решение известно. Если шаров больше, то кажется для корректности надо шары больше 67# не учитывать (не уменьшать количество оставшихся попыток) и возвращать обратно в урну (это принципиально).
Если искать до первого правильного шара, а не ровно 293e15 раз, то это другая столь же стандартная задача теорвера.

-- 11.11.2024, 17:18 --

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

Что-то я опять подозреваю, что никто не будет помогать, хотя математиков на форуме полным-полно. Ну может начнут вопросы задавать: А вы определили вероятностное пространство? А какое у вас распределение? Докажите сначала то и это...

Согласен. Но таки попробую, хоть развлечёмся.

[Yadryara]

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

Ну и кроме того Вы неправильно подставили числа в формулу,

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

В принципе 41% скорее всего Ваши же 40% с точностью до погрешности аргументов.

Вот именно, я же не от балды взял и именно матожидание подставил в степень $e$ — вычисления проводил. Попробуйте поточнее посчитать, получите $0.399-0.400$ ?

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

Вот такая аналогия будет равна поиску кортежей.

Тоже сомнительно. Уж не клоните ли Вы к тому, что вероятность успеха будет увеличиваться с каждым неудачным броском?

[Dmitriy40]

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

Уж не клоните ли Вы к тому, что вероятность успеха будет увеличиваться с каждым неудачным броском?

А это не очевидно? Обоснование:
Пусть абсолютно точно есть ровно один кортеж 19-252 (или любой другой, даже не обязательно из простых чисел, вообще какой угодно) до $10^{1000}$. Тогда тыкая в случайное число и если не попали, выкидывая его, будем уменьшать количество оставшихся непроверенными чисел, т.е. увеличивать вероятность тыкнуть в решение (как 1/M, где M - сколько чисел осталось, для последнего вероятность станет равна 1).
Мы же проверив вариант выкидываем его из оставшейся части проверки.

-- 11.11.2024, 18:18 --

Открыл тему «Вероятность про урну с нумерованными шарами». Готов ловить тапки.

-- 11.11.2024, 18:31 --

Вчера, пока по новой обдумывал выбор $a_i$ в связи с Вашими вопросами, наткнулся кажется на ещё резерв ускорения программы. Скорее всего точно получится ускорить на моём сервере, получив коэффициент гипетртерйдинга тоже 100% как у вас обоих вместо имеющегося 50%, т.е. у меня станет работать в 2/1.5=1.3 раза быстрее. Но только у меня и только на сервере.
Но возможно даст десяток-два процентов ускорения на любых компах за счёт лучшего использования аппаратуры ядер процессора.
Правда это много переписывать, фактически надо организовать два независимых потока управления чтобы при этом одинаковые команды разных потоков стояли в коде рядом (практически симулировать программно двухпоточный проц), это и гипертрейдингу поможет (проц не всегда может разглядеть независимые команды далеко друг от друга), и без него чуть даст эффект.
Пока не решаюсь переписывать, сложно.

[Yadryara]

Ну а я пока публикую обещанный рассказ увлекательного путешествия от чистых к грязным.

Для паттерна 5-60-2 вот такое разбиение по $17\#$ :

          G4   G5   G6    G7    G8   G9 G10
[0, 0, 0, 12, 154, 858, 1596, 1372, 546, 70, 0, 0, 0, 0]   4608

Всего найдено в диапазоне $0-29\#$ 7450 кортежей. Значит нужно найти $\frac1{11}$ часть, или примерно 9.1% , то есть 678 кортежей.

В группе с 4-мя чужими всего лишь 12 вариантов, то есть доля от всех 4608 всего лишь 0.26%. 678 кортежей конечно же не найдутся, если ограничиться поиском только в этой группе. Но всё же попробуем, интересно сколько найдётся. Это же самая чистая группа, должно найтись явно побольше чем $0.0026\cdot7450\approx 19$ кортежей.

Прогу показал выше. Ставлю в ней ограничение if(chuzh<=4,. chuzh это чуж(ие числа). Да! 46 кортежей нашлось! В 2.4 раза больше.

Суммарно в 4-й и 5-й группах 166 от 4608, то есть лишь 3.6%. Маловато, чтоб набрать 678 кортежей. Но тоже ведь должно найтись явно больше чем $0.036\cdot7450\approx 268$ кортежей. Ставлю if(chuzh<=5,. Да! Их нашлось 537. Уже не в 2.4 раза больше, а в 2.0 раза.

Суммарно в 4-й, 5-й и 6-й группах $12+154+858=1024$ варианта от 4608, то есть аж 22.2%. Это уже с огромным запасом. Запускаем if(chuzh<=6,, срабатывает останов и высчитывается уже 3-й кэф на пути от самой чистой группы к более грязным:

$2.4 \to 2.0 \to 1.5$

Третий кэф я как раз и показывал выше, только точнее: $1.538$

[Yadryara]

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

Открыл тему «Вероятность про урну с нумерованными шарами» . Готов ловить тапки.

Видел. Изложение довольно сумбурное. Правильно ли я делаю, что помалкиваю в этой новой теме? Я боюсь запутать людей. Скажу здесь.

waxtep, mihaild. Очень рад, что вы откликнулись. Новая тема Дмитрия родилась из попытки придумать аналогию для нашего поиска. Мы ищем отрезок натурального ряда строго определённой длины со строго определёнными свойствами. Это и есть белый шар.

[Dmitriy40]

По программе для поиска в 71#.
В принципе, ничто не мешает подсунуть внутреннему циклу сразу правильное число, из самой чистой группы. Вопрос лишь как их быстро получать, ведь таких чисел будет порядка 1.53e19/21e3=7e14. Хранить их не получится. Вычислять же ... 21e3 чисел внутренним циклом обрабатываются за типа 60-100мкс или 10-15 тысяч в секунду, чтобы вычисление 7e14 чисел не тормозило счёт они должны занимать максимум 1/30 этого времени или 2-3мкс или 7-10 тысяч тактов. Любой перебор длиннее сотни-тысячи итераций на получения одного числа для проверки исключается.
В принципе можно перебирать остатки по нескольким простым и пропускать на проверку лишь те комбинации, что попадают в желаемую группу (и в желаемую часть группы! группы ведь огромные, а работу надо делить на куски). Но чем больше юнитов в проверяемой группе, тем чаще фильтр будет пропускать на проверку и тем меньше можно успеть перебрать простых. Это выходит в любом случае лишняя работа, но если она уложится в единицы процентов общего времени - будет выгодно.
Только это ещё и распараллелить, чтобы разные потоки не считали одно и то же ...
Интересно, буду думать в эту сторону.