Pandiagonal magic squares of consecutive primes

Message boards : Science : Pandiagonal magic squares of consecutive primes
Message board moderation

To post messages, you must log in.

Previous · 1 · 2 · 3 · 4 · 5

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4807 - Posted: 9 Nov 2019, 6:05:58 UTC
Last modified: 9 Nov 2019, 6:25:15 UTC

Проверила до 2*10^9.
Если в программе нет ошибок, если не пропустила простые числа при ручной генерации, то квадратов Стенли 7-го порядка из последовательных простых чисел в этом интервале нет.
Три полные строки строятся из многих массивов.
Этот полуфабрикат уже за 2 миллиардами

2059536581+
0 20 68 146 170 182 398
240 260 308 386 410 422 638
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
660 680 728 806 830 842 1058

Массив из 49 последовательных простых чисел, который дал этот полуфабрикат
 2059536581 2059536601 2059536613 2059536617 2059536649 2059536653 
 2059536683 2059536727 2059536733 2059536737 2059536751 2059536763 
 2059536779 2059536811 2059536821 2059536841 2059536847 2059536889 
 2059536967 2059536971 2059536979 2059536989 2059536991 2059537003 
 2059537027 2059537079 2059537121 2059537127 2059537201 2059537219 
 2059537241 2059537261 2059537273 2059537309 2059537339 2059537343 
 2059537373 2059537387 2059537397 2059537409 2059537411 2059537423 
 2059537439 2059537481 2059537489 2059537499 2059537583 2059537637 
 2059537639

Да, найти квадрат Стенли 7-го порядка из последовательных простых чисел задача весьма сложная, на одном ПК её не решить.
Может быть, даже в BOINC-проекте придётся искать очень долго; как, например, в проекте yoyo@home ищут совершенный кубоид.
Ещё и неизвестно, существует ли этот кубоид в природе.
Ну, а про квадрат Стенли 7-го порядка из последовательных простых чисел нам что известно? Он существует или нет?
А дьявол его знает, его квадраты - он и должен знать :)
Мы знаем только то, что из произвольных простых чисел квадраты Стенли 7-го порядка существуют.
Но вот составить квадрат Стенли из 49 последовательных простых чисел... увы, не получается.

У нас пока и с порядком 5 всё глухо.
Хочу написать программу аналогичную программе для 7-го порядка. Для 5-го порядка проверяться будут массивы в разы быстрее.
Посмотреть хоть на приближённые решения, строятся ли 4 полные строки?
ID: 4807 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4808 - Posted: 9 Nov 2019, 6:18:39 UTC
Last modified: 9 Nov 2019, 6:20:15 UTC

Программу свою для квадратов Стенли 7-го порядка немного потестировала, хотя подводные камни вполне могут существовать.
Напомню, что у меня в программе только проверка готовых массивов простых чисел, генерация простых чисел выполняется вне программы.
Могу выложить программу, если кто-то горит желанием поискать :)
Но вам нужно иметь хороший генератор простых чисел типа primesieve.

Ушла писать программу для квадратов Стенли 5-го порядка.
ID: 4808 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4809 - Posted: 9 Nov 2019, 10:38:28 UTC
Last modified: 9 Nov 2019, 10:39:06 UTC

Программа для поиска квадрата Стенли 5-го порядка готова, можно искать :)
Поигралась с программой, 4 полные строки не строит (проверила до 680000000).
Программа работает быстро, ну, для моих массивов.
Массивы в интервале длиной 2 миллиарда, как в программе Белышева, я не проверяю.

Всё равно можно попробовать запустить поиск в BOINC.
Теперь есть исходный код!
А для программы Белышева у меня нет исходного кода.
Мою программу можно и оптимизировать по исходному коду.

Квадрат 5-го порядка маленький, шансов его найти побольше, чем для квадрата 7-го порядка (массивы-то почти в 2 раза отличаются).
Но нужна массовая проверка силами поболее одного ПК.
ID: 4809 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4811 - Posted: 10 Nov 2019, 3:19:18 UTC
Last modified: 10 Nov 2019, 3:28:42 UTC

Тестирую свою программу для поиска квадрата Стенли 5-го порядка.
Скормила ей 64 массива из пандиагональных квадратов Павловского (они показаны выше), все квадраты Стенли из этих массивов программа построила замечательно, вот несколько первых

 0  2  12  26  126 
 6  8  18  32  132 
 36  38  48  62  162 
 66  68  78  92  192 
 96  98  108  122  222 

 0  2  6  8  12  18  26  32  36  38  48  62  66  68  78  92  96  98  108  122  126  132  162  192  222 
