2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 168, 169, 170, 171, 172, 173, 174 ... 192  След.
 
 Re: Магические квадраты
Сообщение08.08.2014, 04:04 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak, Томск убрал. Проверил уже даже до 116 триллионов.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.08.2014, 20:00 
Аватара пользователя


20/01/10
766
Нижний Новгород
Алгоритм проверки возможности построения пандиагонального квадрата 5x5 из набора 25 чисел.

Будем проверять возможность построения примитивного квадрата из заданных чисел:
$\left[ {A_{i,j} } \right]$ , где $i = 0..4$, $j = 0..4$. Для примитивного квадрата выполняется условие:
$A_{i,j}  + A_{k,l}  = A_{i,l}  + A_{k,j} $
Без ограничения общности можно считать, что $A_{i,j}  < A_{i,k} $ при $j < k$, $A_{i,j}  < A_{k,j} $ при $i < k$ .
1. Сначала выбираем $A_{0,0}$ $=$ минимальное число набора и $A_{4,4}$ $=$ максимальное число набора.
2. Перебором находим $A_{0,4}$ и $A_{4,0}$
3. Аналогичным перебором последовательно находим пары $A_{0,i} ,A_{4,i}$ для $i=1..3$
4. Из оставшихся чисел набора выбираем минимальное число, это будет $A_{1,0}$
5. Далее вычисляются все числа второго ряда $A_{1,i}$
6. Повторяем п.4 и п.5 для вычисления чисел всех рядов $A_{2,i}$ и $A_{3,i}$

Если вычисляемые значения не находятся в исходном наборе, то производится откат в процедуре перебора.

Я вычислял количества наборов
$s_1$ - с тремя правильными рядами $0,1,4$
$s_2$ - с правильными рядами $0,1,2,4$
$s_3$ - все ряды правильные (возможен пандиагональный квадрат).

Например,
в диапазоне 200000000000..228500000285 получилось =146,0,0
в диапазоне 300000000000..326500000265 получилось =104,0,0
в диапазоне 400000000000..426300000265 получилось =85,0,0

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.08.2014, 21:23 
Модератор
Аватара пользователя


11/01/06
5660
svb в сообщении #896215 писал(а):
Алгоритм проверки возможности построения пандиагонального квадрата 5x5 из набора 25 чисел.

У меня делается быстрая предпроверка, которая отсеивает практически все кандидаты, а на оставшихся запускается неторопливое построение квадрата.

Предпроверка для набора $x_0=0 < x_1 < \dots < x_{24}$ такая:

Пусть $S =\{ x_1, x_2, \dots, x_{24} \}$.

Проверка 0
Сумма элементов $S$ должны быть кратна 5.

Построение "базиса" $T$
1. Полагаем $T\leftarrow S$.
2. Заводим счётчики $c_y$ для каждого $y \in T$, изначльно равные 0.
3. Для каждой пары элементов $y<z$ из $T$, проверяем $y + z\in S$ и если так, то увеличиваем оба счётчика $c_y$ и $c_z$ на 1.
4. Обновляем множество $T \leftarrow \{ y\in T\mid c_y\geq 4\}$. Если множество $T$ при этом уменьшилось, то снова переходим к шагу 2.

Проверка 1
5. Если $|T|<8$, то набор $S$ нам не подходит.
6. Пересечение $P=S\cap \{y+z\mid y\in T, z\in T, y\ne z\}$ должно содержать как минимум 16 различных элементов, причем среди них обязательно должны быть $x_{20}$, $x_{21}$, $x_{22}$, $x_{24}$. Если это не выполняется, то набор $S$ нам не подходит.
7. Проверяем, что $S=T\cup P$, иначе набор $S$ нам не подходит.


Эти проверки настолько "убийственные", что в интервале $[47\cdot 10^{12},235\cdot 10^{12}]$ им не удовлетворяет ни один набор из 25 последовательных простых чисел (при уменьшении на минимальный элемент, так как мы требуем $x_0=0$). А последний из прошедших проверку был такой:
Код:
46335098240069 0 18 30 42 60 78 104 122 168 182 198 200 210 212 224 228 240 272 288 290 302 332 380 410 500

А следующим должен быть магический квадрат :lol:

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.08.2014, 22:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
maxal
это важно, поэтому позволю себе привести здесь свой ответ на вашу реплику в ЛС, что "не в генераторе дело".

