Prime Sums

[Nataly-Mak]

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

1798 довольно долго искал, ничего не найдено. 1800 еще есть шансы, правда минимальные.

Информация исчерпывающая
Чего искал, как искал, какие проверил структуры-схемы-разбиения-разложения - это не столь важно, главное - долго искал

Давно уже я писала о поиске решения 1798:

Цитата:

Структура очень симпатичная - симметричная: 2,16,13,16,2.
Разбиение естественное.
Так у меня 12 зачётных линий выставляются с ходу:

101,103,107,109,113,127,131,137,139,149,151,157

Может быть, разложение плохое. Но я сравнила с тем, которое вы привели, у меня только значение 151 лишнее, в вашем разложении нет такого числа; все остальные числа совпадают.

Выбросим число 151, получится 11 выставленных зачётных линий из вашего разложения 1798 на 14 простых. Это уже совсем не плохо.

Впрочем, я понимаю, вам пока нельзя все карты раскрывать, мне можно
Ну, потерпим до окончания конкурса, осталось совсем чуть-чуть.

Как я уже писала, whitefox написал специальную программу доработки квадратов с выставленными зачётными линиями в количестве меньше 2N. Я крутила эту программу для приведённой структуры-схемы-разбиения, но не для Q=1798, а для Q=1802 (немного изменила разбиение), для меня это было в тот момент актуально. Сейчас уже нет, можно попробовать покурутить для Q=1798 и посмотреть, какие получатся интересные приближения к решению.
Сейчас займусь этим.

БД для "шестёрки" почти закончила. Отмечу, что решения для "шестёрки" ищутся гораздо дольше, чем решения для "семёрки" (речь идёт не об оптимальных решениях и не близких к ним).

[Pavlovsky]

3080 для N=7 нашел.

[Nataly-Mak]

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

3080 для N=7 нашел.

Ура! Молодец!
Значит, остались пока не найдены 1804 и 1810. Всего два!

А я и думала: чегой-то 3080 выскочило вдруг

Vovka17 пропал совсем. Решение 3088 только у него есть, наверное.

-- Пн дек 24, 2012 10:25:58 --

Просмотрела квадраты, выданные при поиске решения 1774 для N=6.

Такие есть приближения к решению:

1. выставлено 10 зачётных линий:

16,6,20,3,30,9,4,27,2,17,13,29,32,22,23,12,33,14,8,35,11,28,19,36,25,15,31,7,34,18,5,26,1,24,10,21

2. выставлено 11 зачётных линий, но две имеют одинаковое значение:

31,8,34,10,32,16,2,20,11,19,9,29,14,3,30,1,26,6,5,18,7,21,13,23,28,4,33,12,35,17,15,27,22,25,24,36
30,7,32,8,34,18,5,24,10,14,13,26,16,3,27,2,29,15,1,17,9,21,4,25,23,6,33,11,35,19,12,28,20,31,22,36
27,11,34,8,36,23,3,16,10,17,7,31,21,1,28,2,32,14,4,19,5,18,13,26,24,9,35,12,29,22,6,30,15,25,20,33

Интересно: во всех решениях повторяется значение 151.

На мой взгляд существование решения 1774 маловероятно.

-- Пн дек 24, 2012 10:49:35 --

Покрутила немного приведённую выше схему-разбиение с оценкой Q=1798 по программе доработки.
Вот, например, какое решение выдаёт программа:



Выставлено 13 различных зачётных линий, но одна из них побочная, то есть она не входит в данную схему; это зачётная линия со значением 227, я нарисовала её.
Таким образом, фактически выставлено 12 правильных зачётных линий.
Значения двух зачётных линий, входящих в схему, 129 и 145.

[Pavlovsky]

1804 для N=7 есть

[Nataly-Mak]

А здесь две побочные линии - 227 и 229!
И в результате 14 выставленных зачётных линий и готовое решение, но... не из той оперы

48,49,41,40,22,12,4,
28,45,42,16,2,10,14,
44,47,35,36,3,23,33,
38,18,5,30,26,17,15,
31,32,25,46,39,43,20,
7,11,37,19,8,21,6,
24,27,29,34,13,1,9

Интересно: значения зачётных линий, входящих в схему, опять 129 и 145.

-- Пн дек 24, 2012 11:36:08 --

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

1804 для N=7 есть

Класс!
У вас действительно очень эффективный алгоритм.
Осталось одно решение - 1810, и вся БД для "семёрки" будет готова.

[Pavlovsky]

1810 для N=7 тоже есть.

[Nataly-Mak]

Ну, вот... ввёл в заблуждение dimkadimon
Pavlovsky
как руководитель темы объявляю вам благодарность с занесением в личное дело

