Придумалось по мотивам одной из задач с форума.

Доказать, что существует бесконечная последовательность натуральных чисел $%a_1$%, $%a_2$%, ... , $%a_n$%, ... такая, что для любого $%n\ge1$% количество делителей числа $%S_n=a_1+\cdots+a_n$% равно $%a_n$%.

задан 28 Май '15 23:51

10|600 символов нужно символов осталось
10

Пусть $%n=p_1^{d_1}\ldots p_r^{d_r}$% -- каноническое разложение. Тогда количество натуральных делителей числа $%n$% находится по формуле $%\tau(n)=(d_1+1)\ldots(d_r+1)$%. Рассмотрим отношение $%\frac{\tau(n)}n=\prod\limits_{i=1}^r\frac{d_i+1}{p_i^{d_i}}$%. Для любого простого $%p$% последовательность $%\frac{d+1}{p^d}$% строго убывает при $%d\ge1$%. Если $%n=2^d$% является степенью двойки, и при этом $%n\ge4$%, то $%\frac{\tau(n)}n=\frac{d+1}{2^d}\le\frac34$%. В противном случае $%n$% имеет простой делитель $%p\ge3$%, и тогда $%\frac{d+1}{p^d}\le\frac2p\le\frac23$%, откуда следует, что $%\frac{\tau(n)}n\le\frac23$%. Таким образом, при всех $%n\ge3$% справедливо неравенство $%\tau(n)\le\frac34n$%.

Рассмотрим ориентированный граф, у которого множеством вершин является множество натуральных чисел, и от каждого $%n > 2$% проведено ориентированное ребро к вершине $%n-\tau(n) < n$%. Отсюда следует, что от каждой вершины можно по стрелкам пройти к $%1$% или $%2$%. Получается объединение двух деревьев. Легко видеть, что связная компонента вершины $%1$% конечна: она состоит из вершин $%1$%, $%3$%, $%4$%, $%5$%, $%7$%, $%8$%.

Рассмотрим дерево, содержащее вершину $%2$%. В ней имеются сколь угодно длинные пути по стрелкам, идущие в эту вершину. Действительно, поскольку $%n-\tau(n)\ge\frac{n}4$%, при проходе ребра происходит уменьшение числа не более чем в 4 раза, и если начать с числа $%2\cdot4^k$% (при $%k > 1$%), то мы придём по стрелкам в вершину $%2$% не менее чем за $%k$% шагов.

Теперь заметим, что наше дерево локально конечно. Действительно, из каждой вершины выходит одна стрелка (из $%2$% не выходит ни одной), а входит только конечное число стрелок, так как в $%n$% не могут входить стрелки из вершин $%>4n$%. Теперь можно применить лемму Кёнига и заключить, что в дереве имеется бесконечная ветвь вида $%2=S_1\gets S_2\gets S_3\gets\cdots\gets S_n\gets\cdots$%. Действительно, такая цепь строится по индукции: мы каждый раз выбираем такое ребро, с которого начинаются сколь угодно длинные цепи. Осталось положить $%a_n=S_n-S_{n-1}$%, где $%S_0=0$%.

Процесс построения такой цепи неконструктивен. Вообще говоря, бесконечных цепей может быть несколько. В данном случае при помощи компьютерных вычислений до некоторого момента (скажем, в пределах 1000) получается единственная цепь. Вот она: $%2,4,6,6,4,8,4,8,4,8,4,4,8,8,12,4,8,4,8,4,3,4,4,15,8,10,4,8,8,8,4,16$%, $%4,8,8,6,6,8,4,16,4,8,12,4,4,8,4,16,12,4,8,4,8,8,16,4,8,8,8,8,8,8,4,16$%, $%4,8,12,8,16,12,8,...$%.

Частичные суммы при этом равны $%2,6,12,18,22,30,34,42,46,54,58,62,70,78,90,94,102,106,114,118,121,125,129,144,152$%, $%162,166,174,921,182,190,194,210,214,222,230,236,242,250,254,270,274,282,294,298,302$%, $%310,314,851,847,330,342,346,354,358,366,374,390,394,1000,402,410,418,426,434,442$%, $%446,462,466,474,486,494,510,522,530,...$%.

Интересно было бы понять, есть ли тут какая-либо закономерность, а также есть ли другие бесконечные последовательности с таким свойством.

ссылка

отвечен 8 Июл '15 22:25

Закиньте это в OEIS обязательно

(8 Июл '15 23:02) knop

@knop: да, это интересная последовательность, а в OEIS её нет. Но я там не зарегистрирован. Может, Вам проще будет закинуть, если Вы это уже делали?

(8 Июл '15 23:14) falcao
1

Я тоже если и зарегистрирован, то очень давно, и забыл пароли-явки. Попробую написать знакомым, которые туда уже не одну последовательность добавили...

(9 Июл '15 12:00) knop

@knop: да, хорошо!

(9 Июл '15 17:26) falcao

@knop: спасибо! Это второй случай моего появления под псевдонимом Фалькао "в печати"! :)

(9 Июл '15 23:05) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

Мы обычно идем от начала к концу. Предположим, что мы будем идти от бесконечности к началу. Пусть очень большое число $%S_n$% и у этого числа найдем количество делителей, которое меньше чем это число и вычтем $%a_n$%, равное количеству делителей $%S_n$% и мы найдем $%S_{n-1}$% и далее вычтем $%a_{n-1}$%, равное количеству делителей $%S_{n-1}$% и так на $%n$%-м шаге мы придем к началу 1. Мы получили последовательность $%n$% чисел. Это $%n$% может быть сколь угодно большим в силу бесконечности натурального ряда чисел. Доказательства этого факта по методу математической индукции индукции.

ссылка

отвечен 31 Май '15 13:51

@Роман83: из Вашего рассуждения следует, что существуют сколь угодно длинные последовательности с требуемым свойством (правда, началом здесь может быть не только 1, а ещё и 2). Но это более слабое утверждение: бывает так, что сколь угодно длинные последовательности с каким-то свойством имеются, а бесконечной последовательности при этом не возникает. В качестве нетривиального примера можно назвать арифметические прогрессии из простых чисел.

(31 Май '15 14:00) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×650

задан
28 Май '15 23:51

показан
1907 раз

обновлен
10 Июл '15 0:27

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

по почте:

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

по RSS:

Ответы

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

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