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

[Yadryara]

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

А почему внизу простые до 43?

Потому что их 14 штук — это и есть $P_{\#14}$.

[EUgeneUS]

Dmitriy40
Напомните, пожалуйста, как Вы строили паттерны для поиска цепочки длиной 14 на 12 делителей (которая сейчас минимально известная).

Дело в том, что в паттерне, которому она принадлежит:
а) получается 7 неизвестных простых (проверяемых мест) после расстановки обязательных простых (до 13 включительно).
б) и ещё четыре добавляется после расстановки квадратов "средних" простых. Итого 11 проверяемых мест.

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

[Dmitriy40]

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

Dmitriy40
Напомните, пожалуйста, как Вы строили паттерны для поиска цепочки длиной 14 на 12 делителей (которая сейчас минимально известная).

Смотрел исключительно паттерны без квадратов $Ap^2$.
Смотрел только паттерны требующие 5-ти дополнительных простых (чтобы в каждой группе было 120 паттернов, а не 720) и при размещении их всех дающие 11 проверяемых мест.
Дальше проверял два класса:
1. Размещал все 5 простых, получалось ровно 11 проверяемых мест, размещал простые 17,19,23,{29..43},{31..47} и 17,19,29,{31..43},{37..47} во всех 120 перестановках.
2. Размещал лишь 4 простых 17,19,23,29 и 17,19,31,37 оставляя 5-е место пустым, тоже во всех 120 перестановках, при этом могло получиться и 11 проверяемых мест, и 10.

Вообще по моему существуют два больших класса паттернов (без квадратов): с дополнительными 5 и 6 простыми. И каждый из них делится на классы с 10, 11 и 12 проверяемыми местами, за исключением комбинации 5+10, она не существует. Т.е. всего 5 комбинаций: 5+11, 5+12, 6+10, 6+11, 6+12, всего 70+24+78+28+2=202 группы и соответственно $5!(70+24)+6!(78+28+2)=89040$ паттернов. До размещения дополнительных простых при этом LCM=7214407200 у всех. Я проверял только первую группу, 5+11.

И как-то я не слишком уверен что комбинация 6+10 вероятнее комбинации 5+11. Зато паттернов в 6 раз больше, а это время компиляции, таких паттернов 78 групп по 720шт в каждой, 56160шт всего, их компиляция займёт часов 6-7 на каждый вариант из 6-ти дополнительных простых, а таких вариантов ого-го.

Это все если проверять по работающей технологии, с компиляцией ускорителей для каждого варианта и последующим линейным перебором с ускорителями. Что и как будет с pcoul или с моим квадратичным перебором (и компиляцией на лету) не знаю, надо проверять. Причём не забывать что pcoul проверяет сразу всю группу паттернов под одним именем bXXX, их как раз 202 и выходит. И каждый такой паттерн (группа в моей терминологии) проверяется похоже много недель (даже не знаю сколько именно), даже с ограничением простых.

[EUgeneUS]

Dmitriy40
Спасибо!

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

И как-то я не слишком уверен что комбинация 6+10 вероятнее комбинации 5+11.

Это просто. После подстановки квадратов, такие паттерны отличаются только тем, что у первой группы надо попасть в 10 простых и в 4 $pq$, а у второй группы - в 11 простых и 3 $pq$, но вероятность $pq$ заметно больше, чем простого.
Другое дело, что вторая комбинация может находиться быстрее, потому что с ускорителями быстрее проверяется простое, а не факторизация большого числа.

У меня получились такие группы (по анализу выдачи pcoul).
10 простых (после подстановки квадратов):
5+5 (10) - 4 ре штуки.
6+4 (10) - 38 штук
7+3 (10) - 36 штук
Все с $LCM=7214407200$ (до подстановки квадратов).

11 простых (после подстановки квадратов): всего 316 групп (b*). Причем встречаются разные LCM, как больше $LCM=7214407200$, так и меньше.

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

Вообще по моему существуют два больших класса паттернов (без квадратов): с дополнительными 5 и 6 простыми.

У меня получилось так:
1. Количество проверяемых мест (больших простых) до расстановки квадратов бывает от 5 до 9.
2. Количество "дополнительных" проверяемых мест после расстановки квадратов бывает от 3 до 8.
3. Не все комбинации возможны. Минимальное общее количество (после подстановки квадратов) проверяемых мест - 10. (см. выше).

