Бесконечная последовательность (по мотивам задачи С.Берлова)

[Ktina]

Дана бесконечная последовательность натуральных чисел $\{a_n\}$, в которой для всех натуральных $n$ выполняется соотношение

$$a_{n+2}=\text{НОД}(a_{n}, a_{n+1})+1$$

а) Может ли эта последовательность содержать более 2016 различных чисел?
б) Может ли эта последовательность содержать более 2016 различных простых чисел?

[gris]

С помощью нехитрого приспособления в виде $a_{n-1}=(a_{n}-1)\cdot( a_{n+1}-1)$ можно организовать обратное движение. Надо ещё следить, чтобы не появлялось паразитных общих множителей. И вроде бы оно получается бесконечно возрастающим. Простых чисел там, конечно, не будет. Но это же просто вариант.
Например: $3,8,14,91,1170,105210,122989321...$, что оборачивается в
$122989321,105210,1170,91,14,8,3,2,2,3...$

[Ktina]

gris в сообщении #1103003 писал(а):

Например: $3,8,14,91,1170,105210,122989321...$, ...

А почему не $3,4,6,15,70,...$?

[12d3]

По пункту 2. После простого $p$ следует либо $p+1$, либо $2$, в обоих случаях последовательность максимум за два хода сваливается в бесконечный цикл $(2,2,3)$, так что всего максимум 3 различных простых.

[DeBill]

gris в сообщении #1103003 писал(а):

Надо ещё следить, чтобы не появлялось паразитных общих множителей

Да вроде их и не будет никогда - по индукции (ну, если база для неё есть)

[Dmitriy40]

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

А почему не $3,4,6,15,70,...$?

Объясните мне дураку, а как тут получилось число 6? Если $\text{НОД}(3,4)=1$? Или НОД это не наибольший общий делитель?
Я сколько не считал, никак не могу получить возрастающую последовательность, НОД всегда же не превышает наименьшего из двух чисел, если наименьшее число меньше другого на 2 и более, то следующее число будет меньше предыдущего, если меньше на 1, может быть равно предыдущему (но никак не больше его!), если же оба числа одинаковы, то следующее будет противоположной чётности и не будет иметь общих делителей кроме 1. Т.е. последовательность или уменьшается, или не более чем за два шага сваливается в цикл $(2,2,3)$.
Я бы поискал решение в виде первых двух чисел равных произведению 2016-2017 простых (или увеличенных на 1 или около того), чтобы при каждом шаге одно из простых "откусывалось" из чисел, но до сваливания в цикл $(2,2,3)$ успело появиться нужное количество простых чисел. Как-то так.

[provincialka]

Dmitriy40 в сообщении #1103064 писал(а):

а как тут получилось число 6?

Насколько я поняла, приводится пример "обратной" последовательности:

gris в сообщении #1103003 писал(а):

С помощью нехитрого приспособления в виде $a_{n-1}=(a_{n}-1)\cdot( a_{n+1}-1)$ можно организовать обратное движение.

[DeBill]

Dmitriy40 в сообщении #1103064 писал(а):

Объясните мне

Дык последовательность надо читать задом наперед.
И будет все хорошо: по 70 и 15 - следуюший - 6.
А, уже написали..

[Dmitriy40]

(Оффтоп)

provincialka, DeBill, спасибо, действительно обратная, не обратил внимания.