Странное число "8"
Back Home Up Next

адача 2. Странное число 8. Первый член последовательности равен любому натуральному числу, а каждый последующий её член равен сумме квадратов цифр её предыдущего члена. Доказать, что все такие последовательности периодичны, длины их периодов равны единице или восьми. В первом случае в периоде находится единица, а во втором - имеется ровно восемь различных периодов длины восемь и все они содержат один и тот же набор чисел. Найти эти периоды.

Решение. Пусть sumsqu(n) есть сумма квадратов десятичных цифр натурального числа n.

1. Покажем, что:

“Если n>999, то sumsqu(n)<n.”                                                    (4)

Пусть число n>999 и содержит k цифр. Тогда имеют место соотношения

sumsqu(n) ³ k × 92 = 81 × k,           10k-1 £ n < 10k.                                  (5)

Но из n>999 следует, что k³4 и, следовательно, 81 × k < 10k-1. Этот факт вместе с (5) и доказывает (4). Иными словами, члены рассматриваемых последовательностей убывают по крайней мере до тех пор, пока не становятся меньше 1000.

2. Отправляясь от произвольного числа n, не меньшего 1000, за конечное число шагов мы получим член последовательности, уже меньший 1000. Все остальные члены этой последовательности также будут меньше 1000. Поэтому период её может начинаться только с числа n£999 и, следовательно, достаточно исследовать лишь все последовательности, начинающиеся с n£999. А это уже простая переборная задача для компьютера.

3. Ниже приведены рекурсивные программы-функции sumsqu(), itera() и головная программа-функция massi(), формирующие сведения о периодах в виде массива b размером 2´9. Элемент b0,j массива b - это наименьшее из начальных чисел последовательностей, для которых период начинается с b1,j(j = 0, 1, ..., 8):

Дадим краткое описание программ:

Рекурсивная функция sumsqu(n) по натуральному числу n находит и возвращает число, равное сумме квадратов цифр n. Декомпозиция задачи организована по цифрам n, начиная с младшего разряда и далее. Базой рекурсии являются однозначные числа. Количество рекурсивных вызовов равно разрядности n.

Функция itera(n, v) рекурсивным образом итерирует действия, реализуемые функцией sumsqu(n). По заданному n она возвращает число, с которого начинается период. Делается это так. 
Получаемые по
sumsqu(n) числа отмечаются в массиве v. Получение очередного числа, уже отмеченного в v, считается индикатором останова вычислений, то есть базой рекурсии. Количество рекурсивных вызовов зависит от начального значения n.

Головная программа massi(fr) запускает последовательные вычисления по itera(n) для всех n от 1 до fr. При обращении к massi(fr) значение параметра fr должно быть равно 999. При вычислениях результат формируется и возвращается в виде ранее описанной матрицы b.

4. Элемент b0,j матрицы b указывает наименьшие из начальных чисел последовательностей, для которых период начинается с b1,j(j = 0, 1, ..., 8). Построение самих последовательностей требует дополнительных средств. Таковыми могут быть рекурсивная функция conse() и головная программа-функция mconse(m):

Опишем эти функции.

Рекурсивная функция conse(n, v, w, k) для данного n строит начало последовательности по такой схеме: “предпериод + период + первый элемент следующего периода”. v, w и k - вспомогательные параметры. Основа действий, реализуемых по itera() и conse(), одна и та же. Но по conse() формируемые члены последовательности не только отмечаются в массиве v, но и дополнительно запоминаются в массиве w. Этот массив и является результатом вычислений. Рекурсия организована по вспомогательному параметру k. Получение очередного числа, уже отмеченного в v, считается индикатором останова вычислений, то есть базой рекурсии. Количество рекурсивных вызовов зависит от начального значения n.

Функция mconse(m) проводит вычисления по conse(n, v, w, k) для всех значений 
n
= b0,j (j = 0, 1, ..., cols(b)-1) из матрицы
b. Получаемые фрагменты последовательностей запоминаются в виде строк вспомогательной матрицы ma размером 9´(m+1), которая затем и возвращается в качестве результата вычислений. Обращение к функции вида mconse(999) и просмотр выведенной матрицы показывает, что все её столбцы после 13-го заполнены нулями. Поэтому реальная информация о последовательностях и их периодах содержится в подматрице со столбцами от 0 до 13 полученной матрицы. Следовательно, можно проводить обращение к mconse(m) с параметром m=13. И вот что из этого получается:

Жирными цифрами здесь отмечены элементы периодов соответствующих последовательностей. Анализ этой таблицы показывает, что все последовательности исходной задачи периодичны, длины их периодов равны единице или восьми. В первом случае в периоде находится единица, а во втором - имеется ровно восемь различных периодов, все они имеют длину восемь и содержат один и тот же набор чисел: {4, 16, 37, 58, 89, 145, 42, 20}. Иными словами, все утверждения теоремы доказаны полностью. Более того, если зафиксировать любой из периодов, например (4, 16, 37, 58, 89, 145, 42, 20), то нетрудно видеть, что все другие периоды получаются из него последовательными циклическими перемещениями элементов из начала в конец.

Home Содержание Схемы ООД Доска объявлений Поиск