-- Пн дек 24, 2012 13:02:07 --

Продолжаю крутить программу доработки квадратов для Q=1798.
При этом делаю так: каждый новый квадрат, выданный программой, добавляю во входные данные, пусть он тоже дорабатывается.
Ну, вот получила квадрат с такой же ситуацией: выставлено 13 зачётных линий, но одна побочная; однако значения двух не выставленных зачётных линий здесь - 129 и 133:

48,49,42,43,19,11,4,
31,44,47,14,2,8,17,
45,35,41,36,3,26,33,
39,13,16,27,21,7,6,
20,38,25,40,34,32,29,
15,12,37,28,10,24,5,
22,23,30,46,18,1,9

-- Пн дек 24, 2012 13:31:15 --

Вот так выглядит у меня сейчас БД для "шестёрки":

(Оффтоп)

912  914  916  918  922  924  928  934  936  940  942  956  960  964  970  972  978  980  
1002  1012  1014  1016  1018  1024  1026  1036  1038  1040  1044  1046  1050  1052  1056  1060  1062  1064  1066  1068  1070  1074  1078  1086  1088  1090  1092  1094  1096  1098    
1100  1104  1106  1110  1112  1114  1116  1118  1120  1122  1124  1126  1128  1130  
1134  1136  1138  1140  1142  1144  1146  1148  1150  1152  1154  1156  1158  
1160  1162  1164  1166  1168  1170  1172  1174  1176  1178  1180  1182  1184  1186  
1188  1190  1192  1194  1196  1198  
1200  1202  1204  1206  1210  1212  1214  1216  1218  1220  1222  1224  1226  1228  1230  1232  
1234  1236  1240  1242  1244  1246  1248  1250  1252  1254  1256  1258  1260  1262  1264  1266  
1268  1270  1272  1274  1276  1278  1280  1282  1284  1286  1288  1290  1292  1294  1296  1298  
1300  1302  1304  1306  1308  1310  1312  1314  1316  1318  1320  1322  1324  1326  1328  1330  
1332  1334  1336  1338  1340  1342  1344  1346  1348  1350  1352  1354  1356  1358  1360  1362  
1364  1366  1368  1370  1372  1374  1376  1378  1380  1382  1384  1388  1390  1392  1394  1396  1398    
1400  1402  1404  1406  1408  1410  1412  1414  1416  1418  1420  1422  1424  1426  1428  1430  1432  
1434  1436  1438  1440  1442  1444  1446  1448  1450  1452  1454  1456  1458  1460  1462  1464  
1466  1468  1470  1472  1474  1476  1478  1480  1482  1484  1486  1488  1490  1492  1494  1496  1498  
1500  1502  1504  1506  1508  1510  1512  1514  1516  1518  1520  1522  1524  1526  1528  1530  
1532  1534  1536  1538  1540  1542  1544  1546  1548  1550  1552  1554  1556  1558  1560  1562  1564  
1566  1568  1572  1574  1576  1578  1580  1582  1584  1592  1596  1598    
1600*  1602  1604*  1606  1608*  1610  1612  1614  1616*  1618*  1620  1622*  1624  1626*  1628  1630  
1632  1634  1636  1638  1640*  1642  1644  1646*  1648*  1650  
1652  1654*  1656  1658  1660  1662  1664  1666  1668  1670*  1672  1674  1676*  1678  1680*  1682*  1686  1688  1690  1698  1700*  1702*  1704* 1706  1708  1710  1712*  1714  1716  1718  1720  1722  1724  1726  1728  1730  1732  1734  1736  1738

То, что помечено звёздочкой, это я сечас нашла, специально искала, а остальное было найдено раньше в процессе поиска разных решений.
Ищу дальше, иду снизу вверх. Как уже сказала, решения ищутся довольно долго, не секунды, как решения для "семёрки" находились.
Решения, близкие к оптимальным, не ищу, так как их нашёл dimkadimon.
Да, и выпавшее у dimkadimon решение 1752 тоже надо поискать.
Чегой-то оно вдруг выпало?

[dimkadimon]

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

1810 для N=7 тоже есть.

Отличная работа! Теперь можно разобраться с N=6.

[Pavlovsky]

dimkadimon в сообщении #662999 писал(а):

Теперь можно разобраться с N=6.

Чего то нет желания.
1) Надо перенести последние улучшения из алгоритма для нечетных N в алгоритм для четных N.
2) Максимум для N=6, моему алгоритму дался очень тяжело. Значит надо разбираться почему.

А настроение уже предновогоднее. Пусть компьютер теперь поработает. Пусть ищет рекорды для N=7. Мое участие ограничевается просмотром результатов два раза в день.

[Nataly-Mak]