S= 395 A(1)= 5 

 0  6  12  96  132 
 10  16  22  106  142 
 24  30  36  120  156 
 34  40  46  130  166 
 54  60  66  150  186 

 0  6  10  12  16  22  24  30  34  36  40  46  54  60  66  96  106  120  130  132  142  150  156  166  186 
S= 403 A(1)= 7 

 0  2  42  68  152 
 6  8  48  74  158 
 24  26  66  92  176 
 36  38  78  104  188 
 54  56  96  122  206 

 0  2  6  8  24  26  36  38  42  48  54  56  66  68  74  78  92  96  104  122  152  158  176  188  206 
S= 409 A(1)= 5 

 0  6  36  66  126 
 18  24  54  84  144 
 26  32  62  92  152 
 42  48  78  108  168 
 68  74  104  134  194 

 0  6  18  24  26  32  36  42  48  54  62  66  68  74  78  84  92  104  108  126  134  144  152  168  194 
S= 413 A(1)= 5 

 0  18  54  84  144 
 8  26  62  92  152 
 14  32  68  98  158 
 24  42  78  108  168 
 48  66  102  132  192 

 0  8  14  18  24  26  32  42  48  54  62  66  68  78  84  92  98  102  108  132  144  152  158  168  192 
S= 419 A(1)= 5 

 0  2  12  56  126 
 6  8  18  62  132 
 36  38  48  92  162 
 66  68  78  122  192 
 96  98  108  152  222 

 0  2  6  8  12  18  36  38  48  56  62  66  68  78  92  96  98  108  122  126  132  152  162  192  222 
S= 425 A(1)= 5 

После каждого квадрата выведен нормализованный массив, индекс квадрата Стенли S и первый элемент исходного массива A(1) (до нормализации).
Индекс квадрата Стенли S посчитан до нормализации массива.
Ошибок пока не обнаружила.
Существующие квадраты программа строит вообще очень быстро; я останавливаю в программе поиск при первом найденном квадрате (не делаю перебор до конца), мне не нужны все варианты квадратов Стенли из данного массива, достаточно одного варианта.
ID: 4811 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4812 - Posted: 10 Nov 2019, 3:25:57 UTC
Last modified: 10 Nov 2019, 3:26:46 UTC

Кстати, это получены готовые паттерны для квадратов Стенли 5-го порядка.
Только надо проверить их на повторяемость.
Где в Интернете проверялка паттернов на допустимость (по вычетам), кто знает?
Я забыла ссылку, но этот сервис точно был (пользовалась им очень часто, когда занималась кортежами), да и сейчас, наверное, есть.
ID: 4812 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4813 - Posted: 10 Nov 2019, 3:46:30 UTC
Last modified: 10 Nov 2019, 4:13:19 UTC

Ещё два массива протестировала, первый - это массив из статьи (о которой выше рассказано, в массиве присутствует число 1)

0 12 22 40 96
6 18 28 46 102
30 42 52 70 126
60 72 82 100 156
66 78 88 106 162

 0 6 12 18 22 28 30 40 42 46 52 60 66 70 72 78 82 88 96 100 102 106 126 156 162 
S= 337 A(1)= 1 

А это моё построение методом из статьи, только сделала замену числа 1

0 10 28 84 154
6 16 34 90 160
30 40 58 114 184
60 70 88 144 214
66 76 94 150 220

 0 6 10 16 28 30 34 40 58 60 66 70 76 84 88 90 94 114 144 150 154 160 184 214 220 
S= 503 A(1)= 13 

Оба квадрата Стенли программа построила.
Покажу иллюстрацию, чтобы было понятнее, о каких квадратах идёт речь




Сверху построение из статьи, внизу - моё построение, но здесь показаны пандиагональные квадраты. Квадраты Стенли, построенные программой, соответствуют этим пандиагональным квадратам..

У меня в рабочем файле полно пандиагональных квадратов 5-го порядка из произвольных простых чисел, давно их строила, продолжая список Павловского. Можно их тоже все протестировать.
Но пора уже подумать о поиске квадрата Стенли 5-го порядка из последовательных простых чисел.
Я давно думаю, да ничего придумать не могу.
Программы есть уже две, Белышева и моя.
Дело за конём :)
Коня мы искали очень давно :)
Напомню, Progger писал на dxdy.ru (это было задолго до всех наших BOINC-проектов, 2014 год!)
Сделал возможность распределённого поиска и запустил поиск квадратов Стенли 4х4 на 22 ядрах (клиент однопоточный, я запустил 22 экземпляра). За ~12 часов удалось проверить до 2,4*10^14. Первые числа найденных квадратов можно посмотреть тут.
Если там ничего не пропущено, то можно запустить для поиска квадратов 5х5, но я могу искать на таком количестве компов разве что по выходным. Может у кого если лишний суперкомпьютер или кластер?

