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

[Dmitriy40]

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

Ещё придумал как исправлять остаток $d$ в случае если он оказался отрицательным:

Да добавить к нему число делящееся на модуль и всё: d=(d+m)%m (а для надёжности взять число побольше, например m^3).

-- 12.12.2022, 15:43 --

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

В Пари ведь нету трёхмерных массивов.

При сильной нужде их можно организовать или как матрицу векторов или как вектор матриц.
Но вообще говоря не очень понятно зачем они, вроде бы достаточно иметь вектор длиной 11 векторов возможных коэффициентов для каждого места паттерна, а остатки не запоминать, а лишь проверять что есть хоть один допустимый для каждого коэффициента на каждом месте паттерна.
И в показанном коде вроде бы удобнее не матрицы фиксированного размера, а именно вектор векторов, ведь Вы же в циклах именно вектор получаете и потом кладёте его в матрицу, проще оставлять его именно вектором и класть как элемент в вектор длины 11.

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

[Yadryara]

Dmitriy40, Благодарю.

Вроде бы проверка по модулям наконец-то завершена. Проверены модули 64, 3, 5, 7, 9, 11, 25, 49, 121, 343, 1331, 16807, 161051.

А какие ещё проверять? Похоже, уже никакие не надо. 3 и 5 проверял на всякий случай.

Итоги:

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

Я пока разделил 2471 паттерн Hugo так:

1044 — основные;
99 — БКП(под Быстрый Квадратичный Перебор);
68 — с кубоквадратами;
1260 — лишние.

По моей версии:

1044 — основные;
45 — БКП;
66 — с кубоквадратами.

(45)

1       1   50   3   28   1   18   55   32   3   2   7
2       1   50   3   4   77   18   5   32   3   2   1
3       1   50   3   28   1   18   55   32   3   2   49
4       1   50   3   28   1   18   55   32   3   2   16807
5       9   10   11   12   1   14   15   32   1   18   1
6       9   10   121   12   1   14   15   32   1   18   1
7       9   10   161051   12   1   14   15   32   1   18   1
8       9   10   11   12   1   98   15   32   1   18   1
9       9   10   121   12   1   98   15   32   1   18   1
10       9   10   161051   12   1   98   15   32   1   18   1
11       10   11   12   1   14   15   32   1   18   1   20
12       10   121   12   1   14   15   32   1   18   1   20
13       10   161051   12   1   14   15   32   1   18   1   20
14       10   11   12   1   98   15   32   1   18   1   20
15       10   121   12   1   98   15   32   1   18   1   20
16       10   161051   12   1   98   15   32   1   18   1   20
17       11   12   1   14   15   32   1   18   1   20   21
18       121   12   1   14   15   32   1   18   1   20   21
19       161051   12   1   14   15   32   1   18   1   20   21
20       1   12   11   14   75   32   1   18   1   20   21
21       11   12   1   14   75   32   1   18   1   20   21
22       1   12   121   14   75   32   1   18   1   20   21
23       121   12   1   14   75   32   1   18   1   20   21
24       1   12   161051   14   75   32   1   18   1   20   21
25       161051   12   1   14   75   32   1   18   1   20   21
26       12   1   14   15   32   1   18   1   20   21   22
27       12   1   14   15   32   1   18   1   20   21   242
28       12   1   14   75   32   1   18   1   20   21   22
29       12   11   14   75   32   1   18   1   20   21   2
30       12   1   14   75   32   1   18   1   20   21   242
31       12   121   14   75   32   1   18   1   20   21   2
32       12   161051   14   75   32   1   18   1   20   21   2
33       12   7   50   3   32   1   18   5   28   3   22
34       12   49   50   3   32   1   18   5   28   3   22
35       12   16807   50   3   32   1   18   5   28   3   22
36       1   14   15   32   1   18   1   20   21   22   1
37       1   14   15   32   1   18   1   20   21   242   1
38       1   14   75   32   1   18   1   20   21   22   1
39       11   14   75   32   1   18   1   20   21   2   1
40       1   14   75   32   1   18   1   20   21   242   1
41       121   14   75   32   1   18   1   20   21   2   1
42       161051   14   75   32   1   18   1   20   21   2   1
43       7   50   3   32   1   18   5   28   3   22   1
44       49   50   3   32   1   18   5   28   3   22   1
45       16807   50   3   32   1   18   5   28   3   22   1

