Простые векторы

[dimkadimon]

Появилась забавная задача которую я назвал "простые векторы". Простой вектор это массив из $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

[dimkadimon]

Карлос сообщил что ему прислали вектор где больше 23 элемента!

[dimkadimon]

Гмм похоже форум умер и никто не пишет. Ну ладно больше не буду писать про интересные задачки... :(

[grizzly]

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

[dimkadimon]

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$. Добавлять посередине не очень удобно, потому что меняются слишком много сумм.

[dimkadimon]

Появились результаты. Один умный человек (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 и наращиваем простые числа справа. Добавляем только которые дают все простые суммы.

[grizzly]

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

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

А чем обычно заканчивается один проход этого жадного алгоритма? Мы выбираем всё множество остатков по какому-то небольшому простому делителю и тогда уже не можем ничего добавить в последовательность?

[dimkadimon]

grizzly в сообщении #1211812 писал(а):

А чем обычно заканчивается один проход этого жадного алгоритма? Мы выбираем всё множество остатков по какому-то небольшому простому делителю и тогда уже не можем ничего добавить в последовательность?

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

[grizzly]

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

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

Контринтуитивно. Впрочем, нужно самому руками попытаться -- это быстро лечит интуицию.

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

[Herbert Kociemba]

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.

[dimkadimon]

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.

[dimkadimon]

I published Jens' sequence here: https://oeis.org/A287939
and Herbert's sequence here: https://oeis.org/A287940