Магические квадраты

[ice00]

maxal в сообщении #249796 писал(а):

ice00 в сообщении #249784 писал(а):

The header is recognize byMingw, but source did not compile (from error message it seems that unfortunately it uses 32 bit even for this type)

That's impossible. What exactly are the errors?

In file included from /home/ice/Scrivania/lin/Prime/cpp2/pms.cpp:35:
/home/ice/Scrivania/lin/Prime/cpp2/pms32.h:35: error: integer constant is too large for "long" type
make: *** [/home/ice/Scrivania/lin/Prime/cpp2/out/pms32] Error 1

this is row 35 of pms32.h:

const int64_t COMB=4294967296; // 2 at pow of order

[maxal]

ice00
You need to append 'll' or 'ull' suffix for any constant that doesn't fit 32 bits. E.g.:

const int64_t COMB=4294967296ll;

See http://gcc.gnu.org/onlinedocs/gcc/Long-Long.html

[Nataly-Mak]

ice00 в сообщении #249794 писал(а):

Цитата:

А что будем делать с квадратами порядков 3 - 9 из последовательных смитов? Вы здесь мне поможете? И для квадрата порядка 10 нужно уточнение ещё.

Maybe it needs other ideas for find a solution for this kind of orders

Придумаем эти идеи вместе?

У меня уже готов наименьший магический квадрат 17-го порядка из последовательных смитов. Квадрат построен из следующего массива смитов: $58, ..., 8073$. Магическая константа равна $66877$.
Я сделала файл для записи квадратов данной серии:
http://www.natalimak1.narod.ru/mk/minsmit.doc

[ice00]

maxal в сообщении #249816 писал(а):

ice00
You need to append 'll' or 'ull' suffix for any constant that doesn't fit 32 bits. E.g.:

const int64_t COMB=4294967296ll;

See http://gcc.gnu.org/onlinedocs/gcc/Long-Long.html

It works. Thanks.

[Nataly-Mak]

ice00, отчитываюсь
Я построила уже наименьшие магические квадраты из последовательных смитов до порядка 22 включительно (квадраты см. по указанной выше ссылке).
Мне осталось построить всего 9 квадратов, до порядка 31 включительно. А что будет для порядков больших 31? Для них нет исполняемых программ?
Я теперь хочу заняться последовательностями А073502 и А164843. Для этих последовательностей тоже, наверное, не будет проблем с построением квадратов до поряка 31.

[ice00]

Цитата:

А что будет для порядков больших 31?

Now I can make Windows executable over order 32, due to the last change suggest in the above post

[Бодигрим]

Я не следил за перипетиями темы некоторое время: что-то получилось с квадратом из (необязательно последовательных) чисел Смита 6-го порядка?

[Nataly-Mak]

Бодигрим, к сожалению, мои попытки построить наименьший магический квадрат 6-го порядка из смитов не увенчались успехом. У меня для магической константы 2787 строится очень много полумагических квадратов, даже, по-моему, с магической суммой в одной диагонали (сейчас уже не помню). Есть надежда, что для этой константы существует и магический квадрат (массивы у меня самые разные). Но насчёт минимальности этой константы ничего не могу сказать. И из последовательных смитов квадрат 6-го порядка не построен. Представьте, что для больших порядков (начиная с 11) такие квадраты строятся запросто, а вот для маленьких порядков никак! Я построила и квадрат 10-го порядка (из последовательных смитов), но не уверена, что он наименьший. Надо выяснять насчёт первого кандидата. Ну, а для порядков 3 - 9 вообще ничего!
ice00, я поняла так, что вы сделаете исполняемые программы и для порядков больше 31. Это здорово!

[Бодигрим]

Nataly-Mak в сообщении #249921 писал(а):

Представьте, что для больших порядков (начиная с 11) такие квадраты строятся запросто, а вот для маленьких порядков никак!

Это как раз естественно: чем больше порядок, тем больше степеней свободы и тем легче построить магический квадрат.

[Nataly-Mak]

Бодигрим в сообщении #249927 писал(а):

Это как раз естественно: чем больше порядок, тем больше степеней свободы и тем легче построить магический квадрат.

