From: Jacob Fugal <lukfugl@...>
Date: 2006-09-07T01:01:44+09:00
Subject: Re: Happy Numbers (#93)

WARNING: Just more math geeking ahead. If you don't care for this
section of the thread, just skim on past... :)

On 9/4/06, Michael Ulm <michael.ulm@isis-papyrus.com> wrote:
> 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

A nitpick, it should be:

  u (1 - u) + v * (b - v) + w * (b^2 - w) >= u (1 - u) + b^2 - 1

rather than a strict less than. Doesn't affect the outcome of the
proof, since the following inequality is still correct. In the case
where v = 0 and w = 1

  u (1 - u) + v * (b - v) + w * (b^2 - w)
  = u (1 - u) + 0 * (b - 0) + 1 * (b^2 - 1)
  = u (1 - u) + b^2 - 1

For those following along at home, it might be hard to see why it must
be less in all other cases -- I had a hard time with it for a while.
Imagine v > 0. v * (b - v) > 0 since b > v. So that term can only make
the expression larger.

Also imagine w > 1.

  w * (b^2 - w)
  = w * b^2 - w^2
  = b^2 + (w - 2) * b^2 + b^2 - w^2
  = b^2 + (w - 2) * b^2 + (b - w) (b + w)

Since b > w, b - w > 0. Also, b + w > b >= 2. So (b - w) (b + w) >= 2 > 1:

  w * (b^2 - w) > b^2 + 1 + (w - 2) * b^2

Now since w >= 2, (w - 2) * b^2 >= 0, and we have:

  w * (b^2 - w) > b^2 + 1

And that term can only increase as well. So as Michael showed, g(x) <
x for all x with three or more digits in the respective base.

Jacob Fugal