Последовательность натуральных чисел строится по следующему правилу: каждый член, начиная со второго, получается из предыдущего прибавлением произведения всех его различных простых делителей (например, после числа 12 должно идти число 18, а после числа 125 — число 130). Докажите, что любые две последовательности, построенные таким образом, имеют общий член. ( А. Голованов )

Прошу прощения за придирчивость, но мне не до конца понятно условие задачи. Что должно итти, например, после 1?

задан 4 Мар 16:42

1

@Казвертеночка: после 1 должно идти 2, так как пустое произведение всегда считается равным 1 (как и в случаях типа 2^0, 10^0, 0! и т.п.).

(4 Мар 17:51) falcao
10|600 символов нужно символов осталось
5

Начнём с того, что если встретилось произведение нескольких последовательных простых чисел, то далее к очередному члену именно это количество будет прибавляться, пока проиизведение не умножится на следующее простое число. Например, после 6 пойдут последовательные кратные 6, пока не получится 30; за ним пойдут кратные 30, пока не встретится 210, и так далее.

Теперь достаточно показать, что в любой из последовательностей встретится число, равное произведению нескольких последовательных простых. Всякое число можно представить в виде $%p_1\ldots p_rn$%, где $%r\ge0$%, числа $%p_1$%, ... , $%p_r$% -- попарно различные простые, и $%n$% не делится ни на какое простое, не входящее в этот список. Далее какое-то число шагов к текущему числу будет прибавляться одно и то же произведение $%p_1\ldots p_r$%, пока не получится его кратное, делящееся на некоторое простое $%p$%, не входящее в данный список.

Утверждение будем доказывать индукцией по $%n$%. Если $%n=1$%, то произведение $%p_1\ldots p_r$% будет прибавляться $%q$% раз, где $%q$% -- наименьшее простое, не входящее в список. После этого получится произведение $%p_1\ldots p_rq$%, и далее будет прибавляться оно же, пока произведение не умножится на очередное простое число, которое до этого не фигурировало. Ясно, что после конечного числа таких шагов, мы получим произведение каких-то последовательных простых.

Теперь пусть $%n > 1$%. Здесь $%p_1\ldots p_r$% будет прибавляться $%i\ge1$% шагов, пока $%n$% не превратится в число $%n+i$%, обладающее "посторонним" простым делителем. Пусть $%n+i=q_1\ldots q_sm$%, где $%q_1$%, ... , $%q_s$% -- все простые делители $%n+i$%, отличные от чисел списка $%p_1$%, ... , $%p_r$%. Ясно, что $%i < q_1$%, так как $%n$% не делилось на $%q_1$%, и поэтому число $%n+i$%, делящееся на $%q_1$%, появится менее чем за $%q_1$% шагов. Следовательно, $%n+i < n+q_1\le nq_1$%. Последнее вытекает из того, что $%(n-1)(q_1-1)\ge1$% (неравенство вообще-то является строгим, так как случай $%n=q_1=2$% невозможен).

Таким образом, мы получаем произведение $%p_1\ldots p_rq_1\ldots q_sm$%, где $%m=\frac{n+i}{q_1\ldots q_s}\le\frac{n+i}{q_1} < n$%, и далее применяем индукционное предположение.

ссылка

отвечен 4 Мар 20:58

@falcao, очень большое спасибо!

(5 Мар 0:44) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×762
×158
×141
×89
×3

задан
4 Мар 16:42

показан
192 раза

обновлен
5 Мар 0:44

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru