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

[EUgeneUS]

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

Полтора месяца назад запускал pcoul -p100 -x6e26 -g9 -f13 12 13, заняло два дня, нашлась известная 13-ка, и больше ничего.

Спасибо, что написали/напомнили. Это, конечно, резко снижает вероятность найти более "низкую" цепочку.

Ещё вот, что заметил: в "перспективных паттернах" (с минимумом количества проверяемых мест) подставляется наибольшее количество простых в квадрате. Что сильно увеличивает LCM после подстановки всех квадратов простых. А это должно бы сильно уменьшить вероятность найти цепочку в заданном интервале.
С другой стороны, это должно бы как-то компенсироваться большим количеством вариантов перестановок квадратов простых...

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

По поводу 13-к. Мне весьма интересен огромный гэп между 1-й и 2-й. Нынешняя вторая 13-ка больше первой в 185 раз !!

Спасибо! Это интересно. А с 14-ками подобный гэп наблюдается?

[Dmitriy40]

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

То есть, например, для 15-ки осталось $528-16= 512$ паттернов:

Поясните пожалуйста почему Вы к математическим запретам стали добавлять численные? А если вдруг в коде решения уравнений Пелля у pcoul есть ошибки?
Ведь так можно и все остальные паттерны исключить, просто проверив их. Но если запрет математический, то решений не будет не только до 8e34, но и до любого предела, а вот с численными запретами это совершенно не так, решения вполне могут быть где- то дальше (очень-очень сильно дальше) текущей минимальной цепочки.

И второй вопрос, чисто из любопытства: а почему считаете количество неделимых паттернов только при расстановках простых до 120? А не до максимального предела где-то за 4e16? Ведь для доказательства минимальности надо подставлять и другие простые и проверять нет ли решений. А проверять лишь простые до малого предела можно только для поиска очередной меньшей цепочки. Полезнее было бы вывести формулу количества неделимых паттернов от величины подставляемых простых, пусть даже она будет весьма примерной и работать лишь до p<1e9 (где все переборы остаются квадратичными).

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

А с 14-ками подобный гэп наблюдается?

Нет, вот наименьшие известные мне 14-ки:
1966089440441196672524986345512345
3051183708749776744662169818575641
5536971777226727622137176815138841
5625796463484324070009617271709145
11865604480910140781102260713619545
Причём первые три были найдены не в рамках поиска 15-ки, а специально, все остальные (и не показанные штук 25 тоже) - при поисках 15-ки.

[Yadryara]

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

Спасибо! Это интересно. А с 14-ками подобный гэп наблюдается?

Конечно нет. И, вроде бы, ни с какими другими цепочками по 12 делителей тоже.

Инфа именно по 14-кам на 100-й странице несколько устарела.

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

Нет, вот наименьшие известные мне 14-ки:
1966089440441196672524986345512345
3051183708749776744662169818575641
5536971777226727622137176815138841
5625796463484324070009617271709145
11865604480910140781102260713619545

А они точно все непрерывные?

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

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

С мат. запретами я уже закончил. 528 внешних паттернов. Точка.

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

Кстати, ещё один мультиквадратный есть: b629. Соответственно, если и его обсчитать, останется не более 511 внешних паттернов для D(12,15).

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

А если вдруг в коде решения уравнений Пелля у pcoul есть ошибки?

О чём Вы спрашиваете? Да, могут быть ошибки.

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

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

Да, собственно этим ведь и занимались последние два месяца. И уже хотя бы однократно проверили все возможные паттерны для 11-к и 12-к.

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

И второй вопрос, чисто из любопытства: а почему считаете количество неделимых паттернов только при расстановках простых до 120?

Это я пока считаю. Например потому, что в рекордных цепочках встречаются простые в квадратах до 113 включительно.

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

А не до максимального предела где-то за 4e16?

Конечно это запланировано. А Вы помните, что есть ещё и стартовые числа, количество которых было трудно учесть?

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

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

Да, да, всё так.

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

Полезнее было бы вывести формулу количества неделимых паттернов от величины подставляемых простых, пусть даже она будет весьма примерной и работать лишь до p<1e9 (где все переборы остаются квадратичными).

Ну вот о таких вещах и думаю не спеша.

[Dmitriy40]

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

А они точно все непрерывные?

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

x=1966089440441196672524986345512345;
print(x); t0=getwalltime(); n=0;
for(d=1,15, print("+",d-1,":",nd=numdiv(x+d-1),"\t",factor(x+d-1)); if(nd==12, n++));
print("n=",n,", time: ",strtime(getwalltime()-t0));

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