Это по паттернам без квадратов, но с любым возможным LCM.

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

И каждый такой паттерн (группа в моей терминологии) проверяется похоже много недель (даже не знаю сколько именно), даже с ограничением простых.

Это да. Но всё таки хочу проверить. Может быть на выходных запущу.
Всё указывает, что 14-ку можнро улучшить, может быть на порядок или три

-- 20.12.2022, 08:15 --

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

или с моим квадратичным перебором (и компиляцией на лету)

Кстати, а Вы не думали об использовании этого метода для поиска новых рекордных цепочек?
ИМХО:
1. Цепочки "с недостатком простых". $k=12(2n+1)$
Здесь могло бы сыграть роль то, что ожидаемая цепочка будет заметно меньше, чем при линейном переборе с фиксированными квадратами простых. А значит вероятность найти её будет заметно выше. Это мы видели при поиске 15-ки на 12 делителей - лучше проверить как можно более полно "низины".
Возможно, этого эффекта будет достаточно, чтобы найти 14, а то и 15-ку, на 36 делителей.

2. Цепочки "с избытком простых". $k=12(2n)$.
Тут, как мы видели ранее, ускорители не столь эффективны. Потому что оказывается небольшое количество проверяемых мест.
Владимир на таких цепочках "задавил мощностями" даже без ускорителей.
Но опять же квадратичный перебор тут должен бы помочь ровно так же.
Остаётся загадкой, почему Хуго с помощью pcoul не нашел подобные рекордные цепочки. Может просто не искал, а может из-за торможения pcoul по сравнению со скриптами на PARI/GP....

[Dmitriy40]

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

Это просто. После подстановки квадратов, таки паттерны отличаются только тем, что у первой надо попасть в 10 простых и в 4 $pq$, а у второй группы - в 11 простых и 3 $pq$, но вероятность $pq$ заметно больше, чем простого.
Другое дело, что вторая комбинация может находиться быстрее, потому что с ускорителями быстрее проверяется простое, а не факторизация большого числа.

С вероятностью согласен.
А про скорость, не факт: скорость факторизации вообще не влияет, как и отличие 10 или 11 проверяемых мест для ускорителя. Вот что паттернов в 6 раз больше замедляет проверку в 6 раз, но что они дают в $p^2$ больше шаг проверки грубо во столько же раз ускоряет (по сравнению с 5+11 или 5+12 вариантами) должно пересилить и варианты 6+10, 6+11, 6+12 будут проверяться быстрее. Кстати для pcoul так и есть, если 6+10 и 6+11 проверяются по 30с (очень сильно ограничивая диапазон проверки), то 5+11 уже 3500с. Возможно Вы правы и имеет смысл запустить проверку вариантов 6+10 ...

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

У меня получились такие группы (по анализу выдачи pcoul).

У меня такие же.

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

11 простых (после подстановки квадратов): всего 316 групп (b*). Причем встречаются разные LCM, как больше $LCM=7214407200$, так и меньше.

А вот здесь нет, видимо Вы не стали исключать или квадраты ($Ap^2$) или скорее степени 1 и 5 (я брал только вторые потому и получил 202 групп всего и 70 групп 5+11).

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

Кстати, а Вы не думали об использовании этого метода для поиска новых рекордных цепочек?

Да мне пока всё недосуг сравнить скорость обновлённой pcoul -W и моей компиляции на лету, возможно pcoul у меня выиграет, особенно если не будет перебирать слишком длинные линейные переборы (и ещё большой вопрос где можно без таковых обойтись). Ну и никак не допишу автоматический выбор глубины рекурсии, а вручную что-то запускать лень (слишком много вариантов и какой и почему выбрать неясно).

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

Остаётся загадкой, почему Хуго с помощью pcoul не нашел подобные рекордные цепочки.

