2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Простые векторы
Сообщение15.04.2017, 07:02 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Появилась забавная задача которую я назвал "простые векторы". Простой вектор это массив из $n$ различных простых $P=(p_0, \ldots, p_{n-1})$, так чтобы любая сумма из нечетного количества элементов подряд была простая. Например массив $(3, 11, 5, 7, 17)$ простой вектор потому что все его суммы простые: $3+11+5=19,~~11+5+7=23,~~5+7+17=29,~~3+11+5+7+17=43$. Самый длинный простой вектор который я нашел имеет 23 элемента:

$(239, 131, 109, 181, 83, 43, 41, 223, 53, 233, 271, 103, 269, 71, 19, 47, 241, 23, 277, 199, 281, 29, 37)$

Кто может найти длиннее? Задача еще выложена тут: http://www.primepuzzles.net/puzzles/puzz_875.htm

 Профиль  
                  
 
 Re: Простые векторы
Сообщение15.04.2017, 17:00 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Карлос сообщил что ему прислали вектор где больше 23 элемента!

 Профиль  
                  
 
 Re: Простые векторы
Сообщение19.04.2017, 02:18 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Гмм похоже форум умер и никто не пишет. Ну ладно больше не буду писать про интересные задачки... :(

 Профиль  
                  
 
 Re: Простые векторы
Сообщение19.04.2017, 10:31 
Заслуженный участник
Аватара пользователя


09/09/14
6328
dimkadimon
Ну зачем же так? За Вашими темами многие следят с интересом. Сужать круги так просто, вот только во всех случаях это приводит к одному и тому же результату: "молчание порождает молчание..." (Сэмюэл Джонсон). А это не то молчание, которое золото.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение19.04.2017, 12:50 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
grizzly спасибо за ответ. Получается все следят, но никто не пишет? Ну ладно, даже это радует. Конечно было бы очень приятно увидеть какое то обсуждение задач, как это было раньше. Даже если у вас нет полных решений, я бы хотел увидеть ваши идеи и доводы. Ладно уговорили, я буду продолжать писать. Я уже видел как несколько отличных форумов развалились потому что активные люди из них ушли. Поэтому очень не хочу чтобы такое произошло с этим форумом.

Вернемся обратно к задаче. Оказывается метод который я описал в своей статье (https://arxiv.org/pdf/1703.06778.pdf) плохо находит длинные простые векторы. Получается более эффективно использовать обычный поиск depth first search. Этим методом я смог улучшить результат до 28 элементов. Поиск продолжается...

-- 19.04.2017, 19:07 --

Допустим у нас есть решение длиной $n: (p_1,\ldots, p_n)$. Тогда можно попытаться добавить еще один элемент $q$ сзади: $(p_1,\ldots,p_n,q)$. При этом не надо проверять простоту всех сумм, а только новыe суммы: $q+p_n+p_{n-1}, q+p_n+p_{n-1}+p_{n-2}+p_{n-3}, \ldots$. Кстати элемент можно добавить спереди: $(q,p_q,\ldots,p_n)$ и тогда надо будет проверять другие суммы: $q+p_1+p_2, q+p1+p_2+p_3+p_4,\ldots$. Добавлять посередине не очень удобно, потому что меняются слишком много сумм.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение23.04.2017, 03:16 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Появились результаты. Один умный человек (J. K. Andersen) нашел вектор из 34 элементов:

(3, 5, 11, 7, 41, 19, 23, 61, 29, 151, 137, 79, 1013, 14347, 43151, 7873,
82469, 444187, 63680783, 80158627, 531845381, 13726723, 2948038229,
341461831, 5391683657, 4759989589, 45033191681, 3342118271593,
57517957292507, 25358009530039, 2584135512217541, 616856808553033,
21225241347141287, 10855325323825603)

Метод простой. Начинаем с 3 и наращиваем простые числа справа. Добавляем только которые дают все простые суммы.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение23.04.2017, 10:57 
Заслуженный участник
Аватара пользователя


09/09/14
6328
dimkadimon в сообщении #1211778 писал(а):
Начинаем с 3 и наращиваем простые числа справа. Добавляем только которые дают все простые суммы.
А чем обычно заканчивается один проход этого жадного алгоритма? Мы выбираем всё множество остатков по какому-то небольшому простому делителю и тогда уже не можем ничего добавить в последовательность?

 Профиль  
                  
 
 Re: Простые векторы
Сообщение23.04.2017, 11:00 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
grizzly в сообщении #1211812 писал(а):
А чем обычно заканчивается один проход этого жадного алгоритма? Мы выбираем всё множество остатков по какому-то небольшому простому делителю и тогда уже не можем ничего добавить в последовательность?

Хороший вопрос. Если честно я не знаю. Есть подозрение что вектор Andersen можно продолжить и дальше, возможно даже до бесконечности. Тогда конца и не будет.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение23.04.2017, 11:12 
Заслуженный участник
Аватара пользователя


09/09/14
6328
dimkadimon в сообщении #1211813 писал(а):
Есть подозрение что вектор Andersen можно продолжить и дальше, возможно даже до бесконечности. Тогда конца и не будет.
Контринтуитивно. Впрочем, нужно самому руками попытаться -- это быстро лечит интуицию.

Это у меня была идея попытаться придумать стратегию остатков по небольшим простым для следующего искомого числа, чтобы оптимизировать жадный алгоритм. Не буду гадать -- подумаю, попробую руками и тогда отпишусь.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение23.04.2017, 20:04 
Аватара пользователя


25/08/12
171
Germany
dimkadimon в сообщении #1211778 писал(а):
Появились результаты. Один умный человек (J. K. Andersen) нашел вектор из 34 элементов:

(3, 5, 11, 7, 41, 19, 23, 61, 29, 151, 137, 79, 1013, 14347, 43151, 7873,
82469, 444187, 63680783, 80158627, 531845381, 13726723, 2948038229,
341461831, 5391683657, 4759989589, 45033191681, 3342118271593,
57517957292507, 25358009530039, 2584135512217541, 616856808553033,
21225241347141287, 10855325323825603)

Метод простой. Начинаем с 3 и наращиваем простые числа справа. Добавляем только которые дают все простые суммы.


There are about 3*10^14 primes up to 10855325323825603. I wonder how it is possible to check all these primes within a reasonable time.
If you want a sequence which is monotonically increasing you get
(3, 5, 11, 13, 29, 31, 47, 61, 71, 409, 2819, 4261, 113819, 124633, 236507,
250693, 501779, 886609, 29089889, 57721663, 157320827, 465327091,
812828249, 1530361321, ...), but already for the 25. element Mathematica did not find a solution within 1 hour. My intuition says that this sequence continues indefinite but of course this seems impossible to prove.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение24.04.2017, 03:02 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
I asked Jens about his solution and this is what he said:

Цитата:
The 34-vector used an old prime tuple finder which set many of the records at http://primerecords.dk/myrecords.htm.
It's in C and requires source modifications for each search. I haven't published it.
The 33rd and 34th term required 17 simultaneous primes.
For that the program made an exhaustive search of all candidates with allowed values modulo the primes up to 31.
It sieves for cases where none of the 17 values have a small factor.
...
I guess vectors can be arbitrarily large but I haven't examined whether my vector is likely to extend forever.
If it can extend in both directions then I expect them to have the same difficulty.


-- 24.04.2017, 08:50 --

Herbert Kociemba в сообщении #1212046 писал(а):
If you want a sequence which is monotonically increasing you get
(3, 5, 11, 13, 29, 31, 47, 61, 71, 409, 2819, 4261, 113819, 124633, 236507,
250693, 501779, 886609, 29089889, 57721663, 157320827, 465327091,
812828249, 1530361321, ...), but already for the 25. element Mathematica did not find a solution within 1 hour.


Thanks Herbert. This looks like a good candidate for OEIS. By the way, what happens if we start with 5 or 7? I will let Jens to submit his 34-element solution to the OEIS.

 Профиль  
                  
 
 Re: Простые векторы
Сообщение04.06.2017, 03:10 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
I published Jens' sequence here: https://oeis.org/A287939
and Herbert's sequence here: https://oeis.org/A287940

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

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



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

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


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

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