https://dxdy.ru/post904931.html#p904931

Господа!
Нам нужен хороший конь :)
ID: 4813 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4814 - Posted: 10 Nov 2019, 4:31:32 UTC
Last modified: 10 Nov 2019, 5:36:55 UTC

И вот какая интересная история!

Минимальный aссоциативный квадрат Стенли 4-го порядка из последовательных простых чисел был найден Максом Алексеевым 30 июля 2014 г.
https://dxdy.ru/post891839.html#p891839
А в сентябре того же года Progger нашёл этот квадрат снова всего за ~12 часов!
(смотрите цитату из сообщения Progger выше).
При этом Progger искал все квадраты Стенли 4-го порядка из последовательных простых чисел, а не только ассоциативные.
Ну, разумеется, ассоциативные квадраты Стенли включаются во множество всех квадратов Стенли.
Покажу фрагмент из результатов Progger по квадратам Стенли 4-го порядка, он их выложил тогда, и я их, конечно, скачала, они у меня сохранились

. . . . . . 
160627944743797
160826476982861
161610082035763
164085618253229
165155673511909
167242195627093
167378129742623
167541053296651
169375985375981
170693941183817 (квадрат Алексеева)
173406001149833
173422250429287
174244726294207
176773622692567
177430719322639
178711892701207
179695339580693
180467105362717
184851350541763
186610628703259
187571464131451
190203353770333
. . . . . .

И это был поиск только на 22 компьютерах!
Супер!

Progger
это было здорово!
Надо повторить для квадрата Стенли 5-го порядка :)
Тем более что и программу поиска вы писали. Даже если она не сохранилась у вас, никакого труда не составит написать новую.
Алгоритм очень простой.
ID: 4814 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4815 - Posted: 10 Nov 2019, 7:06:26 UTC
Last modified: 10 Nov 2019, 7:10:14 UTC

Проверила до 1,5*10^9, нет ни одного квадрата с четырьмя полными строками.
Поискала без последнего элемента в третьей строке, такие есть, например

0 4 18 30 48
126 130 144 156 174
66 70 84 96 0
0 0 0 0 0
180 184 198 210 228

 0 4 18 24 30 48 58 66 70 84 88 96 126 130 136 144 150 156 174 178 180 184 198 210 228 
S= 431121 A(1)= 86113

Достраиваю квадрат вручную, получается решение с 5 "дырками" (неправильные элементы квадрата помечены символом *)

0 4 18 30 48
126 130 144 156 174
66 70 84 96 114*
84* 88 102* 114* 132*
180 184 198 210 228

Вот такой "дырявый" квадрат получился :)

PS. Программа строит квадрат так: сначала первую строку, затем последнюю строку, а потом строки 2, 3, 4 по порядку.
ID: 4815 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 14350
Credit: 0
RAC: 0
Message 4823 - Posted: 11 Nov 2019, 5:52:35 UTC
Last modified: 11 Nov 2019, 5:56:49 UTC

Проверила до 2*10^9, нет ни одного квадрата с четырьмя полными строками.
Нашла ещё "дырявое" решение, здесь уже 6 "дырок" (неправильные элементы квадрата помечены символом *)

0 24 54 114 180
40 64 94 154 220
96 120 150 210 276*
26* 50* 80* 140* 206*
84 108 138 198 264

0 24 30 40 54 64 84 88 94 96 106 108 114 120 136 138 150 154 180 184 198 210 220 234 264 
S= 2262734033 A(1)= 452546683 

Ну вот, на "дырки" насмотрелась :)
Теперь хочу видеть полный квадрат!
Буду сильно мечтать, авось мечта и сбудется.

Покажу формулу, связывающую индекс квадрата Стенли 5-го порядка из нормализованного массива (S1) с индексом квадрата Стенли из исходного массива (S):
S1 = S - 5*A(1)

В приведённом примере
S1 = 2262734033 -5*452546683 = 618

Индекс квадрата Стенли это сумма элементов в любой его диагонали (главных и разломанных).
Не путать с магической константой магического квадрата.
А если из квадрата Стенли построить пандиагональный квадрат, то магическая константа этого пандиагонального квадрата будет равна индексу квадрата Стенли.
Квадрат Стенли - антимагический квадрат.
ID: 4823 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Previous · 1 · 2 · 3 · 4 · 5

Message boards : Science : Pandiagonal magic squares of consecutive primes


©2024 (C) Progger