Является ли число 11 членом этой последовательности?

[Ktina]

Первый член последовательности равен 2, а каждый член, начиная со второго, равен наибольшему простому делителю произведения всех предыдущих членов, увеличенного на 1.
Является ли число 11 членом этой последовательности?

[mihaild]

Да. A000945
А есть простое решение?

[gris]

Э, там наибольший простец. То есть последовательность получается $2,3,7,43,139,50207$ В ней нету чисел, делящихся на $2,3,7$. То есть желанное произведение плюс единица может делиться на $11$ и на $5$. Пусть пятёрки нету. Тогда произведение не может кончаться на $0$, то есть пятёрка должна быть. Но тогда произведение должно кончаться на $4$.
Ой, да это похожая последовательность A000946. Вообще, там написано, что пятёрки нет. А значит и одиннадцати нет. То есть достаточно показать, что пятёрки нет. Если пятёрка есть, то произведение с единицей будет степенью $5$. А тогда просто произведение кончается на $24$. Ага, щас!

[waxtep]

Вторая попытка, в этот раз вроде не наврал
Чтобы встретилось $11$, произведение предыдущих членов последовательности $p$ должно иметь вид $p=5^a 11^b-1$ для каких-то целых $a\ge0,b>0$, делиться на $42$ и не делиться на $4$. По модулю $4$ получаем $b=2n+1$, затем, по модулю $6$, $a=2m+1$, где $m,n$ - неотрицательные целые. Тогда, должно быть $55\cdot25^m\cdot121^n=42k+1$ для натурального $k$, или, по модулю $7$, $6\cdot4^m\cdot2^n\equiv1$, чего быть не может, поскольку степень двойки дает остатки $1,2,4$ по модулю $7$.

[Ktina]

gris
waxtep
Большое спасибо!

-- 30.05.2018, 00:54 --

Вообще, было бы неплохо доказать, что последовательность строго возрастает.

[waxtep]

Ktina в сообщении #1316147 писал(а):

Вообще, было бы неплохо доказать, что последовательность строго возрастает.

Не, там $a_{10}<a_9$, видно по ссылке на oeis от gris, не судьба

-- 30.05.2018, 01:22 --

...и $a_{14}$ сильно меньше $a_{13}$ (там же)
Но как быстро эта штука растет!

[kotenok gav]

waxtep в сообщении #1316136 писал(а):

вид $p=5^a 11^b-1$ для каких-то целых $a\ge0,b>0$, делиться на $42$ и не делиться на $4$.

Почему?

[waxtep]

kotenok gav в сообщении #1316166 писал(а):

Почему?

Последовательность начинается с $2,3,7$, значит, произведение делится на $42$; $p_1\cdot p_2\ldots \cdot p_n+1$ не делится ни на одно из $p_i$, поэтому, во-первых, в последовательности не может быть повторов (в частности, двойка больше никогда не встретится, и произведение не будет делиться на $4$), и, во-вторых, простыми множителями в разложении числа (произведения предыдущих членов плюс один), предшествующего $11$, могут быть только $5$ и $11$, но не $2,3,7$ и не простые, большие $11$

[Ktina]

waxtep в сообщении #1316153 писал(а):

Но как быстро эта штука растет!

Неужели даже быстрее, чем функция Аккермана?

[mihaild]

Ktina в сообщении #1316201 писал(а):

Неужели даже быстрее, чем функция Аккермана?

Нет, эта штука растет не быстрее чем двойная экспонента: если $x_k < 2^{2^k}$ при $k < n$, то $x_n < \prod_{k=0}^{n-1} x_k + 1 < \prod_{k = 0}^{n - 1} 2^{2^k} + 1 = 2^{2^n - 1} + 1 < 2^{2^n}$, а двойная экспонента примитивно рекурсивна (ну и вообще $A(4, n)$ уже растет сильно быстрее, чем двойная экспонента).

[maxal]

Cox and van der Poorten show that 5, 11, 13, 17, ... are not members of this sequence.
С их статьей (довольно элементарной) можно ознакомиться тут.

[Ktina]

maxal в сообщении #1317900 писал(а):

Cox and van der Poorten show that 5, 11, 13, 17, ... are not members of this sequence.
С их статьей (довольно элементарной) можно ознакомиться тут.

Much obliged.