А здесь аж 6 побочных линий! Значения их: 211, 223, 227, 227, 227 и 229.

48,49,45,47,20,4,11,
26,40,42,10,2,5,6,
35,34,32,37,3,19,38,
44,8,16,25,27,14,17,
29,43,23,46,33,39,30,
13,12,41,28,15,21,7,
22,24,31,36,9,1,18

Не выставленные зачётные линии имеют значения 133 и 141.

[Nataly-Mak]

Закончила БД для "шестёрки".
В диапазоне 912 - 1738 есть все решения.
Пока не искала решение 1752. Это единственное отсутствующее в БД решение (для решений, близких к оптимальным, ссылаюсь на результаты dimkadimon).

У меня в начале БД есть решения:

890  900  902  904  906  908  910

а в конце БД:

1740  1742  1744  1746  1748  1754  1756  1758

-- Вт дек 25, 2012 06:15:26 --

Важная информация для поиска решения 1752:

whitefox в сообщении #656153 писал(а):

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

whitefox
а сколько надо было перебрать всего вариантов для поиска решения 1758?

Имеется всего две неизомрфные схемы с оценкой 1760.
Для каждой из них имеется по 14 разбиений с оценкой 1758.
Итого нужно было проверить максимум 2 х 14 = 28 сочетаний схема-разбиение.

Если бы для этих схем решение не нашлось бы, то пришлось бы рассматривать схемы с оценкой 1768, а для них разбиений с оценкой 1758 слишком много.

whitefox
а сколько имеется разбиений с оценкой 1752? Много проверять придётся?

[Nataly-Mak]

Посмотрела на своё решение 1758 для N=6.
Структура: 2,14,8,6,6.
Разбиение:

$M_0=(1,2,3,4,5,6)$
$M_1=(7,8,9,10,11,12)$
$M_2=(13,14,15,16,17,18,19,20)$
$M_3=(21,22,23,24,25,26,27,28,29,30,31,32,33,36)$
$M_4=(34,35)$

Есть несколько способов сделать из этого разбиения разбиение с оценкой Q=1752.
Например, переставить числа с весом 3 и 4 - 28 и 34 (или 29 и 35).

У меня есть программа полного перебора для этой схемы. По этой программе получено решение 1758. Можно попробовать покрутить эту программу с разными разбиениями, дающими оценку Q=1752.

-- Вт дек 25, 2012 08:42:35 --

И вот первое приближение к решению 1752:

149 
 151 
 157 
 167 
 181 
 173 
 113 
 127 
 139 
 137 
 131 
 127 

 21  22  23  24  34  25  26  15  35  30  18  31  32  28  27  29  33  36  7  14  13  17  20  16  19  12  8  9  10  11 
 S= 1752 

 0  18  0  21  0  33 
 31  7  26  14  22  13 
 0  15  0  27  0  23 
 24  12  36  17  32  16 
 9  34  10  28  11  35 
 29  8  25  20  30  19

Просто убрала в программе проверку 12-ой зачётной линии на различность, в результате эта линия повторила одно из предыдущих 11 значений - 127.
Понятно, что в столбце выставленные зачётные линии, в строке элементы квадрата.
Правда, в моей программе нет проверки на побочные линии, а они очень часто возникают.
Но если задать программе конкретное разложение 1752 на 12 простых чисел, то уже никакие побочные линии не страшны.

Pavlovsky
какое разложение 1752 на 12 простых вы рекомендуете?
У меня есть такие два варианта:

103,113,127,131,139,149,151,157,163,167,173,179
107,109,127,131,139,149,151,157,163,167,173,179

[Pavlovsky]

Цитата:

107,109,127,131,139,149,151,157,163,167,173,179

Лучше.

Но я бы поработал над выбором схемы. Схема 2,14,8,6,6 имеет теоретическую оценку 1760. Что далековато от 1752. Надо поискать схему теоретическая оценка которой близка к 1752. Увы мои алгоритмы поиска схем заточены на поиск схем близких к оптимальной. Схемы с теоретической оценкой рядом с 1752 искать отказываются.

[Nataly-Mak]

Pavlovsky
спасибо за рекомендации.

Эх, whitefox куда-то пропал Он большой специалист по схемам.

[Nataly-Mak]

У меня есть два решения 1754 (N=6). Посмотрела их. Увы, в них структуры с теоретическими оценками Q=1760 и Q=1768. Тоже не годятся.

-- Вт дек 25, 2012 11:42:19 --

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

Надо поискать схему теоретическая оценка которой близка к 1752.

А существуют ли такие? Не является ли теоретическая оценка 1760 самой близкой к 1752?

Даже решение 1748 у меня имеет структуру с теоретической оценкой 1760.