2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 40, 41, 42, 43, 44, 45, 46  След.
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 15:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 16:37 
Аватара пользователя


29/04/13
8108
Богородский
Статистика по 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 писал(а):
Впрочем пусть математики подробнее объяснят в чём разница событий/исходов и их вероятностей, я недостаточно понимаю теорвер.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 16:39 
Заслуженный участник


20/08/14
11760
Россия, Москва
Ну и кроме того Вы неправильно подставили числа в формулу, мат.ожидание для 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 писал(а):
Что-то я опять подозреваю, что никто не будет помогать, хотя математиков на форуме полным-полно. Ну может начнут вопросы задавать: А вы определили вероятностное пространство? А какое у вас распределение? Докажите сначала то и это...
Согласен. Но таки попробую, хоть развлечёмся. ;-)

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 17:26 
Аватара пользователя


29/04/13
8108
Богородский
Dmitriy40 в сообщении #1661191 писал(а):
Ну и кроме того Вы неправильно подставили числа в формулу,

Dmitriy40 в сообщении #1661191 писал(а):
В принципе 41% скорее всего Ваши же 40% с точностью до погрешности аргументов.

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

Dmitriy40 в сообщении #1661191 писал(а):
Вот такая аналогия будет равна поиску кортежей.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 18:12 
Заслуженный участник


20/08/14
11760
Россия, Москва
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 раза быстрее. Но только у меня и только на сервере.
Но возможно даст десяток-два процентов ускорения на любых компах за счёт лучшего использования аппаратуры ядер процессора.
Правда это много переписывать, фактически надо организовать два независимых потока управления чтобы при этом одинаковые команды разных потоков стояли в коде рядом (практически симулировать программно двухпоточный проц), это и гипертрейдингу поможет (проц не всегда может разглядеть независимые команды далеко друг от друга), и без него чуть даст эффект.
Пока не решаюсь переписывать, сложно.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение11.11.2024, 18:46 
Аватара пользователя


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

Для паттерна 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$

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение12.11.2024, 02:03 
Аватара пользователя


29/04/13
8108
Богородский
Dmitriy40 в сообщении #1661196 писал(а):
Открыл тему «Вероятность про урну с нумерованными шарами» . Готов ловить тапки.

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

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение12.11.2024, 18:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение13.11.2024, 04:09 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение13.11.2024, 07:12 
Аватара пользователя


29/04/13
8108
Богородский
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 юнитов в порядке загрязнения, прям мечта.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение13.11.2024, 11:22 
Аватара пользователя


29/04/13
8108
Богородский
Повозился я с Вашим разбиением. Оно гораздо лучше, чем Ваше предыдущее, где в самой чистой группе было 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-й группой.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение13.11.2024, 14:16 
Заслуженный участник


20/08/14
11760
Россия, Москва
Yadryara в сообщении #1661353 писал(а):
Повозился я с Вашим разбиением. Оно гораздо лучше, чем Ваше предыдущее, где в самой чистой группе было 25 чужих чисел.
Не совсем понял про какое Вы разбиение, ведь 7.36e14 юнитов попадают в группы с номерами меньше 21. Уже группы 59# (без простых 13...31) дают в 21 группе 168 юнитов:
59#/13...31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 168, 7816, 157684, 1846066, 14091382, 73761148, 271302678, 704642160, 1296115776, 1691206270, 1538392132, 942344902, 375167100, 94320486, 14347332, 1166212, 36288], sum=7018905600
Следующие три считать на PARI слишком долго (это считалось 40мин).
Один такой юнит будет считаться 3мкс*42*48*52=0.3с (у вас вдвое дольше).
Но чтобы выделить скажем 8000 юнитов групп 21-22 (или любых других в любом порядке) минут на 40 счёта из общего количества 7e9 надо перебрать в среднем 7e9/8e3=0.9e6 юнитов, каждая итерация перебора займёт тактов 5 или 1.5нс, на 0.9млн это 1.4мс или 1/200 от времени счёта юнита или 0.5% накладных расходов, вполне приемлемо. Но здесь каждый юнит содержит в себе до 6 групп 71#/13...31, ведь он перебирает ещё три простых 61...71, каждое из которых может вычеркнуть до двух чисел из оставшихся, т.е. уменьшить номер группы на 2 каждое или на максимум 6 все.

