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

[Pavlovsky]

http://primes.utm.edu/lists/small/millions/
здесь можно взять первые 50 миллионов простых чисел. Числа помещены в 50 файлов по миллиону в каждом.
Соответсвенно представленны простые числа от 2 до 982,451,653.

-- Пн ноя 01, 2010 09:53:52 --

Еще есть вот такое безумие http://primegrid.com/orig/torrent.php
Все простые числа до 210.000.000.000.

Вот как скачать файлы на 24 гига и при этом не раззориться?!

[Nataly-Mak]

50 миллионов простых чисел? Это же очень много! Например, я сейчас генерировала новую порцию простых чисел от 1.318.700 до 1.500.000, получилось всего 12814 простых чисел.

Кстати, о моём генераторе. Забыла сказать об одном нюансе: нижняя граница интервала M должна быть не меньше 4. Первые два простых числа программа теряет.
И работает генератор не так уж и медленно, пока я завтрак готовила, новая порция сгенерирована.
Мне достаточно примерно 150.000 простых чисел.

[svb]

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

не подскажете?

#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
 LOCAL Q AS LONG
 LOCAL x AS EXT
 LOCAL y AS SINGLE
 LOCAL z AS CUR
 x=8/7
 y=8/7
 z=8/7
 PRINT x
 PRINT y
 PRINT z
 INPUT q
END FUNCTION
                         

[Nataly-Mak]

Спасибо, конечно, но это очень умная подсказка, мне такую не понять
Все три переменные x, y, z в программе принимают одно и то же значение 8/7, а задаются они по-разному.

Смутные воспоминания из далёкого-далёкого программистского прошлого, в котором было много разных языков программирования. Переменные объявлялись так: целая (что-то типа integer), действительная (что-то типа real). Только не надо смеяться, это было очень много лет назад, после этого было много лет полнейшего отупения, поэтому даже такие смутные воспоминания удивительно как сохранились.

Так, думаю... Значит, можно выбрать любой из трёх вариантов задания переменной? Сейчас попробую.

-- Пн ноя 01, 2010 16:41:27 --

Попробовала, задала переменную так:

LOCAL K AS EXT

Программа работает.
Спасибо.

[Nataly-Mak]

Продолжаю достраивать примитивный прямоугольник 13х12. В этом столбце уже только одно число не простое:

1541963  1542131  1542377  1546997  1548893  1549853  1553381  1558343  1575521  1701731  2034833  2164571  2384897

Сколько ещё предстоит попыток? Уже сгенерировала простые числа до 1.700.000. Надо продолжать генерацию.
Может быть, прямоугольник 13х10 проще достроить, ещё не пробовала его достраивать, кроме одной попытки, в которой получился столбец длины 11. Потом подумала, что один столбец проще достроить и занялась прямоугольником 13х12. Но увы, пока никак не получается.

Да-а-а-а, дьявольский квадрат 13-го порядка так просто не возьмёшь

[svb]

Забавное это решето Сундарама. Вот попробовал на basic-е

#COMPILE EXE
#DIM NONE

FUNCTION PRIME (m AS LONG,n AS LONG) AS LONG
REM Построение таблицы простых чисел
 LOCAL i,j,k,s AS LONG
 OPEN "prime.txt" FOR OUTPUT AS #1
 PRINT m;"...";n
 s=0
 IF m<3 THEN
   PRINT #1,2;:s=1:m=2
 END IF
 m=INT(m/2): n=INT((n-1)/2)
 DIM x(m TO n) AS LONG
 FOR i=1 TO INT(n/3)
   j=1+3*i: IF j<m THEN j=INT((m-i)/(2*i+1))*(2*i+1)+i
   DO WHILE j<m: j=j+2*i+1: LOOP
   DO WHILE j<=n: x(j)=1: j=j+2*i+1: LOOP
 NEXT i
 FOR k=m TO n
   IF x(k)=0 THEN s=s+1:PRINT #1,2*k+1;
 NEXT k
 PRINT #1:PRINT #1,"Number=";:PRINT #1,s:CLOSE #1
 PRINT "Number=";s