А Вы сами попробуйте. У меня например поиск вероятно наименьшей D12n13 (до 6e26) занял двое суток, а поиск вероятно наименьшей D12n14 (до 2e33) занял бы лет 10 (всё в один поток). А про D24 или D36 ... Там только групп паттернов (bXXXX) десятки и сотни тысяч или миллионы! Да ещё и числа огромные - соответственно перебирать квадратично простые надо очень и очень далеко. И даже если искать хоть какое-то решение, то мест для размещения простых для n>15 будет очень много и соответственно глубина рекурсии большая и соответственно время перебора огромное. Вот поискать D36n15 в принципе можно, но надо выбрать правильный паттерн из 336648 или 252835 без квадратов (кстати pcoul под винду глючит с выдачей всех паттернов в таком количестве). Впрочем, нет, тоже не поможет: слишком много вариантов подстановки дополнительных простых, их перебор идёт долго, да плюс ещё числа слишком большие (до 1e90 решения наверняка нет) и включается немалый линейный перебор на каждый вариант. В общем сами попробуйте.

-- 20.12.2022, 10:16 --

Huz

T:\M12minimal\Hugo>pcoul -f13 -v -x2e30 -g6 -p1e15 -W1e9 -b319 12 14
001 pcoul(12 14) -p2764472320 -W1000000000 -f13 -g6 -x2000000000000000000000000000000 -b319 *RT*
2.7^2 13^2 2^2.3 11^2 2.5^2 3 2^5 7 2.3^2 5 2^2 3 2 . W(2762008453,12): 15 / 17

What's that supposed to mean?! Why -p2764472320 instead of -p100000000000000000?! It looks like you have somewhere too early brought the number to the (u)int format.

The second pcoul glitch under windows:

T:\M12minimal\Hugo>pcoul.exe -a -f13 -x1e199 36 15 |findstr /V /B "203"
001 pcoul(36 15) -f13 -x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 *RT*
3^8 2 5 2^2.3 7^5 2 3 2^8.5 . 2.3^2 . 2^2.7 3.5^8 2 .
3^5 2 5 2^2.3 7 2 3 2^8.5 . 2.3^2 . 2^2.7^5 3.5^8 2 .
3^2.5 2 11 2^2.3 7^5 2.5^8 3 2^8 . 2.3^8 5 2^2.7 3 2.11^8 .
. 2 3.5^2 2^2.7^2 11 2.3^2 . 2^8.5 3 2 7 2^2.3 5 2 3^5
3^2.5 2 . 2^2.3.11^2 7^5 2.5^2 3 2^17 . 2.3^2 5 2^2.7 3 2 11
5 2 3 2^2.7 . 2.3^2.5^2 11^17 2^17 3 2 5.7^8 2^2.3 . 2 3^5
3^2 2.5.7^2 . 2^2.3 11^17 2 3.5 2^5 7 2.3^8 . 2^2.5 3 2 .
11 2 3 2^2 5 2.3^2 7 2^3 3 2.5^8 . 2^2.3.11^2 . 2.7^8 3^2.5
. 2 3 2^2 5 2.3^2 7^3 2^3 3 2.5 11^5 2^2.3 . 2.7 3^8.5
367 coul(36, 15): recurse 21360, walk 279600, walkc 22 (9.45s)

The number and list of patterns varies with each run, but on average remains about the same - that is, there are always a few patterns without a number that are not identical to any patterns with a number.
This is observed on the last version as well as on the previous one. I didn't check older ones.

[EUgeneUS]

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

А вот здесь нет, видимо Вы не стали исключать или квадраты ($Ap^2$) или скорее степени 1 и 5 (я брал только вторые потому и получил 202 групп всего и 70 групп 5+11).

да, тут я не исключал степени 1 и 5 (поэтому и LCM получался разным).

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

Вот поискать D36n15 в принципе можно, но надо выбрать правильный паттерн из 336648 или 252835 без квадратов (кстати pcoul под винду глючит с выдачей всех паттернов в таком количестве)

А Вам будет не сложно выслать эти паттерны мне на почту?

-- 20.12.2022, 10:37 --

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

(до 1e90 решения наверняка нет)

Мои гадания на трендах ;) показывают, что минимальную 14-ку на 36 делителей следует ожидать где-то в районе 1e56 (то есть до 1e60 должна найтись не самая минимальная), а минимальную 15-ку на 36 делителей следует ожидать в районе 1e62 (то есть до1e70 должна найтись не самая минимальная). Но то такое, там начало тренда очень короткое, всего пять значений.

[Dmitriy40]

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