А вот на 71#/13...31 с 7.4e14 юнитами с временем счёта каждого 3мкс накладные расходы растут слишком сильно: запуская программу на полчаса для обработки 600млн юнитов нам нужно из общего объёма 7.4e14 выделить 6e8 чисел или в среднем перебрать 7.4e14/6e8=1.2e6 вариантов, по 1.5нс это 2мс, в 700 дольше счёта самого юнита! Т.е. накладные расходы составили 70000%! Однозначно отказать.

На 67#/13...31 с 1.4e13 юнитами с временем счёта каждого 3мкс*52=150мкс для выделения юнитов на те же полчаса (12млн шт) надо перебрать 1.4e14/12e6=1.2e6, те же 2мс или 1200%. Всё ещё неприемлемо.

На 61#/13...31 с 3e12 юнитами с временем счёта каждого 7.5мс для выделения юнитов на полчаса (240тыс шт) надо перебрать снова 3e11/240e3=1.25e6, те же 2мс, но уже лишь 27% накладных расходов. Всё ещё многовато.

Впрочем я походу посчитал расходы лишь на одно простое, а их же 10-14, значит накладные расходы будут ещё в 10-14 раз выше. Ну или в 3-4 если тройки простых объединить в общие таблицы.
Получается последнее условно выгодное разбиение это как раз 59#, с 6-ю группами 71#/13...31 в каждом юните, это плата за скорость и за перебор от чистых.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение13.11.2024, 14:29 
Аватара пользователя


29/04/13
8108
Богородский
Dmitriy40 в сообщении #1661367 писал(а):
Не совсем понял про какое Вы разбиение, ведь 7.36e14 юнитов попадают в группы

Я тогда просто программу приведу:

(PARI)