END FUNCTION

FUNCTION PBMAIN () AS LONG
 LOCAL M,N AS LONG
 INPUT "min=",M
 INPUT "max=",N
 IF M<N THEN prime(M,N)
 INPUT M
END FUNCTION

Пробовал $min=100000000$ и $max=110000000$. Получилось 541854 простых в файле prime.txt достаточно быстро.

[Nataly-Mak]

Вы, наверное, с новым компилятором пробовали, а я со старым всё время генерировала, а это раз в 20 медленнее. Генерировала порциями в интервалах длиной 200.000.
С новым компилятором ещё не генерировала, только попробовала для небольшого интервала, программа работает. Сейчас вот собираюсь генерировать следующую порцию.

[svb]

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

Или, может, ваша программа эффективнее моей?

Вывод чисел на экран, конечно, очень резко увеличивает время работы. Ну и еще кое-что. А в общем pb5 очень хороший компилятор, жаль нет документации на русском.

[Nataly-Mak]

svb в сообщении #369047 писал(а):

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

Или, может, ваша программа эффективнее моей?

Вывод чисел на экран, конечно, очень резко увеличивает время работы. Ну и еще кое-что. А в общем pb5 очень хороший компилятор, жаль нет документации на русском.

Вот насчёт "ещё кое-что", пожалуйста, подробнее
Хочу понять, что именно увеличивает время работы моей программы.
Почему такая резкая разница во времени выполнения вашей и моей программ? Компилятор тут ни при чём, он ведь один и тот же для обеих программ.
Значит, причина в чём-то другом. А именно: в реализации алгоритма.

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

-- Вт ноя 02, 2010 00:40:58 --

Не отвечает Ушёл спать.

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

Итак, оказалось, что мой генератор никуда не годится, выбросить его на свалку. А между тем, я им уже сгенерировала простые числа в интервале 1 - 1.700.000, причём со старым компилятором.

[Pavlovsky]

Продолжаю поиски пандиагонального МК 6х6 из чисел Смита вида 9k+4. Кстати, для магических костант, явно прослеживается арифметическая прогрессия с шагом 108, а не 54. Значит что то есть еще, что было не учтено ранее. Это тема для тех кто любит подумать, а не писать программы.

Pavlovsky в сообщении #351826 писал(а):

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

Любопытное наблюдение:
вот последовательность магических констант, для которых получены пандиагональные квадраты из смитов:

8340, 7260, 6720, 6612, 6504

Это члены арифметической прогрессии с разностью 108. Случайно ли?

Думаю, не случайно магические константы вида 54k + 24 получаются при составлении пандиагональных МК 6х6 из чисел смита вида 4mod9.

Все пока найденные МК 6х6 из чисел Смита составлены из чисел вида 4mod9! Тенденция однако!

Возникает еще один вопрос. Можно ли построить МК с магической константой меньше 5964 с использованием хотя бы одного числа не вида 9k+4? Мои прикидки говорят, что сделать это очень трудно. И есть большая вероятность, что сделать это невозможно.

Пища для размышлений. Для магической константы меньше 5964, максимальной возможным числом, которое можно использовать в квадрате является 3865. Вот статистика по классам вычетов 9 чисел Смита от 4 до 3865

0 30
1 1
2 1
3 4
4 76
6 32
8 6

[maxal]

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

Тут задача совсем простая: достроить всего один столбец. Но числа здесь уже почти до 2 миллионов присутствуют, а при достраивании будут ещё больше.

Следующий столбец начинается с простого числа: 175490449.
Если вдруг нужно еще одно - это 9681856013.

[Nataly-Mak]

О! Спасибо большое!