Да, ice00 сказал мне в личной переписке то же самое, когда я удивилась, почему он так легко построил квадрат 14-го порядка из последовательных смитов, а квадрат 6-го порядка и у него пока не получился.
Таким образом, мы имеем очень хорошие задачи:
1. построить наименьшие магические квадраты порядков 6, 7, 8, ... из произвольных смитов;
2. построить наименьшие магические квадраты из последовательных смитов порядков 3 - 9.
3. дать окончательный ответ для квадрата 10-го порядка из следующего массива последовательных смитов: $378, ..., 2839$ с магической константой $15681$. Существует или нет такой магический квадрат?
Я хочу проверить: возможно для больших порядков и первая задача будет решаться проще, чем для маленьких порядков. О результате проверки сообщу.
P. S. У меня сложилось впечатление, что магический квадрат большого порядка построить сложнее потому, что по моим программам это сложно выполнить технически; уже для порядков больше 15 мои программы не дают результаты за приемлемое время. Но как я теперь поняла, тут всё дело в языке программирования. Мне кажется, что и алгоритм построения у нас с ice00 похож, у него тоже всё начинается с генерации набора из n строк, так что сумма чисел в каждой строке равна магической константе квадрата, а потом он тоже "идёт на столбцы и диагонали". А генерация набора строк тоже выполняется с использованием функции случайных чисел. Так что, если переписать мои программы на компилируемый язык с хорошим быстродействием, они, возможно, тоже будут давать результаты и для больших порядков довольно быстро. К сожалению, я сама не умею это сделать, а помощников у меня нет.
Читатель, который вчера получил моё приложение со всеми магическими квадратами 4-го порядка, просит выложить код программы, по которой они построены. Просто он не программист, а вот изучением магических квадратов очень интересуется. Я ему сказала, что пишу программы на древнем языке; он ответил, что у него есть друзья программисты, и они перепишут программу на современный язык.
На этом форуме в теме "Программирование" была переписана на два современных языка моя программа генерации простых чисел. Говорят, что это неплохая программа. Я поместила оба кода в Википедию (статья "Простые числа"). Разумеется, эта программа не может генерировать простые числа для очень больших значений (для этого есть матпакеты), но для небольших значений она очень удобна. К тому же, в отличие от программы, приведённой ранее в Википедии, моя программа позволяет генерировать простые числа в любом заданном интервале, а не только с начала натурального ряда.

-- Чт окт 08, 2009 08:33:59 --

ice00

Я вчера построила по вашим программам магические квадраты из последовательных смитов до порядка 26 включительно. Сейчас стала переписывать результаты в файл и заметила такой недостаток: нкоторые числа в квадрате напечатаны без пробела, сливаются в одно два или даже три числа. Стала смотреть все квадраты, до порядка 19 такого явления не увидела. А вот квадрат 20-го порядка:

2934 666  8864 9634 2583 5088 690  2038 4960 7438 1581 5386 11388627  9396 7119 3864 107919657 7136 
3294 1921 1626 7834 5926 5422 8568 7674 5098 5526 1952 6835 107976880 9742 1858 5915 634  9166 5172 
8005 778  4054 1086 8077 3138 10462107058736 2944 3663 8372 9387 1449 2362 202  8680 8149 4126 7465 
1872 4832 3595 2745 8883 378  6385 7824 113587287 6760 5269 1908 2958 1255 7078 9296 106062785 8766 
10296110656603 729  2227 6981 8158 9355 4209 7051 4959 7062 2434 438  10489576  958  8095 9427 728  
5062 517  9778 3865 6188 4880 9294 8518 9717 2265 2067 3622 9684 3258 5539 8790 4557 2409 2484 9346 
2578 6252 4594 3390 109664702 762  913  8154 9571 7726 4794 4162 4981 9276 9975 1842 1881 8253 7068 
8196 105921165 8851 2576 5935 3168 2218 4306 7195 7249 6693 107368307 1795 2079 9760 636  648  9735 
9843 6531 2515 7089 2911 2605 4592 5854 3226 7809 7695 9840 5642 8914 5305 1903 6684 6718 1736 4428 
2839 9193 7764 104193694 9301 8792 105796259 526  9648 1822 1642 6457 4185 9483 483  3366 4743 645  
6036 8545 11209922  7683 6934 2751 8257 5602 5253 10494706  1284 5936 8277 3946 9414 5946 319  2326 
7762 7186 9708 7627 6054 1507 7978 4954 2155 346  6702 9184 1029110761654  3564 4414 2286 4855 3852 
852  6187 825  7952 5298 1776 9535 1755 274  9598 5388 8754 9015 108064974 5818 9285 2173 7402 4173 
2902 9522 8901 7447 4472 9382 2366 3246 4464 5458 2888 8023 2974 2475 6084 8421 4369 9274 5242 3930 
2461 3091 2970 382  6096 9094 9386 1678 9924 1111 166  7782 113858628 9968 1962 3690 4191 9861 8014 
102012722 3802 7026 2688 4189 4765 3345 4918 6115 9229 1894 6816 8653 1966 8466 9639 7712 7339 355  
6178 106982182 588  6315 6855 5998 7503 107866567 2679 562  454  6295 3442 6583 5071 8073 7227 7784 
115832964 6439 9895 9880 9031 6344 5638 1633 1282 9633 2614 391  1935 5248 9330 2965 9942 895  4198 
3174 663  9849 8874 3649 10669985  6171 2556 8412 1376 8347 535  9036 1219 6502 106892373 108875874 
5772 7915 5397 5485 5674 3973 861  3615 3505 100869985 4279 915  3046 106648185 265  6585 4788 10845