Цитата:
Не соглашусь.
Разумеется, скорость проверки наборов очень важна.
Но разве скорость генератора простых не имеет значения?

К примеру, генератор svb работает в разы медленнее генератора primesieve. Это означает только одно: его программа будет выполнять поиск очень медленно, даже если в неё вставить вашу быструю проверку наборов.

А вот если соединить очень быстрый генератор primesieve с вашей быстрой проверкой наборов, эффект будет колоссальный.

Много копий было сломано по этому вопросу на форуме ПЕН.
К сожалению, ни вы, ни svb в той теме не захотели принять участие, хотя я приглашала обоих.
Мы обсуждали проблему с участником темы Дмитрием. Так ни до чего и не договорились. Он согласен со мной в том, что скорость генератора имеет очень большое значение. Далее, он убеждён и в том, что скорость проверки наборов имеет не менее важное значение. Скорость проверки построения квадрата моей программой его не удовлетворила (я выложила эту программу на форуме). Поэтому он даже не стал начинать поиск пандиагонального квадрата 5-го порядка из последовательных простых.

В моей программе выполняется проверка построение примитивного квадрата 5х5 для каждого потенциального набора из 25 последовательных простых. Под потенциальным набором я имею в виду набор, удовлетворяющий необходимому условию: сумма чисел набора кратна 5. Проверка этого условия у меня выполняется прямо в программе. Если набор удовлетворяет этому необходимому условию, то он проверяется на предмет построения квадрата; если не удовлетворяет, проверка наборов идёт дальше.

Скорость работы генератора primesieve поразительная. Я его скачала и опробовала. Результаты экспериментов выложены в теме.
К сожалению, Дмитрий не смог разобраться в исходнике программы, чтобы вставить в неё нужный нам фрагмент для проверки построения квадрата.
Я тем более это сделать не могу, так как C++ вообще не знаю.

maxal
P.S. Я не сомневаюсь в том, что вы пользуетесь быстрым генератором простых. Но на всякий случай написала вам о генераторе primesieve.

-- Пт авг 15, 2014 00:01:13 --

О генераторе primesieve я узнала отсюда:

Droog_Andrey в сообщении #875189 писал(а):
Nataly-Mak в сообщении #842539 писал(а):
Итого в интервале [2, 200 000 000] 11078937 простых чисел.

Кстати, простые числа в указанном интервале программой svb генерируются за несколько секунд. Проверяется одна такая порция по моей программе 3-5 секунд.
Намного быстрее программа primesieve: http://primesieve.org/

Действительно, этот генератор работает намного быстрее генератора svb.

-- Пт авг 15, 2014 00:26:10 --

Цитата:
А следующим должен быть магический квадрат :lol:

Магический квадрат 5-го порядка из последовательных простых чисел известен давным-давно A073520 :lol:
А вот пандиагональный магический квадрат 5-го порядка из последовательных простых чисел по прогнозам Jarek и Jean K Andersen в XXI веке вряд ли будет найден.