Я и предполагала, что это будет очень большое число, уже до 4 миллионов проверила и не нашла следующий столбец.
Уже опять вернулась к методу смешанного достраивания, получила одну матрицу, но результат - только квадрат 12х12.
Теперь, наконец-то, дьявольский квадрат 13-го порядка у нас есть из различных простых чисел. Магическая константа его, конечно, о-го-го.
В данной задаче четырнадцатый столбец не нужен, но вот можно попытаться достроить полученный примитивный квадрат 13х13 до примитивного квадрата 17х17. Это значит - надо достраивать не только столбцы, но и строки, по 4 штуки. Тут уже можно дойти до двадцатизначных простых чисел и даже больше

[Nataly-Mak]

Вот он - дьявольский квадрат 13-го порядка из простых чисел:

1154819 51203 13723 14621 175524007 556313 852143 5171 5857 860579 42859 165391 623717
843757 852857 31513 13513 17489 1314587 673397 6793 3617 175497379 74861 42767 497873
625811 175490449 63857 16139 16421 34381 1345559 869413 5791 6143 1162709 67169 166561
498493 844043 1154987 55823 14683 19583 175650217 686051 9209 5417 7753 864107 60037
168977 627611 823 853103 33409 17041 34667 1647689 893723 6961 8237 175498339 79823
84347 499663 846137 175490617 68477 17099 21383 160591 1475297 26479 6037 8039 1166237
869069 186247 628231 1109 1155233 57719 18211 36761 175983319 906377 9377 10037 8713
175501867 97001 502079 847937 991 857723 34369 22003 160877 1777427 50789 7207 10133
8999 1171199 210557 629401 3203 175490863 70373 20627 38561 493693 1695623 26647 10657
11933 12241 886247 519349 848557 1277 1159853 58679 23173 162971 176113057 63443 9623
11827 11093 175506829 223211 631817 5003 1237 859619 37897 39181 493979 1997753 50957
26893 12553 12527 1188377 543659 849727 3371 175495483 71333 25589 164771 623431 852689
63611 14243 12893 17203 1012457 649087 5623 1523 1161749 62207 40351 496073 176333383

Магическая константа квадрата равна 179870403.

Квадрат помогли построить EtCetera и maxal. Такой результат коллективного творчества получился.

Теперь предлагаю всем задачу минимизировать константу.

Я убедилась на примере построения примитивных квадратов 11х11 и 13х13 из простых чисел и примитивного квадрата 7х7 из смитов в том, что работают оба метода: "чистое" достраивание и смешанное достраивание. В случае примитивного квадрата 13х13 были использованы оба метода, сначала смешанное достраивание, которое дало примитивный прямоугольник 13х12, затем "чистое" достраивание тринадцатого столбца. Так же построен один из примитивных квадратов 7х7 из смитов. Но лучший результат для примитивного квадрата 7х7 (в смысле меньшей магической константы) получен методом смешанного достраивания. Предполагаю, что этим методом можно получить и примитивный квадрат 13х13 с меньшей константой. Мне кажется, что смешанное достраивание эффективнее "чистого" достраивания.

[Nataly-Mak]

По другому алгоритму Россера (построение по решётке) удалось построить пандиагональные квадраты 8-го и 12-го порядка из смитов.
Для построения использовала набор комплементарных пар смитов, найденный maxal’ем. Этот набор состоит из 556 комплементарных пар, он был выложен выше.
Подробное описание в статье.
Это пандиагональные квадраты 8-го и 12-го порядка из смитов:

391 778 677101 675058 498514 637474 184018 46714
958 2578 674914 663934 629194 412078 54958 281434
514597 657274 167935 26914 16474 20578 661018 655258
633694 490558 50458 202954 5458 81058 670414 585454
181498 42538 495994 633298 679621 679234 2911 4954
50818 267934 625054 398578 679054 677434 5098 16078
663538 659434 18994 24754 165415 22738 512077 653098
674554 598954 9598 94558 46318 189454 629554 477058

