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

[Dmitriy40]

mathematician123
Спасибо.

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

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

Сложно сказать, надо точнее оценивать время включая и компиляцию.
Вот скажем до 1e35 по второй таблице надо сделать суммарно 6e20 попыток (плюс 15 раз по 8ч на компиляцию или эквивалент 5e14 попыток), при этом гарантированно или найдётся минимальная 15-ка (данного вида), или переберутся все варианты (данного вида) до известной 15-ки. В худшем случае, если меньших нет, то 6е20 попыток.
Если перебирать по строкам второй таблицы с подстановкой одного простого, то строка -31-37 с подстановкой 41 до тех же 1е35 требует 8.2e15 попыток (с 3.5e13 попыток на компиляцию), все 15 строк с подстановкой только 41 требуют 47e15 попыток (с компиляцией), а все 15 строк с подстановкой простых от 41 до 180 требуют 372e15 попыток (с компиляцией). Паритет c 6e20 попыток наступит для простого примерно 1.2e6, причём из-за времени компиляции, которое превышает время счёта уже для простых начиная примерно с 400.
Выходит да, выгоднее считать с подстановкой по одному простому. Во всяком случае пока не найдётся 15-ка на три-четыре порядка меньшая.

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

О как! А почему напрасно? Какой смысл заваливать тему тоннами статистики?

Тоннами заваливать разумеется не нужно, но раз в неделю почему бы не показать полную табличку до текущей границы поиска? 100-я страница темы обновлялась уже почти месяц назад, найдено много нового. Мне например красивое оформление нафик не сдалось, прямой текст удобнее.

[Huz]

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

А остальные мощности направлены на удлинение имеющихся цепочек.

Just to check the translation on this - you are still searching for longer sequences for $n < 100$? I had been meaning to ask about this, since I thought for example that we would have had $M(36) \ge 14$ by now, or even the full $M(36) = 15$.

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

$M(252)\ge 9$

I hope you are keeping a record of the factorizations of these. I gave up trying to verify them - it seemed a waste of CPU to spend days rediscovering factors you already found.

[EUgeneUS]

Yadryara

(Оффтоп)

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

Но найдётся ли ещё хотя бы один красавец Пентадектлон ниже существующего? Никто не знает.
Этим и прекрасен поиск.

У нас разные представления о прекрасном
Мне бОльшее эстетическое удовольствие доставляют более детерминированные результаты.
Например, нахождение цепочки, доказывающее новую нижнюю границу $M(k)$. Или доказательство, что цепочка минимальна.
Впрочем, это уже обсуждалось, и это всего лишь спор о вкусах.

-- 08.09.2022, 17:48 --

Huz в сообщении #1564395 писал(а):

Just to check the translation on this - you are still searching for longer sequences for $n < 100$?

AFAIU, dear VAL means that he calculates longer chains for $k > 100$

Huz в сообщении #1564395 писал(а):

since I thought for example that we would have had $M(36) \ge 14$ by now, or even the full $M(36) = 15$.

Unfortunately, these results are not available. And I have no idea how to get them. Naive computation time estimates using current methods show unacceptable times. AFAIR, These naive assessments were given somewhere in the depths of the topic.

I think the chains could be improved for $k=24n$ (suck as $k=24, 48, 96$) by using more advanced factorization methods than in PARI/GP, but is not yet ready to formulate a meaningful proposal.

-- 08.09.2022, 17:53 --

mathematician123
Рад видеть! А то уже собирался делать перекличку.

(Оффтоп)

Кстати, я вернулся из мест, где занимался физическим трудом
На данный момент, надеюсь, мне удастся выделять 3-4 часа в неделю на вдумчивую деятельность по данной теме.
Планирую это использовать для финализации статьи по $M(2pq) \le 3$. Так как содержательных замечаний (после учёта предыдущих) не поступало, то там осталось только оформление.

[Dmitriy40]

