Решение задачи 510

Условие:
Дана бесконечная последовательность натуральных чисел, в которой каждое число, начиная со второго, равно количеству делителей предыдущего (включая единицу и само это число). В последовательности есть хотя бы четыре попарно различных числа, но нет двух полных квадратов подряд. Докажите, что она содержит степень четверки.

Решение:
Через d(n) обозначим количество делителей числа n. Некоторые нетрудные наблюдения:

1) После единицы идет единица.
2) После двойки идет двойка.
4) Первый элемент последовательности больше двух.
3) Если n больше двух, то d(n) меньше n.
4) Если d(n) = p (простое), то n = q^{p - 1}, где q -- простое. Следует из основной теоремы арифметики и подсчета числа делителей.
5) Натуральное число является полным квадратом тогда и только тогда, когда у него нечетное число делителей. Следует из основной теоремы арифметики и подсчета числа делителей.

Из вышесказанного следует, что последовательность, начиная с первого элемента, строго убывает, пока не стабилизируется на двойке. Рассмотрим первую двойку, перед ней стоит какое-то простое число p > 2. Перед p есть член последовательности, так как должны быть хотя бы четыре попарно различных числа. По пункту 4, перед p стоит q^{p - 1}, причем p не равно двойке, значит p - 1 четное число, то есть q^{p - 1} полный квадрат. Перед q^{p - 1} есть член последовательности. По условию он не может быть полным квадратом, значит, он не квадрат и тогда q^{p - 1} четное число, то есть q = 2. Значит q^{p - 1} это 2 в четной степени, то есть степень четверки. ЧТД.