С написанным на доске числом производят следующее действие. Каждую его цифру возводят в квадрат, все результаты суммируют и результат выписывают на доску вместо исходного числа. Так продолжается сколько угодно раз. Опишите алгоритм, определяющий, можно ли таким образом получить из начального натурального числа N заданное натуральное число M? Обоснуйте конечность разработанного алгоритма.
берем каждую цифру, возводим в квадрат, суммируем цифры, если равно числу M-конец, иначе уже это число берем каждую цифру, возводим квадрат, и тд
А если уже больше- значит нельзя. Это же очевидно.
В данной задаче могут возникать последовательности разной длины, но в итоге либо получаем значение M, либо зацикливаемся.
К примеру:
N = 3
M = 4
3 9 81 65 61 37 58 89 145 42 20 4 = M.
N = 4
M = 5
4 16 37 58 89 145 42 20 4. - Cicle -
N = 123456
M = 5
123456 91 82 68 100 1 1. - Cicle -
N = 951
M = 5
951 107 50 25 29 85 89 145 42 20 4 16 37 58 89. - Cicle -
В первом случае на 11-ом шаге получается искомое число.
Во втором — после 8-ого шага появилось то же число, что было в начале = зациклились…
В третьем — после пятого шага будет получаться только 1 = зациклились…
В четвёртом — на 14 шаге получаем число, которое было ранее получено на шестом = зациклились…
Данные последовательности не очень большие.
Я провёл испытание для всех чисел от 1 до 1 миллиона.
В результате получилось, что самая длинная последовательность составила всего 20 шагов!
⇢