(66)

1       1   2   3   4   5   18   7   32   3   50   1331
2       1   2   3   4   5   18   49   32   3   50   1331
3       1   2   3   4   5   18   16807   32   3   50   1331
4       1   2   3   4   5   18   343   32   3   50   11
5       11   2   3   4   5   18   343   32   3   50   1
6       1   2   3   4   5   18   343   32   3   50   121
7       1   2   3   4   605   18   343   32   3   50   1
8       121   2   3   4   5   18   343   32   3   50   1
9       1   2   3   4   5   18   343   32   3   50   161051
10       161051   2   3   4   5   18   343   32   3   50   1
11       1   2   3   4   5   18   343   32   3   50   1331
12       1   2   3   20   1   18   343   32   75   2   11
13       1   2   3   20   11   18   343   32   75   2   1
14       11   2   3   20   1   18   343   32   75   2   1
15       1   2   3   20   1   18   343   32   75   2   121
16       1   2   3   20   1   18   343   32   75   242   1
17       1   2   3   20   121   18   343   32   75   2   1
18       121   2   3   20   1   18   343   32   75   2   1
19       1   2   3   20   1   18   343   32   75   2   161051
20       1   2   3   20   161051   18   343   32   75   2   1
21       161051   2   3   20   1   18   343   32   75   2   1
22       1   50   3   4   1   18   245   32   3   2   1331
23       9   10   1331   12   1   14   15   32   1   18   1
24       9   10   1331   12   1   98   15   32   1   18   1
25       10   1331   12   1   14   15   32   1   18   1   20
26       10   1331   12   1   98   15   32   1   18   1   20
27       2   3   4   5   18   7   32   3   50   1331   12
28       2   3   4   5   18   49   32   3   50   1331   12
29       2   3   4   5   18   16807   32   3   50   1331   12
30       2   3   4   5   18   343   32   3   50   11   12
31       2   3   4   5   18   343   32   3   50   121   12
32       2   3   4   605   18   343   32   3   50   1   12
33       2   3   4   5   18   343   32   3   50   161051   12
34       2   3   4   5   18   343   32   3   50   1331   12
35       2   3   20   1   18   343   32   75   2   11   12
36       2   3   20   11   18   343   32   75   2   1   12
37       2   3   20   1   18   343   32   75   2   121   12
38       2   3   20   1   18   343   32   75   242   1   12
39       2   3   20   121   18   343   32   75   2   1   12
40       2   3   20   1   18   343   32   75   2   161051   12
41       2   3   20   161051   18   343   32   75   2   1   12
42       1331   12   1   14   15   32   1   18   1   20   21
43       1331   12   1   14   75   32   1   18   1   20   21
44       1331   12   1   2   75   32   7   18   1   20   3
45       1331   12   1   2   75   32   49   18   1   20   3
46       1331   12   1   2   75   32   16807   18   1   20   3
47       3   4   5   18   7   32   3   50   1331   12   1
48       3   4   5   18   1   32   147   50   1331   12   1
49       3   4   5   18   49   32   3   50   1331   12   1
50       3   4   5   18   16807   32   3   50   1331   12   1
51       3   4   5   18   343   32   3   50   11   12   1
52       3   4   5   18   343   32   3   50   121   12   1
53       3   4   605   18   343   32   3   50   1   12   1
54       3   4   5   18   343   32   3   50   161051   12   1
55       3   4   5   18   343   32   3   50   1331   12   1
56       3   20   1   18   343   32   75   2   11   12   1
57       3   20   11   18   343   32   75   2   1   12   1
58       3   20   1   18   343   32   75   2   121   12   1
59       3   20   1   18   343   32   75   242   1   12   1
60       3   20   121   18   343   32   75   2   1   12   1
61       3   20   1   18   343   32   75   2   161051   12   1
62       3   20   161051   18   343   32   75   2   1   12   1
63       4   5   18   7   32   3   50   1331   12   1   98
64       4   5   18   1   32   147   50   1331   12   1   2
65       5   18   7   32   3   50   1331   12   1   98   45
66       5   18   1   32   147   50   1331   12   1   2   45

