Sum of 2001 powers of digits
Source: Problems on Algorithms (Ian Parberry and William Gasarch)
Problem:
Let f be a function which takes a number x (number with say n digits, digit i represented by d_i) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001. Show that for any x, the set {f(x), f(f(x)), f(f(f(x))),..} is finite.
Update (31 January 2011)
Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!
Problem:
Let f be a function which takes a number x (number with say n digits, digit i represented by d_i) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001. Show that for any x, the set {f(x), f(f(x)), f(f(f(x))),..} is finite.
Update (31 January 2011)
Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!
If x has n digits, then
ReplyDeletef(x)\leq n*9^2001 \leq 10^{n-1} \leq x
where second inequality holds for all sufficiently large n.
Thus, there exists an integer N such that f(x)\leq x for all x>N.
This tells us that for any iterate i, f^{(i)}(x) is upper bounded by max{sup_{y\leq N} f(y), x} which is a finite number that depends on x.
:) Nice solution. I so wish blogger had tex support :(
ReplyDeleteThanks.