Goldbach Squares

[dimkadimon]

У меня есть очень красивая задача близкая к Проблеме Гольдбаха (https://en.wikipedia.org/wiki/Goldbach%27s_conjecture). Надо заполнить квадрат $N \times N$ нечетными простыми числами так чтобы сумма любой пары соседних чисел была одним из чисел от 6 до $4+4N(N-1)$. То есть каждое четное число в этом диапазоне должнo встречаться ровно один раз. Например вот такой квадрат 3х3:

$$\begin{bmatrix} 7 & 5 & 3 \\ 17 & 11 & 3\\ 3 & 7 & 19 \end{bmatrix}$$

Заметьте что простые числа могут повторяться. Суммы в рядах:

7+5 = 12
5+3 = 8
17+11 = 28
11+3 = 14
3+7 = 10
7+19 = 26

Суммы в столбиках:

7+17 = 24
17+3 = 20
5+11 = 16
11+7 = 18
3+3 = 6
3+19 = 22

Заметьте что каждая сумма от 6 до 28 встречается ровно один раз. Самый большой квадрат который мне известен это 10x10, пока не буду показывать.

Задача 1: Найдите самый большой квадрат Гольдбаха.
Задача 2: Существуют ли такие квадраты для всех $N \geq 2$ ?

Задачу можно решать тут или посылать решения на сайт http://www.primepuzzles.net/puzzles/puzz_835.htm. Разрешается обсуждать подходы и показывать решения не более 10х10. Возможно решение этой задачи приблизит нас к решению Проблемы Гольдбаха. Всем удачи!

[dimkadimon]

Выкладываю решение 8х8 чтобы возбудить аппетит :)

$$\begin{bmatrix} 17 & 23& 157& 13& 43& 37& 31& 67 \\ 17 & 7 &47 &71 &79 &79 &97 &127 \\ 3 &71 &131& 31 &61 &127& 37& 73 \\ 23 & 5 &7 &11 &149 &19& 89 &139 \\ 41 & 53 &113 &41 &3& 3 &127 &17 \\ 149 &59 &11 &131 &83 &13 &47 &179 \\ 71 &29 &3& 5 &31 &59 &3& 7 \\ 11 &37 &181& 41& 151 &47 &101& 31 \\ \end{bmatrix}$$

[dmd]

задача действительно красивая. сумел найти только 7х7 квадрат.

(Minizinc)

include "globals.mzn";


int: n = 8;
set of int: N = 1..n;

int: h = 2*n*(n-1);
set of int: H = 1..h;

int: f = h div 2;
set of int: F = 1..f;

int: g = 4+4*n*(n-1);

set of int: P = {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, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511};
set of int: Z = {P[k] | k in 1..max(i,j in index_set(P) where g-P[i] = P[j]) (j)};


array[N, N] of var Z: x;

array[F] of var 6..g: s1 =
  array1d(F, [x[(n-1) - i mod (n-1), n - i mod n] + x[(n-1) - i mod (n-1) + 1, n - i mod n] | i in F]);

array[F] of var 6..g: s2 =
  array1d(F, [x[n - i mod n, (n-1) - i mod (n-1)] + x[n - i mod n, (n-1) - i mod (n-1) + 1] | i in F]);

array[H] of var 6..g: s =
  array1d(H, [if i<=f then s1[i] else s2[i-f] endif | i in H]);


constraint alldifferent(i in H) (s[i]);


solve satisfy;


output 
["x = ["] ++ [show(x[i,j]) ++ if j = n then    if i != n then "; " else "" endif    else ", " endif  | i,j in N] ++ ["]\n"] ++
["s = ", show(s), "\n"] ++ ["\n"];

(LocalSolver)

function model()
{
  n = 5;
  g = 4+4*n*(n-1); K = 2*n*(n-1); f = round(K/2);
  P = {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, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511};
  Pc = count(P)-1;

  i = 0; q = 0; while (!q) {h = g - P[i]; i = i + 1; for[j in 0..Pc] if (h == P[j]) {q = 1; H = j;};};

  X[1..n][1..n] <- int(0, H);

  S1[i in 1..f] <- P[X[n-1 - mod(i,n-1)][n - mod(i,n)]] + P[X[n-1 - mod(i,n-1) + 1][n - mod(i,n)]];
  S2[i in 1..f] <- P[X[n - mod(i,n)][n-1 - mod(i,n-1)]] + P[X[n - mod(i,n)][n-1 - mod(i,n-1) + 1]];
  S[i in 1..K] <- i<=f ? S1[i] : S2[i-f];

  for[i in 1..K][j in 1..K : i < j] constraint S[i] != S[j];

  for[i in 1..K] constraint S[i] <= g;

  minimize 1;
}