Прогу пока не привожу, ибо она весьма непричёсанная(380 строк).

[Yadryara]

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

1044 — основные;
45 — БКП;
66 — с кубоквадратами.

Кстати, разделение паттернов на БКП и с кубоквадратами довольно-таки необязательное. Модернизировал прогу, чтоб выдавала сразу все 111 паттернов с квадратами.

Ну и повозившись, сделал прогу, выдавшую сразу все 1155 паттернов.

И вот теперь уже буду тщательно сравнивать эти паттерны и 1211 паттернов Hugo.

На всякий случай. Прога, разумеется, делалась не только для 11-к, но и с прицелом на более длинные цепочки вплоть до 15-к.

[Yadryara]

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

Проверены модули 64, 3, 5, 7, 9, 11, 25, 49, 121, 343, 1331, 16807, 161051.

А какие ещё проверять?

Вообще-то отсутствие 243 и 3125 должно было броситься в глаза. Добавил 243 к перебору и на всякий случай даже 3125. Добавил проверку по модулю 243.

Теперь уже нашлись $1044+51+68 = 1163$ паттерна. 68 паттернов с кубоквадратами вроде бы те же самые, что и у Hugo. Биекцию пока не делал.

[Yadryara]

Hugo,

I found a ban on your pattern:

b1904: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11 [sq=3]

In my notation:

      243   10   1   12   1   14   15   32   1   18   11

My program banned this pattern and I finally figured out why. Possible remainders after dividing $14p^2$ by $11$ are $0\; 1\; 3\; 4\; 5\; 9$.

And this pattern needs a remainder of $14p^2$ per $11$ should be $6$.

--------------------------------------------
Нашёл-таки запрет на Ваш паттерн:

b1904: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11 [sq=3]

В моей нотации:

      243   10   1   12   1   14   15   32   1   18   11

Моя прога запретила этот паттерн и я наконец разобрался почему. Возможные остатки от деления $14p^2$ на $11$ таковы: $0\; 1\; 3\; 4\; 5\; 9$.

А этог паттерн нуждается в остатке $6$.

[Dmitriy40]

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

Нашёл-таки запрет на Ваш паттерн

И что с того? Ну проверяет Хуго лишние паттерны, но это ведь не пропуски возможных решений, он и $8p^2$ проверяет.

И кстати остаток $14p^2=0\pmod{11}$ недопустим (точнее невозможен для простых $p>11$).

-- 13.12.2022, 18:23 --

А ещё очень забавно как при добавлении лишних проверок количество допустимых паттернов не уменьшается (или остаётся прежним) как должно бы, а увеличивается. Это или опечатка в подсчёте или явный признак ошибок в программе.

[Huz]

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

Hugo, I found a ban on your pattern:

b1904: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11 [sq=3]
[...]
this pattern needs a remainder of $14p^2$ per $11$ should be $6$.

Yes, my code only checks for valid quadratic residues with respect to the first square fixed (probably $10p^2$ in this case). When there are more fixed squares, it is fast enough just to let the Pell solver reject them, and avoid unnecessary extra complexity in the residue-checking code.

[Yadryara]

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

И что с того?

Что значит "что с того?" ?

Я тут о разном могу сказать. Навскидку:

По модулю 11 запрещены вот эти 12 паттернов Hugo:

(12)

b1889: 3^5 2.5 . 2^2.3 11^2 2.7^2 3.5 2^5 . 2.3^2 . [sq=2]
b1890: 3^5 2.5 . 2^2.3 11^5 2.7^2 3.5 2^5 . 2.3^2 . [sq=2]
b1891: 3^5 2.5 . 2^2.3 11 2.7^2 3.5 2^5 . 2.3^2 . [sq=2]
b1892: 3^5 2.5 . 2^2.3 . 2.7^2 3.5 2^5 . 2.3^2 11^2 [sq=2]
b1893: 3^5 2.5 . 2^2.3 . 2.7^2 3.5 2^5 . 2.3^2 11^5 [sq=2]
b1894: 3^5 2.5 . 2^2.3 . 2.7^2 3.5 2^5 . 2.3^2 11 [sq=2]

