2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 61, 62, 63, 64, 65, 66, 67  След.
 
 Re: Prime Sums
Сообщение12.01.2013, 18:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
mertz
я получила новую версию программы. Спасибо.
Понимаю, что надо выбрать конфигурацию в том случае, если конфигураций несколько. Ещё не пробовала новую программу.

У меня работала предыдущая версия. Я пыталась искать максимум для N=6 по введённому решению 1758.
Довольно долго работала программа. Лучший результат найден 1746:

Код:
6  18:52:06  (1720)  [103,109,127,131,137,139,149,151,157,163,173,181] (3,14,5,28,1,25,22,9,33,16,32,18,2,17,6,24,4,27,34,10,23,15,21,19,12,29,11,36,8,35,30,7,31,20,26,13
6  18:52:42  (1724)  [103,113,127,131,137,139,149,151,157,163,173,181] (3,13,5,29,1,25,31,8,34,16,21,17,2,18,6,22,4,28,32,9,30,20,23,15,11,27,12,36,10,35,24,7,26,14,33,19
6  18:53:13  (1734)  [97,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,22,4,32,34,11,26,16,23,17,7,31,10,36,12,35,24,9,30,18,29,13
6  18:53:15  (1746)  [109,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18
6  18:55:52  (1746)  [109,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18
6  18:55:52  [1746]  26    swappin  3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18

Во введённом решении была схема с теоретической оценкой 1760.

Теперь я хочу попробовать искать с конфигурацией, имеющей оценку 887/1777.
Моё предположение: в вашем алгоритме нужна большая удача, чтобы найти самое максимальное решение.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 19:06 


02/11/12
141
Just sent another version.

Prevents running multiple searches at the same time. Searches deeper.

N < 8 needs swapping to find optimal. The search provided is generic. Works good for N=8 to N=29. N=4k + 2 will not find optimal, needs a different version.

Click on any line in the Configurations box to select.

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


22/03/08

7154
Саратов
mertz в сообщении #670825 писал(а):
N < 8 needs swapping to find optimal.

Это не поняла в переводе :-(

Есть шансы найти оптимальные решения для N<8?
Это сейчас самое актуальное :-)
При этом интересуют не те решения, что уже найдены конкурсантами, а более оптимальные.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 19:24 


02/11/12
141
Pavlovsky N=6 Max

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


16 and 19 swapped.
35 and 38 swapped.

N < 8 requires different search.

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


22/03/08

7154
Саратов
mertz в сообщении #670831 писал(а):
Pavlovsky N=6 Max

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


mertz
Вы хотели сказать N=7 Max?

Сейчас запустила последнюю версию вашей программы. Выбрала конфигурацию с оценкой 896/1768: 4,10,8,10,4.

Для этой схемы у меня тоже есть программа. Моя программа не даёт решений 1760,1762 и т.д. Существуют ли такие решения :?:
Пока никто не дал ответ на этот вопрос.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 20:47 


02/11/12
141
I finished 14th. I did not solve N=6 or N=7. I have no program.

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


22/03/08

7154
Саратов
Забавные решения нашлись для "шестёрки":

Код:
(1644)[61,61,89,89,127,131,137,139,149,151,157,163,163,167,173] (15,24,6,33,17,25,23,4,21,7,32,2,9,18,5,27,8,19,36,10,30,14,34,13,20,31,12,35,22,29,28,3,16,11,26,1
(1650)[67,89,89,89,127,131,137,139,149,151,157,163,163,167,173] (16,25,10,34,22,32,29,4,17,6,28,5,12,19,2,24,11,18,33,8,27,14,36,9,15,30,13,35,21,23,26,3,20,7,31,1

В первом решении трое "двойняшек" (пар одинаковых зачётных линий: 61,61; 89,89; 163,163); во втором решении - "тройняшки" и "двойняшки" :D
Правда, решения не максимальные.

-- Сб янв 12, 2013 22:12:51 --

mertz в сообщении #670854 писал(а):
I finished 14th. I did not solve N=6 or N=7. I have no program.

У вас очень интересная программа! Мне нравится.

Я и мой коллега whitefox тоже не решили задачу для N=7.
А решения для N=6 больше 1758 даже и не искали. Как я понимаю, их вообще никто не искал. Но ведь 1758 далеко от теоретического максимума :!:
Тут надо думать :wink: Надо тогда доказать теоретически (строго математически!), что решений больше 1758 не существует. Иначе задача остаётся открытой.

-- Сб янв 12, 2013 22:27:28 --

Решение Pavlovsky 7max.
Эх, до чего же хороша весовая раскраска! Гармония :roll:

Изображение

 Профиль  
                  
 
 Re: Prime Sums
Сообщение13.01.2013, 09:38 


16/08/05
827
Nataly-Mak в сообщении #670865 писал(а):
Надо тогда доказать теоретически (строго математически!), что решений больше 1758 не существует.

Это вряд ли возможно, ведь задача связана с простыми числами. В гораздо более простых задачах очень сложно получать строго детерминированные оценки вокруг простых чисел. С другой стороны, именно в этой задаче при больших $N$, насколько понимаю, получена детерминированная оценка максимума и минимума сумм простых. Достаточно уникальный случай с простыми числами.

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


22/03/08

7154
Саратов
Ну, нет ничего невозможного :D
Вспоминается: никак не могла доказать, что построенный мной магический квадрат 7-го порядка из чисел Смита является наименьшим. А числа Смита не менее (простых чисел) капризны!
Доказательство блестяще выполнил 12d3. Он использовал для этого представление чисел Смита (элементов квадрата) в виде вычетов по модулю 9.
Лень искать это доказательство в теме "Магические квадраты", очень давно это было.

Чтобы доказать минимальность пандиагонального квадрата 6-го порядка из чисел Смита, мы с коллегами трудились несколько месяцев. А для простых чисел задача была решена svb довольно быстро. Тут надо отметить, что доказательство было переборным, увы! Математического доказательства не нашли.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение13.01.2013, 15:51 


02/11/12
141
Can you put the last version as PrimeSums2.zip? Thanks for hosting the files.

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


22/03/08

7154
Саратов
mertz
я выложила на файлообменник самую последнюю версию вашей программы (от 12/01/13 г.)
http://narod.ru/disk/65433245001.887dcd ... 5.zip.html

-- Вс янв 13, 2013 21:09:33 --

Nataly-Mak в сообщении #670865 писал(а):
Решение Pavlovsky 7max.
Эх, до чего же хороша весовая раскраска! Гармония :roll:

Просмотрела все решения нашей команды. Нашла решение, похожее по весовой раскраске на показанное решение Pavlovsky. Это 5min.

Изображение

Ещё три решения - 6min, 8min, 8max - имеют шахматный порядок весовой раскраски. Одно из решений для N=8 было показано выше.
Больше у нас нет решений с интересной весовой раскраской.

-- Вс янв 13, 2013 21:40:39 --

А так красиво? :roll:
Преобразовала показанное выше решение 5min (параллельный перенос на торе).

Изображение

Симметрия весовой раскраски относительно главной диагонали сохранилась.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение13.01.2013, 21:05 


02/11/12
141
here are my solutions to N=5:

Код:
492/808 (2,5,9,9,0)
(790)  [59,61,67,71,73,79,83,89,101,107]
9,11,20,13,8,3,21,22,6,7,14,12,25,2,1,17,23,24,19,18,5,4,16,10,15
0 (  2) 1,2
1 (  4) 3,4,5,10
2 ( 13) 6,7,8,9,11,12,14,15,16,17,18,19,24
3 (  4) 13,20,22,25
4 (  2) 21,23


Код:
490/810 (2,4,13,4,2)
(502)  [29,31,41,43,47,53,59,61,67,71] 7,11,12,9,14,6,13,5,1,16,10,18,20,2,24,17,21,19,15,8,3,23,25,4,22
0 (  2) 24,25
1 (  5) 15,20,21,22,23
2 (  9) 8,10,11,12,13,16,17,18,19
3 (  9) 1,2,3,4,5,6,7,9,14
4 (  0)

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


22/03/08

7154
Саратов
И ещё одна картинка, решение Pavlovsky 7max, перенесённое на торе:

Изображение

У кого есть решения с красивой весовой раскраской, покажите, пожалуйста.

Кстати, БД на конкурсе в этот раз открывать не собираются?

-- Вс янв 13, 2013 22:37:49 --

Интересный момент: для N=5 есть решения только с 4 весовыми категориями; элементы с весом 4 отсутствуют. Такое решение есть у нашей команды - 5min (см. иллюстрацию выше), и mertz привёл такое решение.
Есть ли такие решения для "шестёрки" и "семёрки"? Предположу, что нет.

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


22/03/08

7154
Саратов
Эх!.. тишина :D
Сайт конкурса у меня не открывается. Наверное, решили его совсем закрыть до лучших времён :wink:

Тут все пропали. Может, все всё сказали уже?

Я долго крутила программу Эда. Увы, новых рекордов она не даёт :-(

Что ж, будем готовиться к новому конкурсу - на сайте AZ.
Напомню: старт конкурса 19 января тут.

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


21/02/10
1594
Екатеринбург
Двойная схема.

Возьмем схему порядка 7 с оценкой 1802
Схема 1,2,3,4,8,9,10,11,15,16,17,22,25,26
Структура 1,17,16,11,4

Будем искать набор из 7-ми линий, который можно заполнить так чтобы минмально возможная сумма этих линий была меньше заданного порога.
Для вышеприведенной схемы подсхемы меньше или равные порогу 757

Сумма = 756 3,4,9,15,17,22,25
11(7),22(5),21(6),33(2),32(5),31(4),42(2),41(2)
Сумма = 755 3,9,15,16,17,22,25
11(7),22(4),21(8),33(2),32(4),31(5),42(3),41(1)
Сумма = 755 4,8,9,16,17,25,26
11(6),22(6),21(6),33(2),32(4),31(5),42(2),41(2)
Сумма = 756 4,9,15,16,17,22,25
11(7),22(3),21(9),33(2),32(6),31(3),42(2),41(2)
Сумма = 755 4,11,15,16,17,22,25
11(7),22(4),21(8),33(2),32(4),31(5),42(3),41(1)

Запись 21(6) означает 2 - группа для основной схемы; 1 - группа для подсхемы; 6 - количество ячеек обладающих такими свойствами.

1) Получается, что множество чисел мы разбиваем на 5 групп основной схемой, а затем каждую группу еще разбиваем на подгруппы подсхемой.
2) Линии основной схемы делятся на два набора, первый N линий в сумме дают сумму N наименьших простых чисел. Остальные - остальное.

В результате перебор уменьшается катострофически. Правда распределение чисел по группам и подгруппам становится сложнее.

Число 757, в примере, это сумма первых семи чисел в наборе простых чисел
97,101,103,107,109,113,127,131,137,139,151,157,163,167

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 61, 62, 63, 64, 65, 66, 67  След.

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



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

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


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

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