Посмотрите, например, на началр пятой строки. Там, по-моему, три числа слились в одно число. И таких соединившихся чисел очень много во всех следующих квадратах. Скажите, пожалуйста, почему так происходит? Это недостаток ваших программ или это у меня какие-то сбои при выводе результата в файл? Я попробовала вручную разделить слившиеся числа, но это очень трудно сделать.

-- Чт окт 08, 2009 09:49:56 --

Да!
Я начала проверку с наименьшего квадрата 15-го порядка из смитов. И сразу же всё получилось.
Массив смитов: $4, ..., 6171$, но заменить число 6115 на число 6188 и число 6171 на число 6187. Магическая константа равна $43968$.
Квадрат построися за 0,375 секунд.

4794 1449 382  627  5539 2576 3294 1736 1376 5874 5422 3226 3973 85   3615 
3138 2965 1921 6187 1903 2688 4855 5772 2484 2578 2409 1633 2614 2286 535  
2679 483  4198 2515 778  5642 3564 645  5638 1966 4126 4832 1219 729  4954 
4557 4185 5062 4918 3046 1776 2475 634  2218 5305 2227 825  166  2722 3852 
1165 346  1795 3663 3864 265  1111 4189 5854 2785 2839 4594 5098 3442 2958 
4428 5915 5946 94   1908 562  1822 2888 3690 1962 1507 3258 6096 958  2934 
391  4173 27   5248 1255 58   1282 5397 5926 3390 5386 690  2173 2970 5602 
922  2605 1642 319  1952 4464 6188 3946 5269 576  5242 2067 728  4880 3168 
4209 3366 5388 378  3802 2751 1284 913  3246 3174 3091 1678 202  5526 4960 
5253 4191 1755 5674 2461 4702 2366 6036 274  1881 985  4592 2556 588  654  
2079 4959 666  2373 706  6084 3595 4981 663  3622 1858 4369 2434 5458 121  
4765 648  5172 2902 4743 5935 4974 2265 861  4    2038 1935 4788 2583 355  
22   2964 5088 1086 5818 454  4306 517  1842 5936 5485 2944 852  2182 4472 
1872 2974 3345 4054 5298 3649 526  2155 762  4279 438  4414 5071 3505 1626 
3694 2745 1581 3930 895  2362 2326 1894 3865 636  915  2911 5998 6054 4162

С меньшей магической константой мне не удалось сформировать массив смитов (надо бы это проверить). Для сравнения: магическая константа квадрата 15-го порядка из последовательных смитов равна $50560$.
Теперь я пойду по убывающей, начну проверять квадраты 14, 13, ... порядков.

[ice00]

Цитата:

Посмотрите, например, на началр пятой строки. Там, по-моему, три числа слились в одно число. И таких соединившихся чисел очень много во всех следующих квадратах. Скажите, пожалуйста, почему так происходит? Это недостаток ваших программ или это у меня какие-то сбои при выводе результата в файл? Я попробовала вручную разделить слившиеся числа, но это очень трудно сделать.

This is because the number of spaces for output is hard-coded into the source and was based onto prime numbers.
For example 5 spaces was good for sequence of primes at order 20, but with Smith it is probably not good (need 6).
I know this, in fact this is a planned task (I want to code automatic spacing into next version of the program)

[Nataly-Mak]

Всё поняла. Значит, пока не надо строить квадраты больших порядков из смитов?
Сейчас построила ещё один наименьший квадрат из смитов - 14-го порядка. Минимально возможная константа для такого квдарата равна 35175. Мне удалось сформировать массив только для константы $35185$. Вот такой у меня получился квадрат:
ORDER=14 MAGIC=35185

