Взаимная (не)простота

[Ktina]

Можно ли выписать в ряд все натуральные числа, большие 1, так,
чтобы любые два соседних числа были не взаимно просты?

(Попытка)

Первое число может быть любым (ессно, >1).
Далее, пусть последнее из уже выписанных чисел равно $n$, а наименьшее из ещё не выписанных равно $m$.
Будем выписывать числа, кратные $n$, которые ещё не были выписаны, пока не наткнёмся на число $k$, которое кратно не только $n$, но и $m$. Выпишем $k$, а следом за ним выпишем $m$.
Теперь у нас последнее из уже выписанных чисел равно $m$, а наименьшее из ещё не выписанных равно $t$.
Повторим для $m$ и $t$ тот процесс, который мы осуществили для $n$ и $m$.
Ну и так далее.

Пример такой последовательности:

2, 4, 6, 3, 9, 12, 15, 5, 10, 20, 25, 30, 35, 7, 14, 21, 28, 42, 49, 56, 8, ...

В чём проблема?
А проблема в том, что после каждого шага (от $n$ к $m$, от $m$ к $t$ и так далее) последовательность получается конечной
В задаче же требовалось построить бесконечную последовательность.

Как быть?

[svv]

Вас смущает то, что нет явной формулы?
А бесконечная последовательность, заданная рекуррентной формулой, — тоже "не вполне бесконечная", по аналогичной причине?

[Ktina]

svv в сообщении #595350 писал(а):

Вас смущает то, что нет явной формулы?

Как чётко Вы это сформулировали!
А я хотела написать, что у меня получилась не сама последовательность, а алгоритм её конструирования.

-- 15.07.2012, 00:18 --

svv в сообщении #595350 писал(а):

А бесконечная последовательность, заданная рекуррентной формулой, — тоже "не вполне бесконечная", по аналогичной причине?

Она потенциально бесконечна.

[svv]

Но Вам кажется, что Ваша ситуация хуже? В чём?

(Оффтоп)

Я не математик, я психоаналитик.

[Ktina]

svv в сообщении #595357 писал(а):

Но Вам кажется, что Ваша ситуация хуже? В чём?

(Оффтоп)

Я не математик, я психоаналитик.

В принципе, Вы правы. В задаче спрашивается "можно ли?".
Мой алгоритм доказывает, что можно.
Вот если бы спросили "приведите пример такой последовательности"...

[Sonic86]

Не доказано, что такой алгоритм корректен. Например не факт, что когда мы будем выписывать числа, кратные очередному $n$, мы не натолкнемся на уже выписанное число А хотя в принципе мы же выписали лишь конечное число чисел, значит, если мы будем пропускать уже выписанные числа, то с какого-то момента выписанные числа перестанут попадаться, и тогда можно выписать $m$ подряд идущих чисел, одно из которых обязательно будет не взаимно просто с $m$.

[apriv]

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

svv в сообщении #595357 писал(а):

Но Вам кажется, что Ваша ситуация хуже? В чём?

(Оффтоп)

Я не математик, я психоаналитик.

В принципе, Вы правы. В задаче спрашивается "можно ли?".
Мой алгоритм доказывает, что можно.
Вот если бы спросили "приведите пример такой последовательности"...

Вы привели пример такой последовательности. Ну, по модулю того, что нужно доказать, что алгоритм всегда сможет продолжаться, и что все числа окажутся выписаны, но это несложно.