до 1e90 решения наверняка нет

Да, тут я похоже не прав, взял найденную 13-ку, которая порядка 1e70, но она совершенно явно не минимальная, и если D12n15 нашлась всего в 2e8 раз дальше минимального шага, то и D36n15 более-менее минимальная может быть где-то 1e51-1e60.

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

А Вам будет не сложно выслать эти паттерны мне на почту?

А смысл? Сами же можете легко получить за полминуты: pcoul -x1e99 -f13 -a 36 15 |findstr /V "sq" >D36n15.txt (понятно что отфильтровывание квадратов можно и не делать или сделать потом).
Но во первых там у Хуго глюки (см. выше), во вторых список будет с unix-style переводами строк (хотя PARI их легко берёт, про Excel/OpenOffice не знаю). Впрочем, ладно, сейчас вышлю (уже с windows-style переводами строк).

[EUgeneUS]

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

Впрочем, ладно, сейчас вышлю (уже с windows-style переводами строк).

Спасибо!

[miflin]

(Оффтоп)

Прошу прощения.
Влез в тему (в первый и последний раз), ощущая себя в ней абсолютно инородным телом.
Складывается впечатление, что громоздкость задачи не позволяет получить результат,
в правильности которого участники были бы уверены на 100%.

[Dmitriy40]

miflin
Основной результат был получен ещё в апреле 2022. И в нём уверенность 100%.
После чего были получены ещё множество результатов, тоже 100%.
Все они перечислены в первом сообщении темы.
Но потом некоторые занялись поиском более коротких цепочек (и в них тоже уверенность 100%), а ещё потом и доказательством минимальности решений, и вот в последнем абсолютно полной уверенности уже нет. Но её в общем и не может быть так как в процессе используются достаточно сложные и математические и программистские трюки, доказывать 100% корректность которых трудно (очень) и всем лень. Остановились на обычном в программировании состоянии "пока не найдено ошибок считаем верным". А существенных ошибок пока вроде бы не найдено (по мелочи что-то было, но Hugo оперативно исправил и пересчитал всё затронутое).

[Huz]

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

Это да. Но всё таки хочу проверить. Может быть на выходных запущу.
Всё указывает, что 14-ку можнро улучшить, может быть на порядок или три

I have been running some checks with restricted primes to smaller limits. Taking the existing upper limit for $D(12,14)$ as $U$, I find no results for $U / 10^3$ with "-p72" (which took about 9.5 days); the same with "-p120" is about 25% complete after 10 days.

It seems likely that a better-targeted approach is needed: for other tasks, I have had some success searching for likelier patterns and running them manually. I've been trying to think of a useful way to make that easier, and welcome any ideas; currently the best idea I have is to support a list of batch ids "-b1,3,5,7" and write a separate script to supply them.

-- 20.12.2022, 15:20 --

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

Huz

T:\M12minimal\Hugo>pcoul -f13 -v -x2e30 -g6 -p1e15 -W1e9 -b319 12 14
001 pcoul(12 14) -p2764472320 -W1000000000 -f13 -g6 -x2000000000000000000000000000000 -b319 *RT*
2.7^2 13^2 2^2.3 11^2 2.5^2 3 2^5 7 2.3^2 5 2^2 3 2 . W(2762008453,12): 15 / 17

What's that supposed to mean?! Why -p2764472320 instead of -p100000000000000000?! It looks like you have somewhere too early brought the number to the (u)int format.

Huh, not sure; I don't see an immediately obvious bug, will look into it.

Цитата:

The second pcoul glitch under windows:

