On 9/5/06, Ken Bloom <kbloom / gmail.com> wrote:

> Since the order of digits in the number doesn't matter, here's code to
> generate digits whose numbers are in nondecreasing order. This makes the
> "happiest number" test finish almost instantly when the numbers are
> generated this way:

...

I've been playing with this since I first saw it last week.  I've got
a solution which works for arbitary bases, at least between 3 and 36.
Note that ALL base 2 numbers are happy.

I still need to clean up the ruby code before I post my solution,
since I've got a lot of junk in there trying recreational math
'experiments'.

One think that I've noticed is that with increasing numbers of digits,
plateaus in the length of the 'path to happiness' are relatively
quickly reached. I'll give some results for various bases at the end
of this note.

Now, I've got a supposition that eventually a maximum level of
happiness is reached for any given base.  It seems that for numbers
with n digits in base b, the maximum for the next number on the 'path
to happiness' is:

     n*(base-1)**2
and that the maximum number of digits of the next step is therefore:

     1+LOGb(n*(base-1)**2) = 1 + LOGb(n) + 2*(LOGb(base-1))
which is less than
   1 + LOGb(n) + 2*(LOGb(base)) = 1 + lLOGb(n) + 2

    so the number of digits in the next step is no more than

    3 + LOGb(n)

and in two steps we get no more than:

    6 + LOGb(3+LOGb(n)) digits

Now, I think that this means that for increasing n, it gets harder and
harder not to stay out of a number which is less happy than the
happiest lower number below an arbitrary n-digit number.  I haven't
been able to prove that though.

Here are some results from my code for various bases.  Do these look
like what others are seeing?  Has anyone uncovered a base 10 number
which is happier than 8 steps to 1?  Unless my code has a bug in it'
maybe I should state DeNatale's conjecture which is "There is a
maximum happiness for numbers expressed in a base > 2"

Of course it might just be a lack of patience on my part.

This is the result of running a search for the happiest number with a
given number of digits in various bases.  The number of probes is the
number of test numbers generated by Ken Bloom's nondec_digits method,
which I generalized to support using an arbitrary base

rick@frodo:/public/rubyscripts$ ./happynumbers.rb -b8
one of the happiest 1 digit base 8 numbers is 1, with 1 steps after 1 probes
one of the happiest 2 digit base 8 numbers is 33, with 4 steps after 28 probes
one of the happiest 3 digit base 8 numbers is 456, with 6 steps after 84 probes
one of the happiest 4 digit base 8 numbers is 1266, with 6 steps after
210 probes
one of the happiest 5 digit base 8 numbers is 11157, with 6 steps
after 462 probes
one of the happiest 6 digit base 8 numbers is 111277, with 6 steps
after 924 probes
one of the happiest 7 digit base 8 numbers is 1111166, with 6 steps
after 1716 probes
one of the happiest 8 digit base 8 numbers is 22777777, with 7 steps
after 3003 probes
one of the happiest 9 digit base 8 numbers is 124677777, with 7 steps
after 5005 probes
one of the happiest 10 digit base 8 numbers is 1115677777, with 7
steps after 8008 probes
one of the happiest 11 digit base 8 numbers is 11112777777, with 7
steps after 12376 probes
one of the happiest 12 digit base 8 numbers is 111114677777, with 7
steps after 18564 probes
./happynumbers.rb:50:in `sum_squares_of_digits': Interrupt

rick@frodo:/public/rubyscripts$ ./happynumbers.rb -b10
one of the happiest 1 digit base 10 numbers is 1, with 1 steps after 1 probes
one of the happiest 2 digit base 10 numbers is 19, with 5 steps after 45 probes
one of the happiest 3 digit base 10 numbers is 356, with 7 steps after
165 probes
one of the happiest 4 digit base 10 numbers is 1112, with 7 steps
after 495 probes
one of the happiest 5 digit base 10 numbers is 78999, with 8 steps
after 1287 probes
one of the happiest 6 digit base 10 numbers is 378999, with 8 steps
after 3003 probes
one of the happiest 7 digit base 10 numbers is 1188899, with 8 steps
after 6435 probes
one of the happiest 8 digit base 10 numbers is 11279999, with 8 steps
after 12870 probes
one of the happiest 9 digit base 10 numbers is 111259999, with 8 steps
after 24310 probes
one of the happiest 10 digit base 10 numbers is 1111169999, with 8
steps after 43758 probes
one of the happiest 11 digit base 10 numbers is 11111179999, with 8
steps after 75582 probes
one of the happiest 12 digit base 10 numbers is 111111159999, with 8
steps after 125970 probes
./happynumbers.rb:168:in `nondec_digits_internal': Interrupt

rick@frodo:/public/rubyscripts$ ./happynumbers.rb -b16
one of the happiest 1 digit base 16 numbers is 1, with 1 steps after 1 probes
one of the happiest 2 digit base 16 numbers is 8d, with 12 steps after
120 probes
one of the happiest 3 digit base 16 numbers is def, with 14 steps
after 680 probes
one of the happiest 4 digit base 16 numbers is 1aee, with 14 steps
after 3060 probes
one of the happiest 5 digit base 16 numbers is 11eee, with 14 steps
after 11628 probes
one of the happiest 6 digit base 16 numbers is 1115ff, with 14 steps
after 38760 probes
one of the happiest 7 digit base 16 numbers is 11126ff, with 14 steps
after 116280 probes
one of the happiest 8 digit base 16 numbers is 111119ee, with 14 steps
after 319770 probes
./happynumbers.rb:44:in `squared': Interrupt

-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/