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

[Nataly-Mak]

Ага, так значит, проблема в генерации смитов. Тогда надо решить эту проблему отдельно от квадратов, а уже потом проверять построение квадратов.
Ведь удалось же сгенерировать очень большие простые числа (думаю, что это сделано за реальное время). Так почему же нельзя сгенерировать очень большие смиты?

[maxal]

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

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

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

[Nataly-Mak]

Вы, кажется, меня не поняли. Если у меня есть массив смитов (всех подряд), например, до миллиарда, тогда я беру программу проверки на предмет составления квадрата 3х3 из каждого кандидата массива, состоящего из 9 смитов, и выполняю её. И никаких проблем! Как только у меня закончился массив смитов, дальше уже нечего проверять. А теперь у меня появляется следующий миллиард смитов, я снова быстренько проверяю его по своей программе, ведь этой программе абсолютно всё равно, из какого массива берутся числа (массив из 9 чисел), этот массив должен удовлетворять определённым условиям и программа проверяет далее этот массив на предмет укладывания чисел этого массива в магический квадрат 3х3.
Так я вижу проблему только в том, что у меня нет достаточно большого массива смитов. А если бы он у меня был, я бы смогла проверить всех кандидатов из этого массива.
Аналогично для квадрата 4х4. Вот я проверила 800 кандидатов, и массив смитов у меня закончился (он у меня всего в интервале от 1 до 100000). Дальше проверять не могу: нет смитов.

[tolstopuz]

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

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

В любом современном языке программирования для этого есть либо встроенные средства, либо библиотеки. Но проблема, как вам пытаются объяснить, в другом.

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

Опять же вот мне непонятно: как же люди находят, например, арифметические прогрессии из простых чисел в заоблачных пределах? Там числа состоят из сотен цифр.

Всего из 17. И прогрессий из 26 чисел, ради которой и начат проект, не нашли пока ни одной. Из 25 - всего несколько штук.

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

А теперь у меня появляется следующий миллиард смитов, я снова быстренько проверяю его по своей программе

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

Я проверял смиты до нескольких миллиардов решетом Эратосфена, поэтому смиты генерировались несколько минут, а вот прогрессии в них искались неделю.

[Nataly-Mak]

Не поняла, как это только из 17 цифр? Я, конечно, могу что-то не так понимать в этой таблице, но вот самое начало этой таблицы арифметических прогрессий из простых чисел:

k = 3  Digits 137514
k = 4 Digits 11961

Это разве не количество цифр указано?

Далее, мне пытаются объяснить, что дело не в больших числах. Но я, увы, это объяснение не понимаю. Если, скажем, у вас есть отрезок массива смитов, в котором содержится девятка смитов-близнецов, разве программа не построит из этих 9 чисел магический квадрат 3х3?
И программе ведь неважно, в каком месте этот отрезок находится, главное, что вы этот отрезок в своём массиве смитов имеете! А если вы его ещё не имеете, то есть не дошли до него, так дойдите - генерируйте смиты дальше, чтобы достичь этого промежутка массива, в котором находятся девять смитов-близнецов.

И кстати, речь сейчас идёт о построении магических квадратов порядков 3, 4 именно из последовательных смитов.

[tolstopuz]

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

k = 3  Digits 137514
k = 4 Digits 11961

Это разве не количество цифр указано?

Там числа очень специального вида, и последовательных простых чисел никто не считает, поэтому перебор не такой большой. А в поиске прогрессии из 26 чисел перебирают 17-значные.

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

так дойдите - генерируйте смиты дальше

Проверка на смитовость требует разложения на множители, что сложнее, чем проверка простоты.

[Nataly-Mak]

tolstopuz в сообщении #262932 писал(а):

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

k = 3  Digits 137514
k = 4 Digits 11961

Это разве не количество цифр указано?

Там числа очень специального вида, и последовательных простых чисел никто не считает, поэтому перебор не такой большой. А в поиске прогрессии из 26 чисел перебирают 17-значные.

Извините, но ещё больше туману в вашем ответе. Что значит, "числа очень специального вида"? Это прогрессии или не прогресси в таблице, из которой я взяла значения? И я не вела речь о прогрессии из 26 чисел, а вела речь вообще об арифметических прогрессиях из простых чисел.

Если генерация смитов вызывает трудности, так это и означает, что проблема именно в генерации смитов, с чего я и начинала (если вы, конечно, читали начало дискуссии; см.первый пост на этой странице).

[tolstopuz]

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

Это прогрессии или не прогресси в таблице, из которой я взяла значения?

Посмотрите на элементы этих прогрессий:

http://en.wikipedia.org/wiki/Primes_in_ ... rogression

$(100997770 + 3624707n)\cdot27751\# + 1$

В самом числе 11961 цифра, но оно имеет очень специфический вид, поэтому 11961-значные простые числа перебирать нет надобности. Для смитов такой возможности нет.

[Nataly-Mak]

Да чёрт бы с ним - со специфическим видом. Я ведь говорила, что люди нашли арифметические прогрессии из простых чисел, которые (числа) состоят из сотен цифр. Вот в чём смысл моего высказывания! А вы на это возразили, что всего из 17 цифр. С чем я позволила себе не согласиться
Я думаю, что для целей построения магических квадратов из последовательных смитов не придётся перебирать 11961-значные смиты

