2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 47, 48, 49, 50, 51, 52, 53 ... 67  След.
 
 Re: Prime Sums
Сообщение24.12.2012, 08:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #662810 писал(а):
1798 довольно долго искал, ничего не найдено. 1800 еще есть шансы, правда минимальные.

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

Давно уже я писала о поиске решения 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 и посмотреть, какие получатся интересные приближения к решению.
Сейчас займусь этим.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 08:46 
Аватара пользователя


21/02/10
1594
Екатеринбург
3080 для N=7 нашел.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 08:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #662824 писал(а):
3080 для N=7 нашел.

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

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

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.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 10:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
1804 для N=7 есть

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 10:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А здесь две побочные линии - 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, и вся БД для "семёрки" будет готова.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 10:51 
Аватара пользователя


21/02/10
1594
Екатеринбург
1810 для N=7 тоже есть.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 11:41 
Заблокирован
Аватара пользователя


22/03/08

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

-- Пн дек 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 тоже надо поискать.
Чегой-то оно вдруг выпало? :-)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 15:10 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #662870 писал(а):
1810 для N=7 тоже есть.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 15:25 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #662999 писал(а):
Теперь можно разобраться с N=6.


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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение24.12.2012, 16:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А здесь аж 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.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение25.12.2012, 04:58 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Закончила БД для "шестёрки".
В диапазоне 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? Много проверять придётся? :-)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение25.12.2012, 06:49 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Посмотрела на своё решение 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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение25.12.2012, 08:21 
Аватара пользователя


21/02/10
1594
Екатеринбург
Цитата:
107,109,127,131,139,149,151,157,163,167,173,179

Лучше.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение25.12.2012, 08:33 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение25.12.2012, 10:32 
Заблокирован
Аватара пользователя


22/03/08

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

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

Pavlovsky в сообщении #663398 писал(а):
Надо поискать схему теоретическая оценка которой близка к 1752.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 47, 48, 49, 50, 51, 52, 53 ... 67  След.

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



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

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


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

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