On 9/1/06, Hans Fugal <fugalh / xmission.com> wrote:
> Paul Lutus wrote:
> > "Unhappy numbers have eventually periodic sequences of s(sub)i which never
> > reach 1."
>
> And what stops it from being a 1x10^50 length period, or any arbitrary
> length?

The period cannot be any larger than 1000. The largest period is
probably quite a bit smaller than this, but this is a upper bound.
Why?

Some definitions, first.

Let's define g(x) as the function that takes a number to it's
successor. For example, g(42) = 4^2 + 2^2 = 20.

For a variable x, we will denote the result of applying our function
as x'. That is, x' = g(x).

Let Mi = 10^i - 1 for all i. For example, M4 = 9999. Each Mi is the
number made up of i nines. Mi' is then 81 * i.

Let Qi = { x | M(i-1) < x <= Mi }. For example, Q4 is the range of
integers from 1000 to 9999. It's easy to see that the union of all
Qi's cover the natural numbers and that they are all disjoint. So the
set of all Qi's is a partitioning of the natural numbers.

For each x in Qi, it is easy to see that x' <= Mi'.

Now, take any i >= 4. For all x in Qi, x' <= Mi' = 81 * i. But 81 * i
< 10^(i-1) (see below), so 81 * i <= M(i-1), and x' <= M(i-1) for all
x in Qi. But since x > M(i-1) by our choice, we know that x' < x. This
is true for *all* x > 999.

So, for those of you glossing over the math, the conclusion is that
applying the "happy function" to any number greater than or equal to
1000 will necessarily result in a smaller number.

Since the sequence can't loop if we're constantly decreasing (until we
get down to 999 or less), none of the numbers in a period can be
greater than 999 -- there's no way to get back *up* to any of those
numbers.

So, for any loop resulting from a number, the space of numbers liable
to be in that loop is no larger than 1000 number (0 through 999). So
no loop can have a period greater than 1000.

Jacob Fugal