Тут очень не помешал бы распределённый поиск. Однако я отчаялась собрать народ в группу, которая занялась бы таким поиском. Наверное, не обладаю для этого необходимыми способностями :-(

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.08.2014, 23:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Jens K Andersen в сообщении #845503 писал(а):
The smallest admissible width for a Stanley antimagic square with n=5 is 156 for these four patterns:
Код:
0  30  60  84 114
2  32  62  86 116
6  36  66  90 120
20 50  80 104 134
42 72 102 126 156

0   14  30  44  54
6   20  36  50  60
42  56  72  86  96
90  104 120 134 144
102 116 132 146 156

0  12  60  96 102
10 22  70 106 112
24 36  84 120 126
40 52 100 136 142
54 66 114 150 156

0  30 54  84 114
22 52 76 106 136
36 66 90 120 150
40 70 94 124 154
42 72 96 126 156

None of them have an occurrence below 10^20 and finding 25 simultaneous primes is infeasible. The largest known non-trivial prime k-tuplets are 19-tuplets found by Raanan Chermoni & Jaroslaw Wroblewski. 25 may be millions of times harder.

It also looks infeasible to find n=5 by generating consecutive primes and testing them. The jump in complexity from n=4 to n=5, i.e. from 16 to 25 primes, is just too hard.

В этом сообщении вы видите 4 шаблона для антимагического квадрата Стенли 5-го порядка (примитивного квадрата по Россеру).
Если я правильно поняла, в интервале [3,$10^{20}$] нет наборов из 25 последовательных простых чисел, удовлетворяющих этим шаблонам.
Разумеется, шаблонов можно насочинять ещё вагон и маленькую тележку. Однако... утешения мало: поиск по шаблону - бесперспективное занятие, так как конкретный шаблон слишком ограничивает шансы найти решение.

P.S. Прошу прощения, в предыдущем посте исказила ник Jens K Andersen; писала по памяти; правка в посте уже отключена.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение15.08.2014, 02:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
По поводу предпроверки, то есть проверки построения квадрата в два этапа...
Если кому-то интересно моё мнение, считаю, что проверять надо сразу - без предпроверок.
Единственная необходимая предпроверка - это проверка выполнения для набора из 25 последовательных простых необходимого условия: сумма всех чисел набора кратна 5.

Цитата:
Проверка 0
Сумма элементов должны быть кратна 5.

Все остальные предпроверки лишние. Их можно напридумать кучу.

svb в сообщении #896215 писал(а):
Я вычислял количества наборов
$s_1$ - с тремя правильными рядами $0,1,4$
$s_2$ - с правильными рядами $0,1,2,4$
$s_3$ - все ряды правильные (возможен пандиагональный квадрат).

maxal в сообщении #896257 писал(а):
Эти проверки настолько "убийственные", что в интервале $[47\cdot 10^{12},235\cdot 10^{12}]$ им не удовлетворяет ни один набор из 25 последовательных простых чисел (при уменьшение на минимальных элемент, так как мы требуем $x_0=0$).

Ещё пример

[может быть, он уже есть в приведённых тут проверках, я в них сильно не вникала; пример очевидный и сразу приходит в голову - не надо ничего изобретать]

Пусть утверждение А: из данных 25 чисел можно составить квадрат Стенли 3-го порядка;
утверждение B: из тех же самых данных 25 чисел можно составить квадрат Стенли 5-го порядка.

Очевидно, что из B -> A и из (не A) -> (не B).

(Извиняюсь, не знаю, как пишется здесь значок отрицания.)
Таким образом, достаточно проверить данный набор из 25 последовательных простых чисел на возможность построения квадрата Стенли 3-го порядка, что, естественно, выполнится намного быстрее, чем проверка построения квадрата Стенли 5-го порядка.

Ну и что? Нашли мы на первом этапе все потенциальные наборы. Сколько их будет? Много? Мало? И потом надо все эти потенциальные наборы проверять окончательно.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение15.08.2014, 03:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
maxal в сообщении #896257 писал(а):
А последний из прошедших проверку был такой:
Код:
46335098240069 0 18 30 42 60 78 104 122 168 182 198 200 210 212 224 228 240 272 288 290 302 332 380 410 500


Кстати, из чисел данного набора квадрат Стенли 3-го порядка составляется:

Код:
0  18  30 
182  200  212 
210  228  240

Следовательно, этот набор прошёл бы предложенную мной предпроверку.

Пандиагональный же квадрат 5-го порядка из чисел данного набора моя программа находит максимум такой:

Код:
0  410  0  272  60
0  122  42  198  0
240  0  380  0  104
0  0  302  0  168
0  210  18  212  0

S=1018

Все элементы, которые нули (кроме элемента $a_{11}$, который на самом деле равен 0), уже не могут быть найдены; перебор на этом заканчивается (поскольку в программе реализован "перебор с возвратом", всё работает чётко - перебор не пойдёт дальше, если следующий элемент квадрата не нашёлся).
Замечу, что программа ищет квадрат Стенли, но на выход выдаёт пандиагональный квадрат; преобразование Россера выполняется в программе.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение15.08.2014, 07:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Напомню: на сайте primepuzzles.net опубликованы две головоломки, связанные с построением пандиагонального квадрата 5-го порядка из последовательных простых чисел:

Пандиагональные квадраты из последовательных простых чисел
Квадраты Стенли из последовательных простых чисел
Кто найдёт решение, не забудьте, пожалуйста, отправить его Carlos Rivera (автору этого сайта).

Напомню далее (для тех, кто не в теме), что пандиагональные квадраты 4-го порядка из последовательных простых чисел найдены совсем недавно, первый нашёл Jarek, второй (минимальный) - maxal
Оба квадрата показаны в теме.

Наконец, напомню, удивительный парадокс: пандиагональный квадрат 6-го порядка из последовательных простых чисел найден давно, и составлен он из малюсеньких простых чисел (A073523).
36 последовательных простых чисел легко сложились в пандиагональный квадрат 6-го порядка!

Ну, о порядке $n=7$ пока не буду писать :D хотя пыталась решать и эту задачу.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение15.08.2014, 15:25 
Аватара пользователя


20/01/10
766
Нижний Новгород
maxal в сообщении #896257 писал(а):
Проверка 0
Сумма элементов $S$ должны быть кратна 5.
Эту проверку я забыл упомянуть. Времени не требует.
Цитата:
3. Для каждой пары элементов $y<z$ из $T$, проверяем $y + z\in S$ и если так, то увеличиваем оба счётчика $c_y$ и $c_z$ на 1.
Квадратичный характер проверки. П.2 и п.3 у меня также носят квадратичный характер проверки. Уже после п.2 идет значительное сужение пространства перебора, а после п.3 остаются единицы вариантов для дальнейшего рассмотрения.

Nataly-Mak приводит ссылку на программу primesieve и она права, скорость работы этой программы производит впечатление.

Я попробовал рассматривать для поиска простых решето на участке от $M,N$, где $A^2<M,N<(A+1)^2$. Составные числа на таких участках, уменьшенные на значение $A^2$ имеют вид $Aj-Ai-ij$. Получается, что важен прежде всего размер участка $N-M$. К сожалению, потерял все преимущества решета Эратосфена.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение16.08.2014, 10:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #896384 писал(а):
Ну, о порядке $n=7$ пока не буду писать :D хотя пыталась решать и эту задачу.

Начну, пожалуй, с магических квадратов 7-го порядка их последовательных простых.
Последовательности магических констант таких МК посвящена статья OEIS A188536.
Есть и соответствующая статья на моём сайте.

Тут возникает весьма интересная задача.
Статья в OEIS названа "Потенциальные магические константы...", хотя я задумывала её не для потенциальных магических констант, а для реальных, то есть таких, для которых магические квадраты мной уже построены.

Я сейчас не могу вспомнить, почему реальные магические константы в статье превратились в потенциальные (к моим 20 реальным магическим константам в статье OEIS добавлены ещё 18 потенциальных магических констант, для которых я реальные МК не строила).

Фишка вот в чём: для первых 20 потенциальных магических констант я МК построила, все они приведены в моей статье на сайте. Далее я привела в статье следующие 30 потенциальных массивов, которые дают следующие 30 потенциальных магических констант, и написала следующее:

Цитата:
Осталось доказать, что из любого массива, состоящего из 49 последовательных простых чисел и удовлетворяющего необходимому условию: сумма всех чисел массива кратна 7, магический квадрат 7-го порядка может быть составлен. Из первых 20 потенциальных массивов квадраты составились. Можно проверить следующие 30 потенциальных массивов, приведённые здесь. Однако для любого потенциального массива требуется доказательство. Мы не можем проверить экспериментально все потенциальные массивы, так как их бесконечно много.

Итак, вопрос весьма и весьма интересный:
из каждого ли потенциального массива, состящего из 49 последовательных простых чисел таких, что их сумма кратна 7, можно составить магический квадрат 7-го порядка :?:

В статье OEIS вставили аж две программки (в Maple и в Mathematica) для нахождения потенциальных магических констант таких МК.
Ну, находить потенциальные магические константы не проблема, по крайней мере, для не очень больших простых чисел. Проблема в составлении самого МК из потенциального массива простых чисел.

Если с обычными МК всё настолько замечательно, что из любого потенциального массива МК составляется (что вообще-то должно быть строго доказано :!: ), тогда переходим к пандиагональным квадратам :D

Очевидно, что потенциальные массивы для таких квадратов будут точно такие же, как и для обычных МК. Искать эти массивы проще пареной репы (пока простые числа не очень уж большие).
Что дальше? Дальше надо проверять каждый потенциальный массив на предмет составления из чисел этого массива пандиагонального квадрата. Вот тут есть два пути: один простой, второй сложный.
Простой - это поиск регулярного пандиагонального квадрата по Россеру. Проверка построения соответствующего регулярному пандиагональному примитивного квадрата (квадрата Стенли) 7-го порядка выполняется достаточно быстро.
Однако, если регулярный пандиагональный квадрат не найден, это ешё не значит, что пандиагонального квадрата не существует вовсе. Он может существовать и быть не регулярным. А вот найти не регулярный квадрат гораздо сложнее.

Несколько первых потенциальных массивов я проверила на предмет построения регулярного пандиагонального квадрата. Сколько - точно не помню, давно это было.

Интересен вопрос: насколько упрямым окажется пандиагональный квадрат 7-го порядка из последовательных простых :D

-- Сб авг 16, 2014 12:47:39 --

Просматривая рабочий файл, нашла поиск второго пандиагонального квадрата 6-го порядка из последовательных простых.
Как уже писала чуть выше, первый такой квадрат (минимальный) найден давно и составлен из чисел следующего массива простых чисел:

Код:
67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251

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

В рабочем файле у меня записано:
Цитата:
Последний проверенный массив даёт константу 67482. Квадрат не найден ни для одной константы.

Вот этот потенциальный массив:

Код:
11083  11087  11093  11113  11117  11119  11131  11149  11159  11161  11171  11173  11177  11197  11213  11239  11243  11251  11257  11261  11273  11279  11287  11299  11311  11317  11321  11329  11351  11353  11369  11383  11393  11399  11411  11423

Это было в 2012 г.
Вот так ведут себя пандиагональные квадраты из последовательных простых.

С квадратом 4-го порядка примерно такая же история. Первый (минимальный) квадрат найден maxal. Второй квадрат не найден в проверенном Дмитрием (на форуме ПЕН) интервале до $9 \cdot10^{14}$.
Вполне возможно, что вторым окажется квадрат, найденный Jarek, но до этих простых ещё проверять и проверять. Вряд ли это всё будет проверено в ближайшее десятилетие :D

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение16.08.2014, 12:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Нашла программу проверки построения квадрата Стенли 7-го порядка из заданных 49 чисел.
Первый же потенциальный массив из 49 последовательных простых даёт такой недостроенный квадрат Стенли:

Код:
13  31  41  53  67  101  0
19  37  47  59  73  107  0
43  61  71  83  97  131  0
109  127  137  149  163  197  0
139  157  167  179  193  227  0
211  229  239  0  0  0  0
0  0  0  0  0  0  0
S= 797

Ну и что же... элементов нашлось довольно много, квадрат построен на 2/3.
Сравните с аналогичным примером для пандиагонального квадрата 5-го порядка (из потенциального массива простых, приведённого maxal).
Так что, можно предположить, что пандиагональный квадрат 7-го порядка окажется менее капризным, чем квадрат 5-го порядка. Это не противоречит логике: с увеличением порядка квадрата шансы сложить все магические ряды возрастают.
Ничего не записала в рабочем файле - сколько потенциальных массивов проверила, но помнится, что совсем мало (штук 5 или 10). Ещё раз подчеркну: проверка пока только для регулярных пандиагональных квадратов.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение16.08.2014, 23:47 
Заблокирован
Аватара пользователя


22/03/08

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

Код:
7  17  31  41  127  167  0
19  29  43  53  139  179  0
37  47  61  71  157  197  0
73  83  97  107  193  233  0
79  89  103  113  199  239  0
163  173  0  0  0  0  0
0  0  0  0  0  0  0
S =  797

На один элемент меньше, чем в показанном выше примере.

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

А если б к утру умереть кто-нибудь организовал поиск не регулярного пандиагонального квадрата 7-го порядка из последовательных простых, я бы испекла для него пирог с капустой :D

Не исключено, что такой квадрат построится уже из первого потенциального массива с магической константой $S=797$.

Но как вспомню, сколько времени Jarek искал минимальный пандиагональный квадрат 7-го порядка из простых чисел (не последовательных), так вздрогну :-)

