From: Sander Land <sander.land@...>
Date: 2006-09-02T07:02:34+09:00
Subject: Re: Happy Numbers (#93)

On 9/1/06, Hans Fugal <fugalh@xmission.com> wrote:
> Paul Lutus wrote:
> > Peter Hickman wrote:
> >
> >> Problem is that from the quiz it states that you either get a 1 or an
> >> infinite loop and that an unhappy number is "obvious". Which is a sign
> >> that something has not been explained clearly. Given that the Wolfram
> >> page was clearer than the quiz at to what constitutes happy don't be
> >> surprised if some people go off down the wrong path.
> >
> > As I understand the Wolfram article, an unhappy number never hits 1 as a
> > result, whereas a happy number eventually hits 1:
>
> What you have described here is the halting problem. Good luck with that.

Something which reduces to HP is not equivalent to HP, only if you can
reduce HP to this problem is it equivalent to HP/undecidable.

> > "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?

Basic math does.
number of length 100 : 99999...., next step = 100*9^2 = 8100, i.e.
large numbers always go down _a lot_, and therefore cannot be part of
a cycle.
Proving this for n >= 243 (or even smaller n) is left as an exercise
for the reader ;)