Магическая константа равна 2720048.

391 778 3694 677101 675058 659938 498514 637474 454873 184018 46714 241519
958 2578 4198 674914 663934 674194 629194 412078 405274 54958 281434 276358
8014 19678 26014 655618 650974 633838 402214 429214 409594 294178 260158 290578
514597 657274 521446 167935 26914 174946 16474 20578 70267 661018 655258 593365
633694 490558 459094 50458 202954 222538 5458 81058 58018 670414 585454 620374
519466 438934 457078 176926 250438 243094 125266 29398 73498 538366 641254 586354
181498 42538 225139 495994 633298 438493 679621 679234 676318 2911 4954 20074
50818 267934 274738 625054 398578 403654 679054 677434 675814 5098 16078 5818
277798 250798 270418 385834 419854 389434 671998 660334 653998 24394 29038 46174
663538 659434 609745 18994 24754 86647 165415 22738 158566 512077 653098 505066
674554 598954 621994 9598 94558 59638 46318 189454 220918 629554 477058 457474
554746 650614 606514 141646 38758 93658 160546 241078 222934 503086 429574 436918

Магическая константа равна 4080072.

Понятно, что о минимальности констант ничего нельзя сказать.

Задача для всех: построить пандиагональные квадраты 8-го и 12-го порядка из смитов с меньшими магическими константами.

Возник такой вопрос. Я строила пандиагональные квадраты 4-го порядка из указанного набора комплементарных пар следующим образом: построив один квадрат, удаляла из массива числа, вошедшие в этот квадрат, и строила второй квадрат. Так мне удалось построить 14 пандиагональных квадратов из различных чисел. Для построения пандиагонального квадрата 16-го порядка не хватило двух квадратов.
Вопрос: можно ли построить из указанного набора комплементарных пар больше 14 пандиагональных квадратов 4-го порядка, чтобы все они состояли из различных чисел
Надо бы 16 таких квадратов построить, тогда составится пандиагональный квадрат 16-го порядка.
_____

Пока не забыла. Составила первый тематический сборник статей “Квадраты Франклина”:
http://narod.ru/disk/27038932000/franklin.rar.html

В сборник вошли написанные мной статьи о квадратах Франклина, журнальный вариант статьи, полные комплекты квадратов Франклина порядков 4 – 16. Читайте предисловие к сборнику.

В дальнейших планах ещё два тематических сборника статей: “Латинские квадраты” и “Нетрадиционные магические квадраты”.

[Nataly-Mak]

Получила ещё один примитивный прямоугольник 13х12:

823 1109 3203 5003 5623 6793 9209 11399 177013 182653 233669 294773
1237 1523 3617 5417 6037 7207 9623 11813 177427 183067 234083 295187
1621 1907 4001 5801 6421 7591 10007 12197 177811 183451 234467 295571
5857 6143 8237 10037 10657 11827 14243 16433 182047 187687 238703 299807
7753 8039 10133 11933 12553 13723 16139 18329 183943 189583 240599 301703
8713 8999 11093 12893 13513 14683 17099 19289 184903 190543 241559 302663
12241 12527 14621 16421 17041 18211 20627 22817 188431 194071 245087 306191
13627 13913 16007 17807 18427 19597 22013 24203 189817 195457 246473 307577
17203 17489 19583 21383 22003 23173 25589 27779 193393 199033 250049 311153
127747 128033 130127 131927 132547 133717 136133 138323 303937 309577 360593 421697
427711 427997 430091 431891 432511 433681 436097 438287 603901 609541 660557 721661
598867 599153 601247 603047 603667 604837 607253 609443 775057 780697 831713 892817
740227 740513 742607 744407 745027 746197 748613 750803 916417 922057 973073 1034177

Попытала удачу, попробовала достроить 13-ый столбец с небольшими простыми числами. Проверила до 10 млн. Нет, не нашёлся столбец