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

[EUgeneUS]

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

За малыми тонкостями: есть паттерны без свободных мест, например b34 для D12n13, туда $p^2qr$ вообще не поставишь

Свободные места есть во всех паттернах без квадратов для 15-к (от 1 до 3 мест), для 14-к только 96 паттернов без "свободных" мест, для 13-к - 240 паттернов без "свободных мест" (и без квадратов, конечно).

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

не во всех паттернах обязано быть $25$, пятёрка может остаться и только в первой степени.

Для 13-к, 15-к и 14-к обязательно есть $25$ в паттернах без квадратов. Если это не так - можете ли привести контрпример? (не исключаю, что у меня здесь ошибка).

[Yadryara]

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

б) кратные $9$

Даже сильнее: кратные $18$.

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

а) $32$. $p^2$ "разрешает" 4 остатка из 16. То есть из всех $qr$ подходит только четверть.
б) $9$. Остатки $0$ и $3$ запрещены. Всего $7$ остатков, из них $p^2$ "разрешает" только три. То есть из всех $qr$ подходит только $3/7$ вариантов.

Проверил некоторые модули. Вроде лучше смотреть по модулям 64 и 18, чем по модулям 32 и 9 соответственно.

[Yadryara]

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

Ну то есть 190 паттернов таких пустых мест не содержат, а 44 паттерна имеют по 4 пустых места.

Ну вот этими 44-мя и заинтересовался. Взял 4 с самым маленьким для них шагом 554954400:

554954400   [1, 2, 3, 20, 1, 18, 637, 32, 75, 242, 1, 12, 1]
554954400   [1, 2, 363, 20, 1, 18, 637, 32, 75, 2, 1, 12, 1]

554954400   [1, 12, 1, 2, 75, 32, 637, 18, 1, 20, 363, 2, 1]
554954400   [1, 12, 1, 242, 75, 32, 637, 18, 1, 20, 3, 2, 1]

И запретил $323p^2$ на всех местах во всех 4-х паттернах.

В первых двух паттернах $323p^2$ может попытаться встать только на 35-е место, но запрет по модулю 13.

Во вторых двух паттернах $323p^2$ может попытаться встать только на 27-е место, но запрет по модулю 25.

Завтра попробую автоматизировать процесс проверки.

[Dmitriy40]

Немного ошибся в проверке по модулям (почему-то считалось что на 1 не делится ), потому список возможных qr оказался слишком урезанным.
После исправление ошибки допустимы оказались следующие 22<qr<200 (коих всего 52шт): 34, 93, 106, 118, 122, 123, 129, 159. При этом 34, 93 и 106 уже проверены до 6e26.
Паттернов стало 666 из 3408. Из них 637 только по одному варианту размещения одного qr и в 29 паттернов можно расставить два разных qr (на разные места, и одно из них всегда 93).

-- 17.01.2023, 22:03 --

Для 200<qr<600 получилось 2108 паттернов, в них расставляются до 5-ти из qr: 201, 218, 237, 253, 254, 262, 267, 301, 309, 323, 339, 341, 343, 355, 358, 362, 371, 394, 411, 453, 458, 469, 473, 489, 493, 497, 502, 514, 517, 519, 551, 566, 591, 597 (34 из 122 возможных). Что-то выигрыш уже слишком мал ...

qr=323 можно расставить в 158 паттернов, из которых с LCM=50450400 только следующие:
v=[1,12,13,50,3,32,539,18,5,4,3,2,1]; qr[1]=[[323,1]];
v=[1,12,11,50,3,32,637,18,5,4,3,2,1]; qr[3]=[[262,12],[323,1],[591,5]];
v=[1,2,3,20,1,18,539,32,75,2,1,12,13]; qr[1]=[[323,11]];
v=[1,2,3,20,13,18,539,32,75,2,1,12,1]; qr[1]=[[323,11]];

-- 17.01.2023, 22:16 --

Надо бы добавить проверку что все частные на всех местах будут иметь остаток 1 или 5, а не любой ... Интересно сильно ли это повлияет ...

-- 17.01.2023, 22:21 --