Вот он - шедевр, найденный Jarek:

Код:
3 7 173 223 17 197 113
181 211 11 79 131 23 97
43 41 149 89 137 191 83
233 103 107 73 127 31 59
29 167 101 19 199 67 151
5 47 139 179 109 61 193
239 157 53 71 13 163 37
S=733

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

Код:
3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  233  239

Почти последовательные простые!

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение17.08.2014, 04:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Тест

Это найденный мной наименьший регулярный пандиагональный квадрат 7-го порядка из простых чисел (не последовательных):

Код:
191 89 397 409 43 157 311
379 103 101 491 17 313 193
317 241 109 163 439 47 281
223 383 227 107 541 37 79
331 337 7 139 167 563 53
83 347 389 277 127 307 67
73 97 367 11 263 173 613

Решение предшествовало показанному в предыдущем посте наименьшему не регулярному пандиагональному квадрату 7-го порядка из простых чисел (не последовательных), найденному Jarek.

Начинаю проверку. Сгенерировала с помощью генератора svb массив простых в интервале
[$3; 2 \cdot10^6$] и вставила в этот массив набор из 49 простых чисел, из которых составлен регулярный пандиагональный квадрат:

Код:
148932  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83 
89  97  101  103  107  109  113  127  131 
137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233 
239  241  251  257  263  269  271  277 
281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397 
401  409  419  421  431  433  439  443 
449  457  461  463  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571 
577  587  593  599  601  607  613  617 
619  631  641  643  647  653  659  661  673  677  683  691  701  709  719  727  733  739  743 
751  757  761  769  773  787  797  809 
811  821  823  827  829  839  853  857  859  863  877  881  883  887  907  911  919  929  937 
941  947  953  967  971  977  983  991 
997  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091 
1093  1097  1103  1109  1117  1123  1129  1151 
1153  1163  1171  1181  1187  1193  1201  1213  1217  1223  1229  1231  1237  1249  1259 
1277  1279  1283  1289  1291  1297  1301  1303 
7  11  17  37  43  47  53  67  73  79  83  89  97  101  103  107  109  127  139  157  163  167 
173  191  193  223  227  241  263  277  281  307  311  313  317  331  337  347  367  379  383 
389  397  409  439  491  541  563  613
1307  1319  1321  1327  1361  1367  1373  1381  1399  1409  1423  1427  1429  1433  1439 
1447  1451  1453  1459  1471  1481  1483 ...
1999733  1999771  1999799  1999817  1999819  1999853  1999859  1999867  1999871 
1999889  1999891  1999957  1999969  1999979  1999993

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