Код:
{print();

t0=getwalltime();

v=[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252];

d=v[#v];

a=setminus(vector(d/2,i,i*2),v);

vdel   = [3,5,7,11,37,41,43,47,53,59,61,67,71];pro=1; w=2*vecprod(vdel);

kgr=vector(40);schuzh=0;kkor=0;

m=vector(71,i,[]);

for(j=1, #vdel, p=vdel[j];

m[p]=setminus(vector(p,i,i-1),Set(-v%p));pro*=#m[p];

printf("%d:x%d:   %d\n",p,#m[p],pro););

x0=Mod(1,2);

foreach(m[71],m71,
foreach(m[67],m67,
foreach(m[61],m61,
foreach(m[59],m59,
foreach(m[53],m53,
foreach(m[47],m47,
foreach(m[43],m43,
foreach(m[41],m41,
foreach(m[37],m37,
foreach(m[11],m11,
foreach(m[7],m7,
foreach(m[5],m5,
foreach(m[3],m3,

y=chinese([x0,
Mod(m3,3),Mod(m5,5),Mod(m7,7),Mod(m11,11),Mod(m37,37),Mod(m41,41),Mod(m43,43),
Mod(m47,47),Mod(m53,53),Mod(m59,59),Mod(m61,61),Mod(m67,67),Mod(m71,71)
]);

x=lift(y);

kvar++;

chuzh=0;

for(i=1, #a,

for(j=1, #vdel, p=vdel[j];

if((x+a[i])%p==0, next(2)));

chuzh++);
kgr[chuzh]++;

if(chuzh<=22,

do25=round(vecsum(kgr[20..25])/kvar*1000);
do26=round(vecsum(kgr[20..26])/kvar*1000);

print();print(kvar,"   ",kgr[20..26],"   ",do25,"   ",do26));

)))))))))))));

print();
print(kvar);

print();
print(strtime(getwalltime()-t0));
print();

}
quit;

Есть и ещё, скажем так, полное разбиение, которое Вы весной считали:

Код:
0 - 67#

  G4    G5      G6        G7         G8           G9           G10            G11
   0 54760 6792018 325858198 8732689082 153606059908 1913747177340 17483063702860

0 - 71#

    G4       G5        G6
240396 38034460 317757600

А для $0 - 71\#$ уже летом считали: G5 и G6 под сомнением.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение14.11.2024, 00:48 
Заслуженный участник


20/08/14
11760
Россия, Москва
Беспокоит меня что накладные расходы приемлемы только максимум для 59#, но при этом минимальная группа G21, хотя для полного разбиения 71# группы начинаются от G4.
И главное, непонятно ради чего переписывать программу, ведь сейчас без всякой переделки могу сделать разбиение:
47#/13...31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 94, 2032, 17820, 102014, 370054, 842874, 1273324, 1330372, 838402, 308130, 67646, 7862, 336], sum=5160960
Да, тут группы лишь с G25, но ведь при переборе в программе простых 53...71 и 13...31 группы часто сильно уменьшаются (до G4@71# в общем-то, причём видимо G4@71# может получаться из групп вплоть до G42, т.е. фактически из всех вот этих). Т.е. хоть с этим разбиением, хоть с 59#/13...31, по любому без перебора всех групп самая чистая группа G4@71# может не провериться полностью. То, ради чего боролись, остаётся недореализованным.
Да, конечно 240e3 юнитов G4@71# (да и G5 и G6) можно проверить прямо, за 20мкс (G5 за 3мс и G6 за 30мс), вычислять их юниты на много порядков дольше, речь не об этом, а что не понимаю есть ли такая уж необходимость уширять разбиение с 47#/ до 59#/, насколько при этом разница в проценте покрытия самых чистых групп из 71# (объёмы которых мы ещё и не знаем, мрак). Относительно G4 группы что G21 что G25 выглядят одинаково далеко. А программу переписывать без существенной причины как-то не хочется. Тесты писать, что ли ...

-- 14.11.2024, 01:19 --

Хотя Вы же вот уже говорите:
Yadryara в сообщении #1661353 писал(а):
Оно гораздо лучше, чем Ваше предыдущее, где в самой чистой группе было 25 чужих чисел.
Только тут речь про разбиение 71#/13...31 с 7.4e14 юнитами. Как именно выделили 1/1e8 вопрос хитрый, но пусть более-менее равновероятно.
Но тогда понятно что оно лучше чем разбиение 29#/17. Хотя, там же группы были от G21 ... Про какое тогда моё предыдущее разбиение с G25 что оно хуже?
И я пока откровенно не знаю как считать разбиение 71# с 1.5e19 юнитов (ну пусть за исключением 2-4 самых чистых групп, ну и самых грязных если будет нужно), и даже 71#/13...31 с 7.4e14 юнитами, реально только 59#/13...31 (на следующих резко падает скорость, писал выше).

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение14.11.2024, 06:07 
Аватара пользователя


29/04/13
8108
Богородский
Dmitriy40 в сообщении #1661394 писал(а):
Про какое тогда моё предыдущее разбиение с G25 что оно хуже?

Вот про это:

Dmitriy40 в сообщении #1661394 писал(а):
47#/13...31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 94, 2032, 17820, 102014, 370054, 842874, 1273324, 1330372, 838402, 308130, 67646, 7862, 336], sum=5160960
Да, тут группы лишь с G25,

Ну или можно просто вот эту схему обрезать по 47#:

Yadryara в сообщении #1661349 писал(а):
Разбиение для $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



Dmitriy40 в сообщении #1661394 писал(а):
Только тут речь про разбиение 71#/13...31 с 7.4e14 юнитами. Как именно выделили 1/1e8 вопрос хитрый, но пусть более-менее равновероятно.

Я понимаю, что хитрый, но не, я не парился пока. Я просто остановил ту прогу, что привёл, когда она перевалила через 8 миллионов.

Dmitriy40 в сообщении #1661394 писал(а):
Да, конечно 240e3 юнитов G4@71# (да и G5 и G6) можно проверить прямо,

Ну так Вы в августе уже проверили.

Dmitriy40 в сообщении #1661394 писал(а):
самых чистых групп из 71# (объёмы которых мы ещё и не знаем, мрак)

А гляньте нынешнюю тему. В августе я спрашивал и о проверке всего диапазона $0-71\#$, то есть о поиске vc[]. И самый оптимистичный срок был назван Вами — 25 дней. Я уже не помню точно алгоритмы, но вроде бы самые чистые группы можно посчитать гораздо быстрей, совершенно необязательно считать все. Да и 5(?) самых чистых групп и 7 самых грязных уже посчитаны.

Может надо не просто находить количество vc[], то есть юнитов, но и сразу же на лету проверять их по простым больше 71 ...

Конечно группы, где такое крошечное количество чужих чисел (4, 5, 6, ... , 15), да ещё и проверенные по всем модулям до 71, жутко перспективные в плане поиска 19\19.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 682 ]  На страницу Пред.  1 ... 40, 41, 42, 43, 44, 45, 46  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group