Для 600<qr<2400 от 3408 паттернов осталось 3396, фактически все. Но разных qr из 488 разрешены только 147:
611, 614, 629, 634, 669, 697, 698, 699, 703, 706, 737, 779, 793, 803, 813, 838, 842, 843, 849, 851, 879, 901, 921, 923, 926, 943, 951, 955, 974, 982, 1007, 1046, 1067, 1073, 1082, 1101, 1114, 1141, 1186, 1189, 1195, 1203, 1205, 1207, 1211, 1219, 1286, 1306, 1313, 1317, 1318, 1322, 1331, 1333, 1337, 1339, 1343, 1347, 1349, 1357, 1379, 1391, 1403, 1411, 1418, 1457, 1469, 1501, 1513, 1537, 1555, 1563, 1569, 1574, 1577, 1633, 1641, 1643, 1646, 1658, 1671, 1673, 1679, 1687, 1691, 1707, 1714, 1717, 1763, 1781, 1793, 1795, 1817, 1821, 1837, 1851, 1891, 1893, 1903, 1909, 1923, 1929, 1934, 1942, 1957, 1959, 1981, 2021, 2031, 2038, 2041, 2042, 2045, 2047, 2051, 2059, 2077, 2123, 2138, 2147, 2149, 2155, 2159, 2171, 2173, 2174, 2177, 2181, 2182, 2183, 2189, 2194, 2197, 2219, 2231, 2246, 2253, 2283, 2291, 2319, 2327, 2353, 2361, 2363, 2386, 2391, 2395.
Зато их бывает до 11 вариантов в паттерне (в том числе и на одном и том же месте разные qr) ...

-- 17.01.2023, 22:37 --

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

Надо бы добавить проверку что все частные на всех местах будут иметь остаток 1 или 5, а не любой ... Интересно сильно ли это повлияет ...

Добавил, запустил, разницы никакой. В принципе ожидаемо, ведь и 2 и 3 уже расставлены в паттерне и соответственно остатки по ним и так правильные.

[Yadryara]

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

Завтра попробую автоматизировать процесс проверки.

Получилось. Взял конкретный паттерн, 1-й из вчерашних 4-х:

554954400 [1, 2, 3, 20, 1, 18, 637, 32, 75, 242, 1, 12, 1]

Всего $663$ варианта $qr$ не превышают $10\;000$. Из них только $22 $ подходящих:

629    1189   1501   1513   2021
2363   2627   3349   3629   3683
3869   4661   5497   5723   6901
7061   7897   8257   9193   9469
9869   9913    

Смотрел по модулям: $64$, $637$, $18$, $75$ и $242$. Здорово. Больше 96% всех $qr$ отсеялись.

Так можно и другие паттерны проверить.

[Yadryara]

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

Так можно и другие паттерны проверить.

Проверил все 4 паттерна. $26$, $28$, $25$ подходящих куаров соответственно. Для последнего, 4-го паттерна, наименьший подходящий куар — $1411$.

[Dmitriy40]

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

Так можно и другие паттерны проверить.

Так я уже проверил.
Кстати рекомендую паттерн b1176, у него 13 вариантов qr<2400 (и 32 варианта qr<10000).

Хм, а вот для вашего паттерна у меня нашлись 28 вариантов qr<10000, давайте сверим почему у Вас недопустимы [339,3],[2762,2],[2858,2],[4778,2],[6891,3],[8259,3] (qr и место в паттерне), потому что у меня например qr=339 на 32p-5 вполне себе разрешёно по всем модулям:

? m=64;select(x->x==32,vector(m-1,i,(339*i^2-3+8)%m))
[32, 32, 32, 32]
? m=637;select(x->x==0,vector(m-1,i,(339*i^2-3+7)%m))
[0, 0, 0, 0]
? m=18;select(x->x==0,vector(m-1,i,(339*i^2-3+6)%m))
[0, 0, 0, 0, 0, 0]
? m=75;select(x->x==0,vector(m-1,i,(339*i^2-3+9)%m))
[0, 0, 0, 0, 0, 0]
? m=242;select(x->x==0,vector(m-1,i,(339*i^2-3+10)%m))
[0, 0]
? m=20;select(x->x==0,vector(m-1,i,(339*i^2-3+4)%m))
[0, 0, 0, 0]
? m=12;select(x->x==0,vector(m-1,i,(339*i^2-3+12)%m))
[0, 0, 0, 0, 0, 0]