Программа через пару секунд выдаёт квадрат Стенли 7-го порядка, соответствующий показанному регулярному квадрату:

Код:
7  11  17  37  67  191  241
43  47  53  73  103  227  277
79  83  89  109  139  263  313
97  101  107  127  157  281  331
163  167  173  193  223  347  397
307  311  317  337  367  491  541
379  383  389  409  439  563  613
S =  1597
KOLICHESTVO PROVERENNYH MASSIVOV D =  28

Тест программа прошла успешно. Вывелось и количество проверенных потенциальных массивов до найденного решения (дальше проверка не выполняется, программа работает до первого решения).

Убираю из массива вставленный набор из 49 чисел и снова запускаю программу. Проверяется весь массив из 148932 простых чисел, квадрат Стенли не найден.
Время проверки не засекла. В программе никогда не вывожу время проверки, даже и не помню функцию, которая это делает :-)

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение17.08.2014, 07:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Засекла время проверки. Приведённый выше массив из 148932 простых чисел проверялся 4 минуты; проверено 21279 потенциальных массивов. Вполне приемлемая скорость.
Но проверенный интервал-то всего длиной 2 миллиона.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение17.08.2014, 08:23 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ещё один эксперимент...

Проверяемый интервал [1999000,5000000].
По-прежнему использовала генератор svb; для таких небольших чисел этот генератор работает замечательно - секунда и готово!
Сгенерировано в указанном интервале 199646 простых чисел.
Запускаю программу проверки. Две минуты!
Протокол, выданный программой:

Код:
KOLICHESTVO CHISEL V MASSIVE M =  199647
KOLICHESTVO POTENCIALNYH MASSIVOV D =  28686

PJSLEDNIJ PROVERENNYJ MASSIV
4999363  4999387  4999391  4999409  4999427  4999439  4999447  4999453  4999457  4999469  4999493  4999507  4999523  4999529  4999537  4999559  4999591  4999597  4999613  4999627  4999633  4999637  4999639  4999651  4999661  4999667  4999681  4999693  4999703  4999727  4999733  4999759  4999769  4999781  4999783  4999801  4999823  4999849  4999867  4999871  4999879  4999889  4999913  4999933  4999949  4999957  4999961  4999963  4999999

Решение, конечно, не найдено.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 168, 169, 170, 171, 172, 173, 174 ... 192  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group