T:\M12minimal\Hugo>pcoul.exe -a -f13 -x1e199 36 15 |findstr /V /B "203"
001 pcoul(36 15) -f13 -x<1e199> *RT*
3^8 2 5 2^2.3 7^5 2 3 2^8.5 . 2.3^2 . 2^2.7 3.5^8 2 .
3^5 2 5 2^2.3 7 2 3 2^8.5 . 2.3^2 . 2^2.7^5 3.5^8 2 .
3^2.5 2 11 2^2.3 7^5 2.5^8 3 2^8 . 2.3^8 5 2^2.7 3 2.11^8 .
. 2 3.5^2 2^2.7^2 11 2.3^2 . 2^8.5 3 2 7 2^2.3 5 2 3^5
3^2.5 2 . 2^2.3.11^2 7^5 2.5^2 3 2^17 . 2.3^2 5 2^2.7 3 2 11
5 2 3 2^2.7 . 2.3^2.5^2 11^17 2^17 3 2 5.7^8 2^2.3 . 2 3^5
3^2 2.5.7^2 . 2^2.3 11^17 2 3.5 2^5 7 2.3^8 . 2^2.5 3 2 .
11 2 3 2^2 5 2.3^2 7 2^3 3 2.5^8 . 2^2.3.11^2 . 2.7^8 3^2.5
. 2 3 2^2 5 2.3^2 7^3 2^3 3 2.5 11^5 2^2.3 . 2.7 3^8.5
367 coul(36, 15): recurse 21360, walk 279600, walkc 22 (9.45s)

The number and list of patterns varies with each run, but on average remains about the same - that is, there are always a few patterns without a number that are not identical to any patterns with a number.
This is observed on the last version as well as on the previous one. I didn't check older ones.

Sorry, I don't know what findstr does, are you filtering out the "203" lines and leaving the rest? If so, you are still getting normal progress display every second, and the progress display is always kept on a line of its own when any other result is displayed.

With latest code you can use option "-Ls0" to disable the progress logs to screen, and I think I also changed it to write the "203" lines to the log file if you specified one.

[EUgeneUS]

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

It seems likely that a better-targeted approach is needed: for other tasks, I have had some success searching for likelier patterns and running them manually. I've been trying to think of a useful way to make that easier, and welcome any ideas;

Ideas are:
1. After placing all the squares of the primes, we (for 12 divisors) will get either $p$ or $pq$. The larger the number $pq$ and the smaller number $p$, the more likely it is to find a chain.
2. The smallest number $p$ after squaring primes for D(12,14) is $10$. And it is achieved only in 78 patterns.

(Here is their list)

b319:
b323:
b324:
b325:
b327:
b328:
b348:
b351:
b354:
b355:
b357:
b358:
b359:
b362:
b365:
b366:
b368:
b369:
b370:
b373:
b376:
b377:
b379:
b380:
b417:
b421:
b424:
b425:
b426:
b428:
b432:
b434:
b435:
b436:
b457:
b461:
b462:
b465:
b466:
b1682:
b1683:
b1684:
b1687:
b1689:
b1693:
b1694:
b1695:
b1697:
b1699:
b1722:
b1723:
b1724:
b1725:
b1729:
b1818:
b1819:
b1821:
b1822:
b1823:
b1826:
b1830:
b1831:
b1833:
b1834:
b1835:
b1838:
b1842:
b1843:
b1845:
b1846:
b1847:
b1850:
b1853:
b1854:
b1856:
b1857:
b1858:
b1860:

3. Therefore, we need to look for a chain close to the minimum in these patterns.
4. Limits for primes up to 120 and an upper bound up to $U/10^3$ look overly optimistic.
5. IMHO, more relevant would be -p1000 and upper bound $U/10^2$
6. I ran a trial calculation of the b319 pattern with the keys -p1e3 -x1e31 (which corresponds approximately $U/(2 \cdot 10^2)$.

[Huz]

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

Huh, not sure; I don't see an immediately obvious bug, will look into it.

I was looking in the wrong place - everything that touches "maxp" assumes it is 64 bits, but it was actually being stored in 32 bits (same for minimum prime and "-W" threshold).

I'll try to get a new Windows build soon with the fix.

[EUgeneUS]

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

Sorry, I don't know what findstr does, are you filtering out the "203" lines and leaving the rest? If so, you are still getting normal progress display every second, and the progress display is always kept on a line of its own when any other result is displayed.

I received this output from Dmitry (before findstr processing). And I can say that there really are some snippets of lines. Perhaps there are some problems with stdout in Windows

[Huz]

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

Limits for primes up to 120 and an upper bound up to $U/10^3$ look overly optimistic.

Well, I was just targetting what I thought could be checked in a reasonable time. I also had a run to $U/10^4$ with -p200, which I've given up on for now.

-- 20.12.2022, 15:50 --

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

Perhaps there are some problems with stdout in Windows

See my response above, this is expected output.