По каким модулям qr=339 запретилось у Вас?
Да и количество 22<qr<10000 у меня не 663, а 2601 (до любых запретов).

А, думаю понял: Вы не стали брать qr с множителями <14 - ну и почему? Их ведь вполне себе тоже можно расставлять в паттерн на места с уже имеющимися простыми. Евгений их проигнорировал для простоты оценки своей идеи, это понятно, но оценка и реальное положение вещей дело таки разное.

-- 18.01.2023, 14:40 --

Кстати для вашего паттерна допустимы и кубические qr, целых 7 штук разных простых под кубом до 1e9: 7189057, 12008989, 86938307, 95443993, 97972181, 288804781, 833237621. Последнее правда даёт все решения выше 6e26, так что можно уже не учитывать.

[Yadryara]

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

А, думаю понял: Вы не стали брать qr с множителями <14 - ну и почему?

Да, конечно. Только простые, начиная с 17-ти. Я думал, это из контекста понятно. Заинтересовался именно пустыми местами.

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

По каким модулям qr=339 запретилось у Вас?

По той же причине: $339=3\cdot113$ ведь не может быть на пустом месте.

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

Для последнего, 4-го паттерна, наименьший подходящий куар — $1411$.

Ну, это лучший.

А на 27-м месте наименьший подходящий куар — $3131$. И всего 4 подходящих из 663-х для этого места. То есть отсеивается 99% всех куаров до 10 тысяч.

[Dmitriy40]

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

Да, конечно. Только простые, начиная с 17-ти. Я думал, это из контекста понятно. Заинтересовался именно пустыми местами.

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

[Yadryara]

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

А считать отдельно только подмножество таких qr непонятно зачем, это знание негде реально применить. Во всяком случае я не вижу такого применения, Вы видите (кроме чисто абстрактного интереса)?

Давайте разберёмся.

Вот есть паттерн 554954400-4-4:

[ 1, 12, 1, 242, 75, 32, 637, 18, 1, 20, 3, 2, 1]

Какое число будем ставить на 27-е место, то есть на пустое место с большой единичкой?

Если $p^2qr$, то какие $qr$ взять ? До 10 тысяч можно взять только 3131, 5891, 9731, 9899.

А если идти до 20 тысяч, то возможных кандидатов на 27-е место уже 12. Тогда лучше посмотреть на 39-е место, на которое всего лишь 9 кандидатов из 1493 вариантов куаров до 20 тысяч. 99.4% исключается. Этого мало?

Я так понимаю, что кубоквадраты и 5-е степени до 6е26 всё-ещё перебираются довольно быстро. Если чё, их ведь тоже можно по модулям проверять.

[Dmitriy40]

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

Давайте разберёмся.

Давайте. Только тогда уж подробно.

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

Вот есть паттерн 554954400-4-4:

Не знаю такого, номер по списку Хуго скажите.

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

Какое число будем ставить на 27-е место, то есть на пустое место с большой единичкой?

Это не 27-е место, это или первое место в паттерне, или 32p-5.

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

Этого мало?

Да, этого мало! Потому что для формирования ограничения -p для pcoul надо знать ограничения на простые по всем допустимым местам паттерна, а не только с единицами! Pcoul не умеет ограничивать простые только для пустых мест, там ограничение глобальное для всего паттерна. И именно оно и интересует на практике. Или Вы хотите предложить какой-то свой метод проверки паттернов, не с pcoul? Так поделитесь.
Снова повторю: нет никакого практического смысла ограничивать простые (для чего и проверяются qr) только для пустых мест, не ограничивая для остальных!
Потому мне не интересно какие qr можно ставить на пустые места, мне интересно какие qr вообще можно ставить в конкретный паттерн. Потому что только это позволит ограничить -p в pcoul и ускорить счёт. И я не вижу никакой принципиальной разницы ограничивать qr только на пустых местах или на всех. И не понимаю тогда смысла заниматься первым если можно сразу заниматься вторым, которое и нужно.