Наивную оценку времени для доказательства $M(36)=15$ сделать несложно: поиск $M(12)=15$ занял кажется недели три, грубо говоря в 6-7 потоков, примем 20 недель, числа в M36 примерно вдвое длиннее (1e86 против 1e38), значит простые среди них примерно вдвое реже, а нам нужно минимум 11 больших простых (на проверяемых местах), т.е. вероятность ниже в $2^{11}=2048$ раз, или 40 тысяч недель (больше 700 лет) в один поток. Даже сотню потоков мы набрать не можем, значит ожидаемое время не упадёт ниже десятка лет счёта всем вместе. Вот такая оценка "на пальцах".
С другой стороны, 15-ка уже найдена почти в 700 раз меньше, но для этого пришлось проверить более чем на порядок больше паттернов. Т.е. при некоторой оптимизации процесса вычислений можно надеяться найти M36n15 раз в сто раньше той наивной оценки выше, лет за 10 в одном потоке. Потоков 30 мы вроде бы набрать пока можем, а если и VAL соизволит наконец потратить денёк и разобраться как запускать ускорители, то и 50 потоков. Можно надеяться за пару-тройку месяцев (ну полгода) обнаружить цепочку M36n15 и доказать $M(36)=15$. Но это прямо скажем оптимистичная оценка, при уточнении она скорее всего возрастёт в несколько раз. Насколько это acceptable судить не берусь.

[EUgeneUS]

Dmitriy40
Если мне не изменяет память, то с 14 и 15 на 36 делителей есть отдельный геморрой.
Там для 14 и 15 делителей не удается оптимально расставить тройки в паттерне.
Что дополнительно резко ухудшает ситуацию, на порядок минимум

[Dmitriy40]

EUgeneUS
Не, геморрой там с тем что при переходе от 13 к 14 числам резко возрастает количество проверяемых мест, с 6 до 10. Что напрочь убивает вероятность ускорителю обнаружить кандидата (показатель степени 10 вместо 6). Почему и M36n13 было найдено быстро, а n14/n15 нет. Т.е. это кардинальное ухудшение по отношению к M36n13, а не к M12n15.
Цифру же выше 1e86 я взял из реального тестового запуска M36n15 в конце апреля (тогда за сутки проверил 100e85 в 4 потока и не нашёл ни одной ALL цепочки, со всеми 10-ю найденными простыми на проверяемых местах). В плане скорости ускорителей с тех пор ничего сильно не менялось.

[EUgeneUS]

Dmitriy40
ИМХО
1. улучшение оценок $M(k)$ для $k < 100$ может быть связано только с ускорением факторизации больших чисел, по сравнению со скоростью PARI/GP.

2. Нужно ускорение на порядок или больше.

3. Реализация известных алгоритмов на C вряд ли даст такой выигрыш.

4. Но реализация известных алгоритмов с использованием SSE2 и-или AVX (и-или графических карт) такое вроде бы может дать. Наивно предполагаю.

5. Буде случится ускорение факторизации относительно PARI/GP в несколько раз, хотя бы, то можно ожидать улучшение цепочек для $k$ кратных 24. В том числе, улучшения мирового рекорда
Так как паттерны для этих цепочек ("с избытком простых") можно оптимизировать: в пользу $pqr$ в ущерб менее вероятных $pq$.

-- 08.09.2022, 19:47 --

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

Т.е. это кардинальное ухудшение по отношению к M36n13, а не к M12n15.

Да, согласен.

[Dmitriy40]

Ускорение факторизации нужно для цепочек с малым количеством проверяемых мест, когда ускоритель возвращает слишком много кандидатов и основное время тратится в PARI (причём не на isprime, а именно на факторизацию). Для M24, M48, M96 это так и есть, а вот для M36 нет, там PARI занимал лишь треть общего времени (и я кажется знаю как его ещё втрое уменьшить), причём всё оно тратилось на isprime, до факторизации дело вообще не доходило.
В общем я не уверен что факторизация в PARI является самым тормозящим фактором для всех цепочек $k<100$, есть же методы её оптимизировать.

[EUgeneUS]

Другой путь улучшения цепочек для $k < 100$ - экстенсивный.

Грубо говоря, если какая-то цепочка считалась у меня с привлечением мощностей Артема (RTM) 2-3 недели, то следующую можно ожидать за время в 10 раз больше. (это не относится к цепочками на 36 делителей, там переход от 13 к 14 требует увеличения времени на два порядка минимум), то есть 20-30 недель.

При увеличении мощностей в 5 раз ожидаемое время получается 4-6 недель, что уже выглядит приемлемо.