b1899: 3^5 2.5 . 2^2.3 11^2 2.7 3.5 2^5 . 2.3^2 . [sq=3]
b1900: 3^5 2.5 . 2^2.3 11^5 2.7 3.5 2^5 . 2.3^2 . [sq=3]
b1901: 3^5 2.5 . 2^2.3 11 2.7 3.5 2^5 . 2.3^2 . [sq=3]
b1902: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11^2 [sq=3]
b1903: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11^5 [sq=3]
b1904: 3^5 2.5 . 2^2.3 . 2.7 3.5 2^5 . 2.3^2 11 [sq=3]

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

И кстати остаток $14p^2=0\pmod{11}$ недопустим (точнее невозможен для простых $p>11$).

Ну мне для проги пока проще считать что он допустим. Так же как и ставить единичку на как бы пустые места.

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

А ещё очень забавно как при добавлении лишних проверок количество допустимых паттернов не уменьшается (или остаётся прежним) как должно бы, а увеличивается. Это или опечатка в подсчёте или явный признак ошибок в программе.

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

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

Yes, my code only checks for valid quadratic residues with respect to the first square fixed (probably $10p^2$ in this case). When there are more fixed squares, it is fast enough just to let the Pell solver reject them, and avoid unnecessary extra complexity in the residue-checking code.

It's clear. So I'm right that there are fewer legal patterns than your 1211.

[Dmitriy40]

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

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

Смотрим:

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

45 — БКП;
66 — с кубоквадратами.

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

Добавил проверку по модулю 243.
Теперь уже нашлись $1044+51+68 = 1163$ паттерна.

Добавил проверку по модулю 243 и количество изменилось с 45+66 до 51+68. Что вижу не так?

-- 13.12.2022, 20:55 --

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

Что значит "что с того?" ?

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

[Yadryara]

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

Смотрим:

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

45 — БКП;
66 — с кубоквадратами.

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

Добавил проверку по модулю 243.
Теперь уже нашлись $1044+51+68 = 1163$ паттерна.

Добавил проверку по модулю 243 и количество изменилось с 45+66 до 51+68. Что вижу не так?

Даже сейчас при цитировании меня выкинули одну важную строчку! Даже теперь не видите какую?

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

Вы же искали пропущенные у Хуго паттерны, а нашли пропущенные (запрещённые) у себя.

Я планировал

1. Построить по возможности независимую систему паттернов.

2. Если найдутся законные паттерны которых нет у Хьюго, предложить обсчитать их. Кстати один вроде нашёлся, завтра перепроверю.

3. Сообщить о результатах в любом случае и сверить их.

Вот, сообщаю и сверяю.


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

[Dmitriy40]

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

Даже сейчас при цитировании меня выкинули одну важную строчку! Даже теперь не видите какую?

Не вижу.

[Yadryara]

Вот же эти два предложения рядом стоят:

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

Добавил 243 к перебору и на всякий случай даже 3125. Добавил проверку по модулю 243.

Однако же первое Вы выкинули. Что у меня два предложения об одном и том же что ли?

"Добавил 243 к перебору". То есть добавил строчку

vstp3 =[0,...,0,0,1,9,1,1,3,1,1, 3,1,1,   243,1,1,3,1, 1,3, 1,1,9,1,  1,3,1,1,3,1];

Которую прога протаскивает справа налево таким образом, чтобы число 243 с нужным окружением оказалось на всех 11 местах для всех 5 расположений цепочки. Без этой цепочки поиск будет среди $5*20*38*40*44 = 6688000$ паттернов, а с ней — среди $5*31*38*40*44 = 10366400$ паттернов.

