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

[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 тысяч тактов. Любой перебор длиннее сотни-тысячи итераций на получения одного числа для проверки исключается.
В принципе можно перебирать остатки по нескольким простым и пропускать на проверку лишь те комбинации, что попадают в желаемую группу (и в желаемую часть группы! группы ведь огромные, а работу надо делить на куски). Но чем больше юнитов в проверяемой группе, тем чаще фильтр будет пропускать на проверку и тем меньше можно успеть перебрать простых. Это выходит в любом случае лишняя работа, но если она уложится в единицы процентов общего времени - будет выгодно.
Только это ещё и распараллелить, чтобы разные потоки не считали одно и то же ...
Интересно, буду думать в эту сторону.

[Dmitriy40]

Кажется я придумал как можно перебрать 7.4e14 чисел в порядке загрязнения не храня их и ещё и поделив на куски.
Эти числа получаются из остатков по 14 простым 2-71 кроме 13-31, их можно перенумеровать 1...7.4e14 и легко вычислить и номер числа с его группой по заданным остаткам, и наоборот, остатки по его номеру (а из них уже и его группу). Тогда идея в том чтобы перебирать эти числа в порядке увеличения номера в заданном диапазоне для желаемого куска работы и вычислив группу проверять что она желаемая и только в этом случае запускать внутренний цикл проверки. Для групп с малым количеством юнитов придётся перебирать много номеров для нахождения желаемой группы, но для центральных самых больших групп перебрать придётся буквально всего несколько значений и можно запускать внутренний цикл. Т.е. для самых объёмных групп накладные расходы оказываются небольшими. Ну а крайние самые небольшие группы можно проверить и по другому, тупо найти все числа из 7.4e14 что в них попадают и перебрать их прямо по списку. Ну а для промежуточных групп (слишком больших чтобы хранить список, но недостаточно больших чтобы хватало перебора десятков-сотен вариантов до попадания в желаемую группу) смириться с какой-то потерей скорости, вряд ли таких странных групп будет слишком много, тем более в процентах от общего объёма 7.4e14 юнитов.
Фактически получится перебор 7.4e14 юнитов в порядке загрязнения, прям мечта.

[Yadryara]

Dmitriy40

Ну вот Вы и придумали разбиение. Я и не сомневался. Поясняю для всех. Сейчас мы считаем диапазон $0-67\#$ вот по этому разбиению:

Prime  RazrOst        Product

    2        1              1
    3        2              2
    5        2              4
    7        2              8
   11        2             16
   13        2             32
   17
   19        6            192
   23        6           1152
   29       12          13824

И из этих 13824 юнитов мы уже обсчитали более 10 тысяч. То есть мы уже досчитываем.

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

Время пока есть, до весны точно, может и до лета.

Дело пошло настолько хорошо, что ни о каком лете и весне речь уже давно не идёт. А в последнее время стало понятно, что она уже и не идёт о феврале и даже январе.

В этом году должны закончить. А может даже, страшно сказать, в ноябре. Так что о запуске поиска в диапазоне $0-71\#$ конечно уже не просто пора задуматься, неплохо бы уже иметь код и тестить его.

Разбиение для $0-71\#$

Prime  RazrOst            Product

    2        1                  1
    3        2                  2
    5        2                  4
    7        2                  8
   11        2                 16
   13
  ...
   31
   37       20                320
   41       24               7680
   43       24             184320
   47       28            5160960
   53       34          175472640
   59       40         7018905600
   61       42       294794035200
   67       48     14150113689600
   71       52    735805911859200

Почувствуйте разницу: не 13 тысяч юнитов, а 735 триллионов юнитов!

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

Для групп с малым количеством юнитов придётся перебирать много номеров для нахождения желаемой группы, но для центральных самых больших групп перебрать придётся буквально всего несколько значений

И центральные группы, равно как и самые грязные, нас пока не должны волновать совершенно. Я ведь вот это с запасом писал:

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

надо придумать такое разбиение, чтобы выделить участок в 10-20% от всего диапазона $0-71\#$, на котором было бы как можно меньше чужих чисел.

Расчёты с 5-ками и 7-ками вообще говорят, что в среднем может хватить 4-6% от всего диапазона. Я понимаю, что пока может и рановато экстраполировать на 19-ки, но понять как дело обстоит с 19\19 глядя на 17\17, 17\18, 17\19, 18\18 и 18\19 (дро) получается, пожалуй, ещё хуже.

Так что лучше дальше считать 9-ки и 11-ки, но зато находить полные чистые кортежи, а не приближения к ним.

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

Фактически получится перебор 7.4e14 юнитов в порядке загрязнения, прям мечта.

Да, всё внимание прям на самые чистые группы!

[Yadryara]

Повозился я с Вашим разбиением. Оно гораздо лучше, чем Ваше предыдущее, где в самой чистой группе было 25 чужих чисел.

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

Если придётся считать $0-71\#$, то надо стремиться сделать такое разбиение, чтобы чужих чисел было поменьше. То есть не $21-33$, как сейчас, а скажем $18-30$.

Да, оно очень широкое, шириной не меньше чем 18, то есть $20-37$ чужих чисел уже видел.

Но не это важно, а вот что. Я перелопатил одну стомиллионную от 735 трлн:

G20 G21   G22    G23    G24     G25     G26            Всего

[ 0, 81, 1642, 15702, 87152, 320019, 837065, ...]    8716421

(81 + 1642 + 15702 + 87152 + 320019)               / 8716421 =  4.9 %

(81 + 1642 + 15702 + 87152 + 320019 + 837065)      / 8716421 = 14.5 %

Почти уверен, что заветная 19\19 ждёт нас в группах до 25-й включительно, в тех самых 4.9 %. Эта доля, конечно может измениться, но пока верю, что ниже 4% она не упадёт.

14.5 % — это уже очень большой запас, так что не хотелось бы возиться с 26-й группой.