[maxal]

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

[Nataly-Mak]

То, что смиты намного "сложнее" простых чисел, я давно поняла
У них и аддитивные свойства намного хуже, чем у простых чисел.
Но ещё раз повторю: говоря об арифметических прогрессиях из очень больших простых чисел, я имела в виду только очень большие числа, а не сами арифметические прогрессии.
Далее: для построения магического квадрата 3х3 нам не нужна арифметическая прогрессия длины 9, достаточно три прогрессии длины 3 специального вида. А для построения магического квадрата 4х4 вообще не нужны никакие арифметические прогрессии! Достаточно иметь большой массив смитов, для которого выполнить проверку по имеющейся программе на предмет укладывания каждого подходящего массива из 16 последовательных смитов в магический квадрат 4х4. Нельзя сейчас сказать, какой длины массив нужно для этого иметь. Но, как мне кажется, в массиве до 30 миллиардов магический квадрат 4х4 из последовательных смитов должен найтись. Это ведь никто ещё не проверил? А квадрат 5х5 может найтись и в пределах одного миллиарда. Программа для построения магического квадрата из заданного массива, состоящего точно из 25 чисел, составлена пользователем 12d3. Она прекрасно работает. Он сообщал, что проверил числа до миллиона для квадрата 5х5. А до 10 миллионов ещё никто не проверял? А вдруг уже во втором миллионе квадрат найдётся
Повторюсь: на фоне картины с квадратами порядков 3 - 5 прямо чудом кажется наименьший магический квадрат 6-го порядка из последовательных смитов, который построился из первого кандидата. Чего можно ждать для квадратов порядков 7 - 9? Для этих порядков у нас нет даже программы построения. Проверять не с чем.

От рассуждений о сложности задачи задача не станет проще. Её надо решать!

[Nataly-Mak]

Закончила построение наименьших магических квадратов порядков 29 - 35 из произвольных смитов. Вот уточнённые результаты:

n = 29  S = 359151
n = 30  S = 400064  три варианта массива
n = 31  S = 442886  два варианта массива
n = 32  S = 487920
n = 33  S = 536844
n = 34  S = 589129
n = 35  S = 644797

К сожалению, в минимальности констант не уверена. Ещё возможно, что найдены не все варианты массива.

[Nataly-Mak]

Составила схему для построения идеального магического квадрата 5-го порядка из любого массива чисел, состоящего точно из 25 элементов. Массив должен удовлетворять следующим условиям: сумма всех чисел массива должна быть кратна 5. Магическая константа квадрата равна сумме всех членов массива, делённой на 5. Обозначим магическую константу S. Далее: магическая константа квадрата тоже должна быть кратна 5, и в массиве должно содержаться число равное S/5. Это число будет стоять в центральной ячейке квадрата (x13).
Константа ассоциативности квадрата будет равна 2*S/5. Схема квадрата такая:

I   J   K   L   x5
M   N   P   Q   x10
x11 x12 x13 x14 x15
x16 x17 x18 x19 x20
x21 x22 x23 x24 x25

Здесь переменные I, J, K, L, M, N, P, Q свободно варьируются, при этом все они пробегают значения от 1 до 24. Переменные x5, x10, x11, x12 вычисляются по следующим формулам:

x5 = S – I – J – K – L
x10 = S – M – N – P – Q
x11 = M + J – K – N + S/5
x12 = 6*S/5 + I – L – M – N – 2*P – Q

Все остальные элементы xi вычисляются по ассоциативности. Ещё необходимо проверять суммы чисел в первом, втором, четвёртом и пятом столбцах, ибо они не получаются автоматически.
Вот такая несложная схема. По этой схеме можно строить и традиционные идеальные квадраты, тогда массив чисел состоит из первых 25 натуральных чисел, S = 65, x13 = S/5 = 13, константа ассоциативности равна 2*S/5 = 26.

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

[ice00]

Цитата:

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

int main() {
  for (int i1=1; i1<25; i1++)
   for (int i2=1; i2<25; i2++)  
    for (int i3=1; i3<25; i3++) 
     for (int i4=1; i4<25; i4++) 
      for (int i5=1; i5<25; i5++) 
       for (int i6=1; i6<25; i6++) 
        for (int i7=1; i7<25; i7++) 
         for (int i8=1; i8<25; i8++) 
  ; 
}

here the result:

[ice@localhost cpp]$ c++ test.cpp
[ice@localhost cpp]$ time ./a.out

real    5m23.801s
user    5m19.845s
sys     0m0.216s

so about 5 minutes for making nothing inside the cycles

[Nataly-Mak]

Большое спасибо, ice00! Всего 5 минут! Ну, конечно, когда в теле цикла будут выполняться некоторые действия, это время увеличится, но всё равно это будет вполне реальное время.
Итак, мы имеем алгоритм построения идеального квадрата 5-го порядка из заданного массива, состоящего из 25 чисел (массив должен быть подходящим, то есть удовлетворять определённым условиям).
Если, например, мы хотим искать идеальный квадрат 5-го порядка из простых чисел (или из смитов), то можно добавить в программу блок поиска подходящих массивов, а потом каждый найденный массив проверять на предмет построения из него магического квадрата 5х5.