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!

Comments

  1. If x has n digits, then

    f(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.

    ReplyDelete
  2. :) Nice solution. I so wish blogger had tex support :(
    Thanks.

    ReplyDelete

Post a Comment