For a positive integer k, let f1(k) be the square of the sum of the digits of k. Define fn+1 = f1∘fn . Evaluate f2007(22006).
Problem
Source:
Tags: function, logarithms, modular arithmetic, algebra unsolved, algebra
10.11.2010 15:23
WakeUp wrote: For a positive integer k, let f1(k) be the square of the sum of the digits of k. Define fn+1 = f1∘fn . Evaluate f2007(22006). Let n(x) the number of digits of x and s(x) the sum of digits of x. n(x)≤1+log10(x) and so s(x)≤9n(x)=9(1+log10x) and f(x)≤81(1+log10x)2 So f(22006)≤81(1+2006log102)2 ≤81(1+20063)2 <81⋅7002<108 f(f(22006))≤81(1+8)2<104 f(f(f(22006)))≤81(1+4)2=2025 f[4](22006)≤(1+9+9+9)2=784 f[5](22006)≤(6+9+9)2=576 f[6](22006)≤(4+9+9)2=484 f[7](22006)≤(3+9+9)2=441 and this process enters then a loop on 441 So we know that, from this point, s(f[n](22006))≤21 But 2^{2006}\equiv 4\pmod 9 and so it's clear that s(f^{[n]}(2^{2006}))\equiv 4,7\pmod 9 and so : s(f^{[n]}(2^{2006}))\in\{4,7,13,16\} \forall n\ge 7 And since : s(x)=4 \implies f(x)=16 whose sum of digits is 7 s(x)=7 \implies f(x)=49 whose sum of digits is 13 s(x)=13 \implies f(x)=169 whose sum of digits is 16 s(x)=16 \implies f(x)=256 whose sum of digits is 13 we get that f^{[n]}(2^{2006})\in\{169,256\} \forall n\ge 10 It remains to look at the values modulus 9 to get that f^{[2p]}(2^{2006})\equiv 4\pmod 9 while f^{[2p+1]}(2^{2006})\equiv 7\pmod 9 And so \boxed{f^{[2007]}(2^{2006})=169} since 2007 is odd