Но для этого нужно "навалиться всем кагалом", а у нас все разошлись по интересам - кто-то считает цепочки для $k > 100$ (что вполне перспективно, так как множество натуральных чисел бесконечно), кто-то улучшает цепочки для $k=12$, тоже занятие на 10 млрд. лет, как Вы оценили

-- 08.09.2022, 20:15 --

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

а вот для M36 нет, там PARI занимал лишь треть общего времени, причём всё оно тратилось на isprime, до факторизации дело вообще не доходило.

Поэтому, улучшение цепочек для 36 делителей считаю бесперспективным при наличных мощностях (даже "в сумме", если всем навалиться). Можно что-то половить в 60 или 84 делителя, но это нужно отдельно посмотреть.

-- 08.09.2022, 20:30 --

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

Там для 14 и 15 делителей не удается оптимально расставить тройки в паттерне.

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

Не, геморрой там с тем что при переходе от 13 к 14 числам резко возрастает количество проверяемых мест, с 6 до 10. Что напрочь убивает вероятность ускорителю обнаружить кандидата (показатель степени 10 вместо 6).

Второе есть следствие первого.

-- 08.09.2022, 21:01 --

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

Поэтому, улучшение цепочек для 36 делителей считаю бесперспективным при наличных мощностях (даже "в сумме", если всем навалиться).

Под "наличными мощностями" тут имеются в виду озвученные процессорные мощности. Но есть же видеокарты, как минимум одна
Вспоминая оценки, она должна бы кратно увеличить мощности

[VAL]

Huz в сообщении #1564395 писал(а):

Just to check the translation on this - you are still searching for longer sequences for $n < 100$? I had been meaning to ask about this, since I thought for example that we would have had $M(36) \ge 14$ by now, or even the full $M(36) = 15$.

At the moment, a search is underway for a run of 17 consecutive numbers with 96 divisors.

Huz в сообщении #1564395 писал(а):

I hope you are keeping a record of the factorizations of these.

Unfortunately I didn't keep factorization of the last number (8 previous may be found for some seconds).

[Huz]

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

Unfortunately I didn't keep factorization of the last number (8 previous may be found for some seconds).

Ah, that's a shame; maybe it would be worth posting factorizations when you announce these. (Or if you feel they would be offtopic here, feel free to email them to me - I can put them in my database of results so that they are preserved.)

[Dmitriy40]

Достаточно было бы указывать всего по одному трудно находимому делителю, остальное разлагается почти мгновенно.
В PARI кстати есть команда addprimes() для добавления таких делителей к списку проверок чтобы факторизация проходила быстрее.

[Yadryara]

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

В частности это сразу снова ограничивает $M(12)\le15$ и требует во всех таких цепочках (длиной от 10 и выше) число вида $32p$.

Кстати, совсем недавно об этом же писал gris, но почему-то в другой теме:

gris в сообщении #1563557 писал(а):

Теперь прояснилось, что без $32p$ нет даже десятки:)

Я уже давно думал попросить VAL обновить 100-ю страницу. Вот сегодня, когда Маруся после 2-х фальстартов пройдёт наконец 12 000 е30 в 29-м комплекте, как раз и наступит благоприятный момент. Вышлю новые таблицы взамен старых.

Dmitriy40, всё ж таки прошу цепочки постить начиная с самого числа, а не с имени паттерна.

[Dmitriy40]

Huz
That number n+8 has large divisors: 83698472713236973121374446371971582145593, 48962887928467132052461716355944614657219060742569565490483369258223
Factorized in 7 hours.

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

Dmitriy40, всё ж таки прошу цепочки постить начиная с самого числа, а не с имени паттерна.

Это неудобно.
Вот Вам команда для перестановки местами числа и имени паттерна (и туда и обратно), сможете сами для себя выбрать любой порядок, запускать в консоли:
for /f "tokens=1,2,3* delims=:" %a in (file_in.txt) do @echo %b:%a:%c>>file_out.txt

[VAL]

Huz в сообщении #1564424 писал(а):

Ah, that's a shame; maybe it would be worth posting factorizations when you announce these.

Ok. I will record difficult factorizations for the next time. If it is important i can repeat factorization for 252. It takes above 80 hours.

-- 09 сен 2022, 13:29 --

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

That number n+8 has large divisors: 83698472713236973121374446371971582145593, 48962887928467132052461716355944614657219060742569565490483369258223
Factorized in 7 hours.

О! Это чем так быстро?