О чём Вы спрашиваете?

Если с математическими запретами закончили, то уже ни о чём.

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

А Вы помните, что есть ещё и стартовые числа, количество которых было трудно учесть?

Вот и давайте грубо прикинем нижнюю границу общего количества неделимых паттернов, у которых шаг всё ещё меньше 8e34.
Возьмём только паттерны без sq потому что те можно проверить быстрее линейного поиска. Таких паттернов 488шт для 15-ки.
В 212 из них можно расставить 6 простых. Чтобы при этом шаг не превысил 8e34 все 6 простых должны быть меньше (когда какие-то больше, а остальные ещё меньше пока не учитываю, и всё округляю) $\sqrt[6]{8\cdot10^{34}/7214407200}=15000$. Выбрать 6 чисел из $\pi(15000)=1750$ можно примерно $1750^6=3\cdot10^{19}$ способами. Для всех 212 паттернов общее количество получится уже 6e21.
В 224 из 488 можно расставить 7 простых. Все они должны быть (с оговоркой выше) меньше $\sqrt[7]{8\cdot10^{34}/7214407200}=3800$, таковых простых $\pi(3800)=530$, выбрать 7 из них можно 1e19 способами, всего выходит 2.6e21.
В 50 из 488 можно расставить 8 простых. Все они должны быть (с оговоркой выше) меньше $\sqrt[8]{8\cdot10^{34}/7214407200}=1350$, таковых простых $\pi(1350)=215$, выбрать 8 из них можно 4.5e18 способами, всего выходит 2.3e20.
Итого только вот с такой оговоркой выходит почти 9e21 неделимых паттерна. А без оговорок их будет ещё больше, может даже на пару порядков.
Собственно на этом все вычисления количества неделимых паттернов можно и закончить, уже нижняя граница 9e21 штук слишком велика для любых практических целей и вычислять более точное значение совершенно незачем.

Если же использовать ускорители для исключения последних переборов, то грубо можно заменить 3-4 перебора на линейный поиск ускорителями, но вариантов всё равно останется порядка 1e10 и только компиляция такого количества ускорителей займёт 3e9 секунд или сотню лет. Плюс несколько тысяч лет счёт по ним. И это нижняя граница! И пока не наберётся под сотню тысяч потоков это остаётся не слишком реальным.

[Yadryara]

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

Возьмём только паттерны без sq потому что те можно проверить быстрее линейного поиска.

Ну вот поэтому я и спрашивал, насколько быстро можно их проверить. Речь об оставшихся 23-х одноквадратных паттернах, которые у Хьюго отмечены [sq=1]:

b127-130, b196-198, b248-251, b571, b582, b602, b611, b621-628

Остальные расчёты проверю. Сразу скажу, что меня не удивила 22-я степень десятки.

[Dmitriy40]

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

Ну вот поэтому я и спрашивал, насколько быстро можно их проверить. Речь об оставшихся 23-х одноквадратных паттернах, которые у Хьюго отмечены [sq=1]:

Проверить можно часов за 10 каждый. Наверное.

[Yadryara]

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

Проверить можно часов за 10 каждый. Наверное.

Тогда смотрите логи
Во всем известном блоге...

Там и на 100 часов не похоже. Проверялся паттерн b127(12-15).

Потихоньку начинаю проверять Ваш расчёт.

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

Таких паттернов 488шт для 15-ки.
В 212 из них можно расставить 6 простых.
[..]
В 224 из 488 можно расставить 7 простых.
[..]
В 50 из 488 можно расставить 8 простых.

Это подтверждаю. А ещё

в 2 из 488 можно расставить 9 простых.

Думаю, что Вы этим просто пренебрегли.

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

Выбрать 6 чисел из $\pi(15000)=1750$ можно примерно $1750^6=3\cdot10^{19}$ способами.

Уточню: выбрать и расставить. Потому что выборка, это обычно число сочетаний, а оно будет в $6!$ раз меньше. Но способов расставить выбранные как раз $6!$

Так что число размещений надо брать. Вот его и Вы взяли. Примерно.

$1745\cdot1746\cdot1747\cdot1748\cdot1749\cdot1750\approx1750^6$

Дальнейшее пока не проверял.

[Dmitriy40]

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

Тогда смотрите логи
Во всем известном блоге...

Там и на 100 часов не похоже. Проверялся паттерн b127(12-15).

