Последовательность Евклида

[Xenia1996]

Последовательность Евклида определена следующим образом:

$a_0=2$
$a_{n+1}$ является наибольшим простым делителем числа $a_0 a_1 a_2 \dots a_n+1$

Встретится ли в этой последовательности число

а) 5

б) 11

?

[Sonic86]

а) $a_{n+1}=5 \Leftrightarrow a_0...a_n+1=2^a3^b5^c$.
$a_0=2, a_1=3 \Rightarrow a=b=0 \Rightarrow 5^c-1=a_0...a_n \Rightarrow 4|a_0...a_n$, однако только $a_0=2$, а остальные числа нечетны.

-- Пн мар 28, 2011 21:51:55 --

б) Аналогично $a_{n+1}=11 \Leftrightarrow a_0...a_n=2^a3^b5^c7^d11^e-1$.
$a_0=2,a_1=3, a_2=7$, отсюда $a=b=d=0$, и тогда
$a_0...a_n=5^c11^e-1$.
Теперь
$4 \not | 5^c11^e-1 \Leftrightarrow e \equiv 1 \pmod 2$.
$3|5^c11^e-1 \Leftrightarrow (-1)^{c+e} \equiv 1 \pmod 3 \Leftrightarrow c \equiv e \pmod 2 \Rightarrow c \equiv 1 \pmod 2.$
И теперь $43|5^c11^e-1 \Leftrightarrow c\text{ind}(5)+e\text{ind}(11) \pmod {42} \Rightarrow \text{ind}(5)+\text{ind}(11) \pmod 2,$ однако $5$ - первообразная по модулю 43, а вот $11^7 \equiv 1 \pmod {43}$, так что $\text{ind}(5)$ нечетно, а $\text{ind}(11)$ - четно. Противоречие.

Последовавшие за этим сообщением троллинг vorvalm и ответы на него отделены в Чулан.
/ GAA, 9.04.11

[Sonic86]

Интересно было бы доказать, что последовательность является возрастающей (похоже, что это так).

[venco]

Sonic86 в сообщении #428887 писал(а):

Интересно было бы доказать, что последовательность является возрастающей (похоже, что это так).

$a_9=4680225641471129 > a_{10}=1368845206580129$
См. A000946
Да и дальше я не вижу причин, по которым последовательность должна возрастать.

[VAL]

venco в сообщении #432174 писал(а):

Sonic86 в сообщении #428887 писал(а):

Интересно было бы доказать, что последовательность является возрастающей (похоже, что это так).

$a_9=4680225641471129 > a_{10}=1368845206580129$
См. A000946
Да и дальше я не вижу причин, по которым последовательность должна возрастать.

Разумеется, не должна возрастать. Монотонно.
Но, мне представляется очевидным, что она должна "возрастать в среднем". Произведение предыдущих членов растет (и довольно быстро). Ясно что наибольший простой делитель таких произведений, увеличенных на единицу, в среднем будет расти.

Рассуждение, конечно, не строгое. Но зато правильное

-- 07 апр 2011, 20:04 --

Придумал вариант обоснования "возрастания последовательности в среднем".
Допустим, что это не так. Тогда рано и или поздно мы переберем все простые (кроме тех, которые заведомо не могут быть членами последовательности, как, например, 5) из некоторого диапазона. Тогда очередному члену ничего не останется, как быть больше всех предыдущих. И т.д.

[Null]

Это называется стремиться к $+\infty$

[VAL]

Null в сообщении #432234 писал(а):

Это называется стремиться к $+\infty$

Полагаю, очевидной является только неограниченность последовательности, но не стремление ее к бесконечности.

[venco]

VAL в сообщении #432240 писал(а):

Null в сообщении #432234 писал(а):

Это называется стремиться к $+\infty$

Полагаю, очевидной является только неограниченность последовательности, но не стремление ее к бесконечности.

И то и другое присуще любой натуральной последовательности без повторов.

[venco]

VAL в сообщении #432436 писал(а):

venco в сообщении #432245 писал(а):

VAL в сообщении #432240 писал(а):

Полагаю, очевидной является только неограниченность последовательности, но не стремление ее к бесконечности.

И то и другое присуще любой натуральной последовательности без повторов.

Но стремление к бесконечности не очевидно

"Очевидность" - понятие относительное.

[VAL]

venco в сообщении #432461 писал(а):

VAL в сообщении #432436 писал(а):

Но стремление к бесконечности не очевидно

"Очевидность" - понятие относительное.

Соглашусь.
За примерами далеко ходить не надо. Достаточно перечитать эту ветку