кортежи последовательных простых. ключ к 19-252

[Yadryara]

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

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

Банально, но факт

Конечно я больше цифр считал, но не все показал. Если угодно: 6.9790% и 6.9748%.

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

3500 кортежей в секунду, а в ней сколько, а?

Смотря для какого периода. Понятно, что квадриллионы быстро не осилить.

[Dmitriy40]

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

Смотря для какого периода. Понятно, что квадриллионы быстро не осилить.

Пустая ячейка у Вас на 71#, а посчитать реально лишь:

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

Для всех групп реально только для 37# (полчаса) и 41# (часов 13), ждать две недели для 43# уже влом.
Могу предложить анализировать лишь скажем по миллиону кортежей в каждой группе, уж наверняка статистика будет достаточно точной, но тут не вполне уверен что выборка в каждой группе получится достаточно случайной. Да плюс ещё и подсчитать сами начальные числа кортежей в средних группах от 53# и выше весьма проблематично (не общее, его знаем, а именно вот этот миллион чисел, равномерно распределённых по всем).

Ну и о чём разговор тогда ...

-- 15.08.2024, 20:46 --

Кстати до $2^{64}$ скорость раз в 8 выше:

? predel=vecprod(primes([2,41]));
? vc=vector(49);for(i=1,1e5,x=random(predel);vc[#primes([x,x+252])+1]++);
time = 3,432 ms.

Почти 30000 в секунду.

[Yadryara]

Ну как о чём разговор.

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

2. Если точность будет выше, можно будет точнее оценить момент, когда матожидание для того или иного периода преодолеет $\frac1{11}$ от полного значения.

3. Если и это будет посчитано, то экстраполируя на период 71#, получим более точную оценку, когда матожидание для этого периода преодолеет 1-цу.

Тогда возникает логичный вопрос. А зачем вообще тебе считать по Y2, посчитай по HL-1.

Не знаю как считать по HL-1 для различных порядков проверки. А по Y2 — знаю.

[Dmitriy40]

Напомню, как поменять порядок проверки я без понятия, максимум могу перебирать скажем 31# (332тыс) в порядке возрастания загрязнённости, остальные же будет перебирать моя программа (надеюсь её получится так настроить). Так порядок проверки будет совсем не строго по группам, ведь в 31# группы 19+17 и 19+18 проверить относительно быстро, но хотя бы будут проверяться группы не правее текущей в 31#. И так не получится исключить уже проверенный кусок (почти 4% от 67#), на что можно и наплевать.
Только я пока не понял определились ли Вы с лучшим порядком проверки? Надеюсь слева направо (от чистых к грязным)?

Хорошо, давайте думать как получить миллион кортежей из каждой группы не вычисляя остальные квадриллионы.
У меня идея лишь та же: выбирать случайный кортеж из каждой группы в 53# и просчитывать всех его наследников (по 59...71), их будет 52*48*42*40=4.2млн, но они будут в разных группах, так что есть надежда что в каждую попадёт хоть по сотне тысяч. Повторить это несколько раз для разных случайных начальных кортежей из 53# и сравнить что получается, если разброс окажется небольшим, то считать что оно близко к правде. Как Вам идея?

-- 15.08.2024, 22:39 --

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

Если и это будет посчитано, то экстраполируя на период 71#, получим более точную оценку, когда матожидание для этого периода преодолеет 1-цу.

Честно говоря не вижу в этом практического смысла - проще брать и считать, до упора, когда-нибудь найдётся. Или примерно к 1/11 полного периода, или раньше. Всё равно матожидание не догма, отклонения могут быть огромными. А 1/11 от 71# тоже в общем устраивает (года на 3-4, если не придумаю как ещё ускорить).

[Dmitriy40]

C12=6675438285921408545085248.2803143746741
3053880326 паттернов.
Посчиталось за 22ч38м.

[Yadryara]

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

Только я пока не понял определились ли Вы с лучшим порядком проверки? Надеюсь слева направо (от чистых к грязным)?

Именно так. Причём не просто определился. Из примитивной программы счёта по Y2 прямо следует, что вероятность успеха падает при переходе вправо к соседней более грязной группе в $1-p$ раз:

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

более тщательный анализ показывает, что первоначальное предположение справедливо и вероятность найти 19+0 для 19+5 выше чем вероятность для 19+30 аж в 38 раз:

19+ 5 1.658853263169199247842288359 E-17
19+30 4.291919161372029244999614640 E-19

Разделите первое на второе. Что получите ? $38.6506$. И то же самое получается 25-кратным умножением за 25 шагов вправо:

$$\frac1{(1-0.136)^{25}}\approx38.6506$$

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

Как Вам идея?

Нравится. Мы по числам увидим, хорош ли этот метод.

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

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

Конечно проще. Только в среднем дольше.

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

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

когда-нибудь найдётся. Или примерно к 1/11 полного периода, или раньше. Всё равно матожидание не догма, отклонения могут быть огромными.

Вот именно. Тогда почему же Вы два исхода указали? Лучше было тогда уж сказать о всех трёх:

Или примерно к 1/11 полного периода, или раньше, или позже.

Да хоть сегодня может найтись.

Да, отклонения могут быть огромными. Сам писал недавно, что при матожидании 8.7 количество кортежей могло быть от 0 до 20 и даже больше. Интуитивно чувствовал, что 20 это уже больше 3-х сигм и Вы это позже подтвердили:

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

$8.7 \pm 2.9 n $

$n$ - количество сигм.

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

А 1/11 от 71# тоже в общем устраивает

А $\frac1{20}$ не устраивает? Это предварительно.

-- 16.08.2024, 04:03 --

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

Посчиталось за 22ч38м.

Здорово. Эдак C13 посчитается чуть ли не быстрее чем C12.

[Dmitriy40]

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

А $\frac1{20}$ не устраивает? Это предварительно.

Неа: вероятность этого заметно меньше 1%. Если распределение и правда нормальное, то с вероятностью 68% значение попадёт в интервал $[11-3.3\cdot1\ldots11+3.3\cdot1]$, с вероятностью 95% в интервал $[11-3.3\cdot2\ldots11+3.3\cdot2]$ и с вероятностью 99.73% в интервал $[11-3.3\cdot3\ldots11+3.3\cdot3]$, т.е. за его границы вылезет с вероятностью 0.27$ (а именно вверх с половинной вероятностью, 0.13%).

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

Именно так. Причём не просто определился. Из примитивной программы счёта по Y2 прямо следует, что вероятность успеха падает при переходе вправо к соседней более грязной группе в $1-p$ раз:

Отлично, что ж, буду думать как перенастроить порядок перебора, благо для этого асм править не надо, только обвязку на PARI.
Теперь стоит пересчитать мою оценку выше что в 71# искать в 2.4 раза дольше, она была прикинута если в 67# считать всё до упора и в 71# тоже в произвольном порядке, а если считать 71# в порядке загрязнения, то может с хорошей вероятностью (1 или 2 сигмы) даже по нижней границе найдётся быстрее чем в 2.4 раза и тогда нет смысла считать 67#?

[vicvolf]

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

Если распределение и правда нормальное

Нормальное распределение является только предельным. Практически это означает, что распределение становится близким к нормальному, когда на интервале большое количество кортежей. При единичных кортежах, как я уже писал надо использовать неравенство Чебышева https://ru.wikipedia.org/wiki/%D0%9D%D0 ... 0%B2%D0%B0
Так как неравенство Чебышева рассчитано на любое распределение, то вероятности немного хуже: случайная величина укладывается в 2 стандартных отклонения с вероятностью 75 % и в 3 стандартных отклонения с вероятностью 88.88 % и.т.д.

[Yadryara]

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

Неа: вероятность этого заметно меньше 1%.

Чего этого? Вы не поняли о чём я говорил? $\frac1{20}$ это 5 %. А про 5% я говорил раньше:

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

В среднем, если проверять кортежи безыдейно, то для нахождения $\frac1{11}$ всех кортежей нужно проверить ту же долю, то есть 9.1% кандидатов. Если проверять от чистых к грязным, то 5.2%.

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

Понятно, как я посчитал эти 5.2% ? То есть вижу уменьшение среднего обсчёта по меньшей мере в 1.75 раза.

По меньшей мере — потому что для 71# жду улучшения примерно до 5%.

Проверяем 71# произвольно — в среднем находим кортеж за $\frac1{11}$ полной проверки.
Проверяем 71# от чистых к грязным — в среднем находим кортеж за $\frac1{20}$ полной проверки.

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

нет смысла считать 67#?

Там же:

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

293.4 квадра на 0.51 кортежа это примерно 575 квадров на кортеж.

При счёте по 71# , видимо, всё-таки поменьше чем 800:

$293.4\cdot52\cdot0.05\approx 763$ квадра на кортеж.

То есть даже произвольный счёт по 67# выигрывает у продвинутого счёта по 71#.

Пока так. Точнее мы ещё не посчитали.

[vicvolf]

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

Да, отклонения могут быть огромными. Сам писал недавно, что при матожидании 8.7 количество кортежей могло быть от 0 до 20 и даже больше. Интуитивно чувствовал, что 20 это уже больше 3-х сигм и Вы это позже подтвердили:

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

$8.7 \pm 2.9 n $
$n$ - количество сигм.

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

[Yadryara]

vicvolf, на сколько моих вопросов Вы не ответили? В том числе более ранних?

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

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

Лично мне психологически комфортно, когда что-то посчитано поточнее. В том числе для сравнения с Y2.