function output()
{
  solFile = openAppend(solFileName);

  println(); print("X= [");
  for[i in 1..n]
  {
    for[j in 1..n-1] print(P[getValue(X[i][j])],", "); print(P[getValue(X[i][n])], i!=n ? "; " : "]");
  };
  println(); println(); print("S= [");
  for[i in 1..K] print(getValue(S[i]), i!=K ? ", " : "]"); println();

  println(solFile, n); print(solFile, "X= [");
  for[i in 1..n]
  {
    for[j in 1..n-1] print(solFile, P[getValue(X[i][j])],", "); print(solFile, P[getValue(X[i][n])], i!=n ? "; " : "]");
  };
  println(solFile); println(solFile);
//  println(g); println(K); println(H);
}


function param()
{
  if(lsTimeLimit == nil) lsTimeLimit=10000;
  if(lsTimeBetweenDisplays == nil) lsTimeBetweenDisplays=5;
  if(lsNbThreads == nil) lsNbThreads=3;
//  if(lsSeed == nil) lsSeed=2;
  if(solFileName == nil) solFileName= "gbc.txt";
}

(AMPL)

param n integer, := 3;
param g integer, := 4+4*n*(n-1);
param K integer, := 2*n*(n-1);
param f integer, := K div 2;
set Z := {3,5,7,11,13,17,19,23};


var X {1..n, 1..n} integer in Z; 

var S {i in 1..K} =
  if i<=f
     then X[2 - i mod 2, 3 - i mod 3] + X[2 - i mod 2 + 1, 3 - i mod 3]
     else X[3 - (i-f) mod 3, 2 - (i-f) mod 2] + X[3 - (i-f) mod 3, 2 - (i-f) mod 2 + 1];


subject to c1 : alldiff {i in 1..K} S[i];

subject to c2 {i in 1..K} : S[i] <= g;


#option solver jacop;
#option jacop_options 'version timing=1 outlev=1 outfreq=10 timelimit=60';

#option solver gecode;
#option gecode_options 'outlev=1 outfreq=10 timelimit=60';

#option solver ilogcp;
#option ilogcp_options 'version timing=1 timelimit=30 logperiod=1000000 outlev=verbose';

option solver locsol;
option locsol_options 'version verbosity=normal timing=1 time_between_displays=10 timelimit=600 threads=3';


solve;
display X;
display S;

dimkadimon

Не могли бы Вы в двух словах описать, каким алгоритмом был найден квадрат 10х10? И найден ли 11х11?

[dmd]

нашел квадраты 8х8 и 9х9

(8x8)

71, 107, 97, 97, 79, 113, 97, 83;
23, 101, 127, 61, 103, 113, 59, 137;
113, 61, 79, 139, 83, 101, 89, 29;
89, 61, 73, 73, 71, 59, 109, 3;
53, 67, 43, 59, 67, 37, 61, 23;
53, 47, 43, 29, 41, 37, 31, 31;
29, 29, 37, 23, 23, 19, 19, 17;
5, 11, 7, 7, 5, 5, 3, 3

(9x9)

211, 13, 257, 23, 199, 17, 3, 223, 43;
61, 193, 3, 197, 89, 101, 181, 61, 149;
197, 59, 233, 11, 113, 149, 83, 151, 127;
71, 89, 41, 59, 53, 23, 71, 67, 67;
103, 61, 31, 37, 37, 41, 43, 43, 89;
101, 79, 73, 29, 23, 17, 13, 37, 89;
97, 79, 43, 19, 23, 11, 11, 7, 139;
151, 19, 101, 7, 31, 5, 3, 3, 29;
79, 109, 137, 5, 131, 83, 103, 79, 211

[dimkadimon]

dmd в сообщении #1136317 писал(а):

dimkadimon

Не могли бы Вы в двух словах описать, каким алгоритмом был найден квадрат 10х10? И найден ли 11х11?

Наконец то появился какой то интерес к задаче. Поздравляю с решением 9х9! Я использовал метод отжига. Минимизируем количество пропущенных четных чисел. Если обменять два числа то можно быстро проверить перемену в пропущенных четных числах. Для 10х10 я запускал 1000 стартовых случайных квадратов на кластере и искал несколько дней. Для 11х11 несколько раз доходил до одно пропуска, но решение так и не находилось.

Кстати появились два продолжения к задаче:

http://www.primepuzzles.net/puzzles/puzz_839.htm
http://www.primepuzzles.net/puzzles/puzz_840.htm

Для Puzzle 840 я могу найти решения любого размера. А вот для Puzzle 839 пока больше 7х7 не находил - задача трудная, поэтому советую попробовать. Скоро пошлю свои решения на сайт.

[dimkadimon]

Появилась новая головоломка на эту тему:

http://simplementenumeros.blogspot.com. ... uzzle.html