Это известно чьи проблемы (особенно с пониманием смысла параметров при запуске pcoul) и уж точно не мои, я то как раз в логи и смотрел, не с потолка же взял цифру 10ч (точнее я её прикинул по первому часу, потому и "наверное" добавил, но потом она прекрасно сошлась):

T:\M12minimal\Hugo>pcoul -v -f13 -x8e34 -b127 12 15
001 pcoul(12 15) -f13 -x80000000000000000000000000000000000 -b127 *RT*
3^2.5 2.13^2 11 2^2.3 7^2 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3 2.11 13: 60988592220412786461516805 / 60989071978082967093956104
367 coul(12, 15): recurse 280, walk 3786, walkc 64728917793 (36716.80s)

Кстати это выходит можно считать хорошим примером когда ключ ограничения чего-то (-p в данном случае) кардинально меняет метод проверки паттерна (даже не знал об этом).

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

Думаю, что Вы этим просто пренебрегли.

Именно, правильно думаете, они на общую картину влияют меньше погрешности оценки.

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

Уточню: выбрать и расставить. Потому что выборка, это обычно число сочетаний, а оно будет в $6!$ раз меньше. Но способов расставить выбранные как раз $6!$
Так что число размещений надо брать. Вот его и Вы взяли. Примерно.

Согласен, всё так.

[Yadryara]

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

В 212 из них можно расставить 6 простых. Чтобы при этом шаг не превысил 8e34 все 6 простых должны быть меньше (когда какие-то больше, а остальные ещё меньше пока не учитываю, и всё округляю) $\sqrt[6]{8\cdot10^{34}/7214407200}=15000$.

Сейчас вот разбираюсь с шагами. И шаг $7214407200$ встречается в 94 случаях из 212. Во всех остальных случаях шаг больше.

-- 01.01.2023, 14:09 --

А почему, кстати, корень 6-й степени извлекается? Вы что опять про квадрат забыли ?? Разве не корень 12-й степени надо извлекать?

[Dmitriy40]

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

А почему, кстати, корень 6-й степени извлекается? Вы что опять про квадрат забыли ?? Разве не корень 12-й степени надо извлекать?

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

[Yadryara]

Сейчас уже три вопросительных знака поставлю. Восклицательные, так и быть, не буду.

Как об этом можно забыть ???

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

И шаг $7214407200$ встречается в 94 случаях из 212. Во всех остальных случаях шаг больше.

Вот они 8 различных шагов(LCM):

$7214407200 = 2^5\cdot3^2\cdot5^2\cdot7^2\cdot11^2\cdot13^2$ — 94;
$2474541669600= 2^5\cdot3^2\cdot5^2\cdot7^5\cdot11^2\cdot13^2$ — 42;
$9602375983200 = 2^5\cdot3^2\cdot5^2\cdot7^2\cdot11^5\cdot13^2$ — 20;
$15850052618400= 2^5\cdot3^2\cdot5^2\cdot7^2\cdot11^2\cdot13^5$ — 28;
$3293614962237600 = 2^5\cdot3^2\cdot5^2\cdot7^5\cdot11^5\cdot13^2$ — 10;
$5436568048111200= 2^5\cdot3^2\cdot5^2\cdot7^5\cdot11^2\cdot13^5$ — 12;
$21096420035090400 = 2^5\cdot3^2\cdot5^2\cdot7^2\cdot11^5\cdot13^5$ — 4;
$7236072072036007200 = 2^5\cdot3^2\cdot5^2\cdot7^5\cdot11^5\cdot13^5$ — 2.

$94+42+20+28+10+12+4+2=212$

И в них во всех ведь тоже все простые как минимум в квадратах.

[Yadryara]

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

Разве не корень 12-й степени надо извлекать?

$\sqrt[12]{8\cdot10^{34}/7214407200}\approx122$.

Вроде как то самое ограничение в 113 получилось. Но на самом деле конечно и гораздо большие простые числа в квадратах могут быть. Конкретный расчёт пока не делал.

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

И не до 8е34, а до 81е33.

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

Может кому-то захочется указать само число $80215613469168729088982885848674841$.

Однако Дмитрий проигнорил.

А теперь уже и Ахиллес вслед за Дмитрием проверяет до 8е34. Но ведь кусочек-то остаётся непроверенным. Зачем же его оставлять...

[Yadryara]

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

А теперь уже и Ахиллес вслед за Дмитрием проверяет до 8е34.

А нет, прошу прощения, это в планах у Ахиллеса было:

Цитата:

pcoul -v -f13 -x8e34 -b127 12 15

