Квадрат суммы цифр

[Xenia1996]

Для каждого натурального n функция $f_{1}(n)$ определена как квадрат суммы цифр числа n (в десятичной записи).
Определим $f_{k+1}(n)=f_{1}\circ f_{k}(n)$
Вычислить $ f_{2011}(2^{2012})$

[Crutoy Pazan]

что значить кружочек по середине?

[Xenia1996]

Crutoy Pazan в сообщении #420036 писал(а):

что значить кружочек по середине?

$f(g(x))=f\circ g(x)$
Если Вы - Crutoy Pazan, Вы должны это знать!

[caxap]

$169$ ?

[Xenia1996]

caxap в сообщении #420041 писал(а):

$169$ ?

Так-то оно так, но вот почему?

[caxap]

$(2+5+6)^2=169$, $(1+6+9)^2=256$, а с первыми членами я сжульничал -- посчитал на компутере

[Xenia1996]

caxap в сообщении #420051 писал(а):

$(2+5+6)^2=169$, $(1+6+9)^2=256$, а с первыми членами я сжульничал -- посчитал на компутере

Зря! Там очень красивая закономерность прослеживается.

[ИСН]

Все выкатываются либо туда, либо на 81, кроме тех, что попали на 1?

[Xenia1996]

ИСН в сообщении #420059 писал(а):

Все выкатываются либо туда, либо на 81, кроме тех, что попали на 1?

Скажем так:

Существуют лишь три типа зацикливаний:

1) .....1, 1, 1, 1.....
2) .......169, 256, 169, 256, ..........
3)............81, 81, 81, .............

Тип зацикливания зависит от остатка при делении на 9.

[Crutoy Pazan]

красивой закономерности нет, доказать можно только рассмотрев все однозначные числа до девяти, что дарамдаш не очевидно

[Xenia1996]

Crutoy Pazan в сообщении #420064 писал(а):

почему?-а если число однозначно?- тогда все композиции функций будут равны ему

Нет. Например, $f_1(8)=64, f_2(8)=100$

[Crutoy Pazan]

аааа-ну тогда все понятно, но вот догадаться про остатки....

За флуд Crutoy Pazan заблокирован на две недели. / GAA, 6.03.2011

[ИСН]

Ну, это очевидный инвариант в задачах такого рода, так что - - -

[Sonic86]

Чего-то не могу доказать, что $f_{+ \infty}(2^{3k}) = 1$ А вроде бы верно

А все остальные вроде сваливаются в другой цикл.

В 81 степени двойки, очевидно, никогда не свалятся. По признаку делимости на 3.

-- Пн мар 07, 2011 03:07:37 --

Не, все просто:
Поскольку $n \equiv s(n) \pmod 9$, где $s(n)$ - сумма цифр $n$, то для отображения $f: n \to s^2$ корректно определено отображение по модулю 9 $F:n \to n^2$. У него тоже 3 предельных цикла: 0; 1; и $4 \to 7 \to 4$ - эти циклы взаимно однозначно соответствуют циклам $f$. Значит, если $F_{+ \infty}(2^m) = 1$, то и $f_{+ \infty}(2^m)=1$, если же $F_k(2^m)$ впадает в цикл длины 2, то и $f_k(2^m)$ впадает в цикл длины 2.
Теперь очевидно, что $F_k(2^m) = 2^{m2^k} \pmod 9 = 1$ тогда и только тогда, когда $3|m$ (поскольку $\varphi (9) = 6$ и 2 - образующая по модулю 9).
$3 \not |2012$, значит все понятно....