202  2688 2902 663  4    2461 3615 729  5172 2038 4880 3930 5253 648  
2958 861  517  535  2944 4592 1822 3442 1633 4788 3564 3046 2265 2218 
3258 3345 2888 5386 3663 166  121  852  1642 3865 3595 2373 526  3505 
3852 922  3622 2286 4794 4185 958  3973 1255 4464 1795 1872 562  645  
4557 1952 346  4959 4702 22   4472 2515 728  1678 2614 2409 2605 1626 
634  483  2679 5305 4974 2970 2839 4832 1376 3649 1881 985  94   2484 
2227 5088 4209 3946 454  1165 3138 85   3294 2475 778  4198 3366 762  
666  4765 3802 913  1755 1449 4369 4981 2182 2556 1219 355  1894 4279 
5098 3690 1581 1284 2965 2434 274  627  1111 2578 3694 5269 4189 391  
1966 2067 3864 3174 2964 4414 1908 576  2722 27   2576 2326 2173 4428 
2583 915  2366 4954 438  4126 895  4054 4162 654  1935 4306 3091 706  
1842 2079 690  825  2155 1282 4173 2362 5071 265  3226 1776 4191 5248 
382  4594 2745 319  588  2751 1858 2911 1903 5062 1921 378  4918 4855 
4960 1736 2974 636  2785 3168 4743 3246 2934 1086 1507 1962 58   3390

Этот квадрат строился аж 33 секунды!
Для сравнения: магическая константа квадрата 14-го порядка из последовательных смитов равна $35936$.
Пошла строить наименьший квадрат 13-го порядка из смитов.
Бодигрим, вы тем временем идите от порядка 6 по возрастающей, где-нибудь мы с вами встретимся

-- Чт окт 08, 2009 14:28:29 --

Есть наименьший квадрат 13-го порядка из смитов!
Массив чисел: $4, ..., 4472$, но заменить число 4428 на число 4594. Магическая константа равна $27612$. Минимально возможная магическая константа - 27600, но у меня меньше 27612 не получается (не удаётся сформировать массив смитов). Вот квадрат:
ORDER=13 MAGIC=27612

2067 2366 588  2911 2970 2751 454  1642 2461 562  382  3864 4594 
3390 319  3694 1962 2182 2286 2038 1842 1165 2944 22   2173 3595 
265  915  1282 1858 2362 2409 2888 2475 346  4369 3930 2434 2079 
483  3505 706  2934 3345 58   4126 1894 3663 728  895  3649 1626 
202  690  2839 2964 3174 1507 2902 3690 3946 3091 1755 27   825  
985  3622 4414 1255 438  1376 627  2265 2326 2218 3366 535  4185 
4209 4198 2722 166  1086 958  4054 121  2688 2155 1872 778  2605 
4162 2556 4464 4173 1795 913  762  4    2745 1219 3564 729  526  
1736 2227 1284 1678 94   3046 517  2965 1908 3258 2515 3138 3246 
4189 355  391  2679 3865 3168 1881 654  576  3442 3852 1449 1111 
3226 2578 648  2484 1935 2373 1822 1952 1633 2974 852  4472 663  
1776 666  2614 1903 2785 4191 2583 4306 861  378  634  4279 636  
922  3615 1966 645  1581 2576 2958 3802 3294 274  3973 85   1921

Этот квадрат строился 204 секунды. Я уж хотела прерывать программу, думала, что не построится.
Для сравнения: магическая константа квадрата 13-го порядка из последовательных смитов равна $28301$.
Итак, между порядками 5 и 13 осталось всего 7 квадратов. Товарищи, помогайте же ещё кто-нибудь Программы теперь есть для всех. По готовым программам строить одно удовольствие
А в сторону бОльших порядков (>15), наверное, совсем хорошо дело пойдёт.

-- Чт окт 08, 2009 16:10:33 --

И наименьший квадрат 12-го порядка из смитов готов!
ORDER=12 MAGIC=21333 (минимально возможная константа 21330)

382  663  2173 1894 2751 1626 2227 2614 2373 1219 2745 666  
22   2964 3246 4    654  1633 2974 3138 2182 636  2038 1842 
861  2576 1507 2409 2067 202  3345 3390 729  2434 1755 58   
1449 3595 1282 2902 648  3168 1822 588  762  2475 1952 690  
3226 2578 3046 517  1086 922  1795 2679 391  346  2785 1962 
2944 1966 706  2958 3258 2556 2326 94   2839 355  1165 166  
728  1908 2461 2911 1284 2366 627  1903 1111 3564 535  1935 
3663 121  454  562  3442 2218 274  1376 1642 2155 1736 3690 
985  2965 2688 3091 645  1581 1921 27   2722 913  2970 825  
3505 895  319  958  378  1881 265  2888 2484 1776 2362 3622 
2934 576  3366 1255 2515 915  2079 778  483  2286 852  3294 
634  526  85   1872 2605 2265 1678 1858 3615 3174 438  2583