А запуск был такой:

Цитата:

pcoul -rlog_b127_15.txt -x80215613469168729088982885848674841 -f13 -b127 12 15

Это хорошо.

(Источник)

Не сочтите за цитату без источника. Ибо этот источник вроде как нельзя на нашем форуме публично сообщать. Но в личке я сообщаю.

[Dmitriy40]

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

Однако Дмитрий проигнорил.

Потому что 8e34 я использую только для оценок (в том числе времени счёта), а не для реального счёта, в котором как раз беру или 8.1e34, или 8.03e34, лично меня такая точность в обоих случаях устраивает и запоминать и вбивать/копировать точное число ленюсь.

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

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

Да чего его там делать-то ... 10 минут программку написать (главное снова про квадраты не забыть) и полминуты она считает:

\\Сколько вариантов выбора 6-ти простых чтобы их произведение не превысило sqrt(8e34/7.2e9)=3.335e12
n=0; q=0; m=3.335e12;
{forprime(a=17,ceil(m^(1/6)),\\Простые до 17 не учитываем
   forprime(b=a+1,ceil((m/a)^(1/5)),
      forprime(c=b+1,ceil((m/a/b)^(1/4)),
         forprime(d=c+1,ceil((m/a/b/c)^(1/3)),
            forprime(e=d+1,ceil((m/a/b/c/d)^(1/2)),
               n+=primepi(ceil(m/a/b/c/d/e))-6;\\Простые до 17 не учитываем
               \\forprime(f=e+1,ceil(m/a/b/c/d/e), q+=ceil(8e34/7.2e9/(a*b*c*d*e*f)^2););\\Подсчитаем и количество итераций
            );
         );
      );
   );
);}
print(n*6!);\\Размещений в 6! раз больше
print(q*6!);\\Итераций тоже в 6! раз больше

Вывод:
483272950320
49865208777360

Всего порядка 5e11 на каждый паттерн с LCM=7.2e9, которых 94, т.е. всего 4.5e13 вариантов.
Паттерны с большими LCM можно не учитывать, их хоть и вдвое больше, но вариантов будет сильно меньше из-за сокращения количества простых. Желающие могут изменить m= и проверить прямо. Например общее количество вариантов со следующим по величине LCM=2.47e12 всего чуть менее 4e11, т.е. менее 1%.

Но общее количество вариантов паттернов мало о чём говорит в плане затрат времени, ведь каждый из них надо ещё и просчитать до 8e34, т.е. надо бы знать и потребное количество итераций, для оценки которого раскомментировать команду forprime(f=e+1,...);, что замедлит программу до десятка минут и выдаёт результат в 5e13 итераций (2.1e15 на все 42 паттерна), т.е. в среднем всего по 100 итераций на паттерн, что например для ускорителей очень и очень мало.
Получается что на каждый паттерн из 42 надо почти 5e11 компиляций ускорителей и потом ещё 5e13 итераций им выполнить. Компиляция занимает 0.3с, выполнение итераций можно принять 1e9/c, компиляция занимает намного больше времени, значит прямой смысл исключать квадратичные переборы и уменьшать время компиляции за счёт возрастания количества итераций.

И теперь имея готовую программку оценки количества итераций и количества вариантов ускорителей можно легко оценить что будет если убрать один цикл перебора квадратов простых, для этого заменим всё тело внутреннего цикла на n++; q+=ceil(8e34/7.2e9/(a*b*c*d*e)^2); (т.е. уберём цикл по f) и запустим программу снова, она за 3с выдаст 23e9 компиляций и 28e15 итераций. 23e9 компиляций (по 0.3c) всё ещё в 250 раз дольше 28e15 итераций, хотя последние уже занимают почти год счёта (в один поток со скоростью 1e9/c).

[Yadryara]

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

Потому что 8e34 я использую только для оценок (в том числе времени счёта), а не для реального счёта,

Это понятно было, но сейчас-то очень похоже, что Вы именно реально посчитали за 10 часов паттерн b127.

Буду проверять Ваш новый расчёт. Пока только вот это заметил.

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

Сколько вариантов выбора 6-ти простых чтобы их произведение не превысило sqrt(8e34/7.2e9)=3.335e12

Во-первых. Даже если превысит, стартовое число всё равно может быть подходящим.

Во-вторых, Ваша формулировка эквивалентна этой?

Сколько вариантов выбора 6-ти простых, таких чтобы произведение их квадратов не превысило

8e34/7.2e9 = 1.112e25