А проверять по модулю 243 паттерны, где нет ни единого числа кратного 243, не вижу смысла. Число паттернов от этого не изменится.

Так что увеличил перебор на 3 с лишним миллиона, добавил проверку, и добавились 8 паттернов с 243, которые прошли все проверки.

То есть увеличение количества паттернов, как раз ожидаемый результат. Старым паттернам эта доп. проверка была не страшна, а новые могли появиться.

[Dmitriy40]

Yadryara
Правильно ли я понял что эти вот лишние паттерны взялись из-за добавления (в частности) $3^5$?
Но ведь насколько я помню тройка в пятой может быть лишь на местах где есть тройка в квадрате, а там везде обязательно есть и ещё одно простое - т.е. никаких неизвестных простых там уже нет и эти паттерны имеют всего лишь ровно одно возможное значение величины чисел цепочки и проверяются прямо. Тогда какой смысл учитывать эти паттетны если их можно легко и быстро проверить сразу же? Ну ведь очевидно же что цепочек длиной 10+ нет ни до 1e6, ни до 1e9, ни до 1e12, это просто всё уже было давно проверено прямо, а все такие паттерны будут сильно меньше. Ну и зачем тогда их включать в списки? Если они не дают множества возможных решений, а всегда лишь максимум одно, да и то весьма небольшое и легко проверяемое.

-- 14.12.2022, 01:30 --

Я к тому что если цепочка с числом $2\cdot3^5$ точно не даёт решения длиной 10+ (что легко проверяется), то это эквивалентно запрету любых паттернов с $2\cdot3^5$ и совершенно незачем включать их в список возможных паттернов.

[Yadryara]

Dmitriy40,
попозже Вам отвечу, а пока продолжу подводить итоги.

Итак, мною найдено 1163 паттерна, у Hugo — 1211.

Разница — 48 штук. И как раз вот все эти 48 паттернов Hugo

b215-17, b220-22, b650-52, b1209-11, b1571-76, b1581-86,
b1820-25, b1830-35, b1889-94, b1899-904

запрещены по модулю 11. Пример такого запрета был показан выше. Все эти паттерны содержат пометку [sq=2] или [sq=3]. Что на жаргоне означает два или три квадрата. А точнее, это означает одновременное наличие в паттерне двух или трёх чисел из этого списка:

6, 10, 14, 15, 21, 22, 33, 35, 55, 77, 27, 125, 343, 1331

Даже при наличии нескольких таких чисел, Hugo проверял только одно. А моя прога проверяла все, даже если их было больше трёх.

В общем эти 48 паттернов можно было и не обсчитывать. То есть даже и не пытаться найти с их помошью 11-ку. Хотя все так называемые паттерны с квадратами обсчитываются весьма быстро.

Видимо, паттернов для 12-ки у меня тоже окажется меньше чем у Hugo.

Ещё надо проверить что 1163 моих паттерна полностью совпадают с оставшимися паттернами Hugo.

[Yadryara]

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

Ещё надо проверить что 1163 моих паттерна полностью совпадают с оставшимися паттернами Hugo.

Ну в общем сделал я наконец-то биекцию.

(PARI)

{print();h=vector(11);y=vector(11);
yad=vector(1163);hug=vector(1211);
m = read("1163m.txt");
hu = readstr("1211.txt");

for(i=1,1211,
s=strsplit(hu[i],":");
x=strsplit(s[3]," ");

for(j=2,12,
if(x[j]==".", h[j-1]=1,
ss=strjoin(strsplit(x[j],"."),"*");
h[j-1]=eval(ss));
);
hug[i]=h;
);
ksov=0;
for(i=1,1163,
print1(i,"      ");
for(j=1,11,
y[j]=m[i,j]);
yad[i]=y; 
print(yad[i]);
for(j=1,1211,
if(hug[j]==yad[i], ksov=ksov+1;
print(j,"   ",hug[j]);
print();next);
));
print();print(ksov);}
quit;

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

Да, у Hugo нашлись все мои паттерны до единого. Ничего у Hugo не пропущено, ну а про лишние уже говорил.

Congrats, Hugo!