2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Goldbach Squares
Сообщение19.06.2016, 14:02 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
У меня есть очень красивая задача близкая к Проблеме Гольдбаха (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. Возможно решение этой задачи приблизит нас к решению Проблемы Гольдбаха. Всем удачи!

 Профиль  
                  
 
 Re: Goldbach Squares
Сообщение21.06.2016, 15:46 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Выкладываю решение 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}$$

 Профиль  
                  
 
 Re: Goldbach Squares
Сообщение07.07.2016, 11:52 


16/08/05
1146
задача действительно красивая. сумел найти только 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?

 Профиль  
                  
 
 Re: Goldbach Squares
Сообщение08.07.2016, 13:57 


16/08/05
1146
нашел квадраты 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

 Профиль  
                  
 
 Re: Goldbach Squares
Сообщение30.07.2016, 11:01 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 не находил - задача трудная, поэтому советую попробовать. Скоро пошлю свои решения на сайт.

 Профиль  
                  
 
 Re: Goldbach Squares
Сообщение31.07.2016, 13:13 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Появилась новая головоломка на эту тему:

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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