On 9/4/06, Michael Ulm <michael.ulm / isis-papyrus.com> wrote:
> Actually, it is possible to show that for any three digit number
>
> g(x) < x.
>
> This holds in any base. The proof:
>
> Let the base be  b > 1, and the number x be
> x = u + b * v + b^2 * w,
> with 0 <= u, v, w < b, and w > 0.
> Then
>
> x - g(x) = u + b * v + b^2 * w - (u^2 + v^2 + w^2)
>   = u (1 - u) + v * (b - v) + w * (b^2 - w)
>   > u (1 - u) + b^2 - 1
>   > (b - 1) (2 - b) + b^2 - 1 = 3 * (b - 1) > 0

Cool, thanks.

I had suspected as much, but didn't want to try and prove it. The
proof for x >= 1000 (or x >= b ** 3, for arbitrary base) came to me
rather intuitively, so that's why I chose that one as a loose upper
bound.

Jacob Fugal