Эх, забыла записать (от радости), сколько строился этот квадрат, ну, примерно минут 40. Я успела приготовить обед и пообедать.
Для сравнения: магическая константа квадрата 12-го порядка из последовательных смитов равна 26062.
Осталось 6 квадратов!

[ice00]

Here the programs recompiled with the new automatic spaceing of square result:

http://www.4shared.com/file/138532176/647a87fa/pms4-10.html
http://www.4shared.com/file/138533403/e526403c/pms11-20.html
http://www.4shared.com/file/138534021/a3c0d3f7/pms21-30.html

[Nataly-Mak]

Всё! На наименьшем квадрате 11-го порядка из смитов я застряла. Квадрат не строится (я ждала программу ice00 40 минут). Попробовала по своей программе. Полумагических квадратов строится много. Существует ли магический - неизвестно. Данные у меня для этого квадрата получились такие: массив последовательных смитов: 4, ..., 2964, но заменить число 2944 на число 2970 и число 2964 на число 2974. Магическая константа $16335$ (минимально возможная магическая константа равна 16332).
В сторону бОльших порядков всё прекрасно. Наименьший квадрат 16-го порядка из смитов построился за 2 секунды.
ORDER=16 MAGIC=54013

5248 4472 2958 5935 5926 3138 2484 94   1894 648  2475 1219 1842 5772 4306 5602 
636  5062 2173 4189 6385 588  4198 1642 121  7051 4855 2970 6585 4173 2722 663  
6178 6084 3946 526  778  6187 1633 958  6344 5386 391  922  5485 2155 6188 852  
6981 202  1376 2227 6315 3174 6603 6115 166  825  319  1822 2745 6036 3865 5242 
355  6096 3649 4369 6693 1736 378  2409 5674 4414 1962 6259 2366 5305 382  1966 
6760 2888 265  6252 3852 1255 2373 2583 6718 728  6835 5422 1858 913  1921 3390 
645  1282 4557 3694 517  4162 2556 4880 2079 2614 6702 4960 1507 2944 5526 5388 
4209 576  4428 1881 895  4464 3345 7062 4702 5638 706  1086 562  3973 4191 6295 
1755 535  2434 3294 4279 6502 5253 4794 1776 2785 3690 5298 5936 22   2038 3622 
3663 2902 6934 4743 4959 1284 2362 1908 58   5098 3226 5642 5539 1626 454  3615 
5088 6567 4832 2911 1165 2578 5397 2751 3802 2974 861  1581 3091 6816 3595 4    
4765 654  1111 2265 729  2839 6457 5269 6054 4126 6439 27   4185 2576 6171 346  
3442 3564 5071 3864 4954 3258 1449 4788 2182 6583 2965 4918 915  438  2934 2688 
634  5818 2461 985  3246 2218 5874 6880 5998 666  1678 4594 1935 3366 2679 4981 
690  627  5915 4592 274  5172 3168 1795 3930 2605 4054 6531 7136 1952 2067 3505 
2964 6684 1903 2286 3046 5458 483  85   2515 1872 6855 762  2326 5946 4974 5854

Квадрат построен из массива последовательных смитов: 4, ..., 7062 с заменой числа 7026 на число 7136. Минимально возможная константа для такого квадрата равна 54007. Для меньших констант мне не удалось сформировать массив.
Для сравнения: магическая константа наименьшего квадрата из последовательных смитов равна $55330$.
ice00
как я поняла, вы перекомпилировали программы с целью изменения формата вывода результата. Спасибо!
Вам удалось построить магический квадрат порядка 11 из последовательных смитов. Долго строился этот квадрат? Хочу сориентироваться: сколько мне нужно ждать от программы результата в случае построения наименьшего магического квадрата порядка 11 из смитов? Может быть, больше, чем 40 минут?

[ice00]

Цитата:

Долго строился этот квадрат? Хочу сориентироваться: сколько мне нужно ждать от программы результата в случае построения наименьшего магического квадрата порядка 11 из смитов? Может быть, больше, чем 40 минут?

Statistically, if you don't get an result in short time (maybe some minutes) you will probably never get a result even if a square exists. The best way is to test with different methods for some minutes. The programs are built with algorithms that want to be fast: in other word, I did not make one square and use algorithm that make it magics applying all that it is possible to do that, but getting a square I apply fast methods for make all magic, but if in one point the methods seems to not be good, the square is rejected and another random one is pick up. If the space of solution is big, you have high probability to find a magic square in a tick, in opposite case, you did not find it..