[EUgeneUS]

Новости по поиску меньшей 14-ки.

У меня и DemIS'а группа паттернов (78 штук) с 10 проверяемыми местами досчиталась до 7e31. Цепочек не найдено.
Сейчас усилия распределяются так:
1. DemIS считает эту же группу паттернов для следующего диапазона - 7e31-14e31.
2. У меня считаются некоторые группы паттернов с 11 проверяемыми местами "по низинам" (до 7e31).

Кстати, с 11 проверяемыми местами есть три группы паттернов с "низкими LCM":
1. $LCM=554954400$, 42 штуки
2. $LCM=655855200$, 52 штуки
3. $LCM=1030629600$, 48 штук

Для всех из них подставляются $p^2$ в семи местах.
ИМХО, наибольшие усилия потребуются для проверки этих групп паттернов. Но оставим их пока "на потом".

Все расчеты ведутся с ключом -p500.

[Yadryara]

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

Это не 27-е место, это или первое место в паттерне, или 32p-5.

Ну что, опять будем спорить об обозначениях??
Из 32p-5 выбрасываем p и получаем ровно 27. И это более короткое обозначение, 2 символа вместо 5.

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

Или Вы хотите предложить какой-то свой метод проверки паттернов, не с pcoul?

Разумеется, нужно проверять не с pcoul, а с помощью Вашей усовершенствованной проги Асм+Пари. Почему вдруг снова про pcoul заговорили?

[Dmitriy40]

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

Ну что, опять будем спорить об обозначениях??
Из 32p-5 выбрасываем p и получаем ровно 27. И это более короткое обозначение, 2 символа вместо 5.

Если Вам так трудно набрать лишние 3 символа - то да, будем спорить.
И между прочим "1" (номер позиции в паттерне) ещё короче чем "27".
А вот набрать коэффициенты паттерна вместо гораздо более короткого его номера у Хуго Вам почему-то не трудно. Мне же (и другим) приходится искать этот паттерн по его содержимому вместо короткого и понятного номера. Никакого уважения к другим ... ОК, я тоже буду указывать только минимум информации и в удобном для себя виде.

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

Разумеется, нужно проверять не с pcoul, а с помощью Вашей усовершенствованной проги Асм+Пари. Почему вдруг снова про pcoul заговорили?

Потому что pcoul уже есть и работает, а моей проги нет. Это первое.
Второе, даже когда она будет, то она тем более не будет использовать пустые места без крайней необходимости! Потому что мне выгоднее перебирать по занятым местам ради увеличения CP (что ускоряет ускорители ). К тому же это чуть проще, ведь пустых мест может и не быть, а места с простым есть всегда.
В третьих, вся эта бодяга с ограничением $qr$ и $p^2$ затеяна исключительно ради доказательств минимальности, для поиска любых решений это всё не нужно (или не очень нужно), там квадратичные переборы вовсе не обязательно запускать до самого конца, можно ограничиться первыми сотнями/тысячами.
В четвёртых, результаты работы моих программ Хуго так и не принимаются, так что никакого смысла их писать и нет. Хоть проверки паттернов, хоть уменьшения порога -p, хоть исключения qr. Для себя - да, когда интересно (как с КТО и обратным элементом в кольце по модулю).

В итоге речи про мою программу вообще не идёт. Речь идёт про ускорение работы pcoul! Не знаю почему Вы упорно это игнорируете.

[Dmitriy40]

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

никакого смысла их писать и нет. Хоть проверки паттернов,

Тут я несколько слукавил, именно проверки паттернов писать можно, ради поиска любых решений, а не доказательств минимальности.
Вот только кажется никаких реальных задач для таких программ фактически и нет: 13-ку и так докажем с pcoul (так или иначе ограничив -p ей), минимальность 14 и 15 пока выглядит неподъёмной (хоть с pcoul, хоть с ускорителями), искать меньшие 14 и 15 перспектив мало (а те что были уже более-менее проверены), с другими количествами делителей проблемы вовсе не в скорости линейного перебора (чтобы заменять его на квадратичные), а с квадратичными переборами проблем и без того выше крыши. Вот и выходит что применить то их особо и негде.