[QUIZ] Happy Numbers #93 How happy can you get? (was Re: [QUIZ SOLUTION] Happy Numbers (#93) -- nondecreasing digits)

...

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

···

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:

--
Rick DeNatale

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

"Rick DeNatale" <rick.denatale@gmail.com> writes:

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"

That conjecture is false.

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

Probably.

one of the happiest 5 digit base 10 numbers is 78999, with 8 steps
after 1287 probes

I propose that the number (10**78999 - 1)/9, that is, the number made
by:

("1" * 78999).to_i

takes 9 steps. I strongly doubt that this method is the most
efficient way to get to a 9-step number; as a trivial adjustment, the
number

  ("1" * 24 + "9" * 975).to_i

is also a 9-step number. However, if 78999 is the smallest 8-step
happy number, the smallest 9-step happy number must have at least
(78999/81.0).ceil digits. Small wonder that you didn't find one...

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]

"Rick DeNatale" <rick.denatale@gmail.com> writes:

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

That conjecture is false.

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

Probably.

> one of the happiest 5 digit base 10 numbers is 78999, with 8 steps
> after 1287 probes

I propose that the number (10**78999 - 1)/9, that is, the number made
by:

("1" * 78999).to_i

takes 9 steps.

Right you are. I never really beleived my conjecture, just wanted to
stir up thoughts.

I strongly doubt that this method is the most
efficient way to get to a 9-step number; as a trivial adjustment, the
number

  ("1" * 24 + "9" * 975).to_i

is also a 9-step number.

I think you lost me on that step.

However, if 78999 is the smallest 8-step
happy number, the smallest 9-step happy number must have at least
(78999/81.0).ceil digits. Small wonder that you didn't find one...

Efficient or not, it would seem that generating large happy numbers by
construction beats the hell out of trying to find them.

···

On 9/6/06, Daniel Martin <martin@snowplow.org> wrote:
--
Rick DeNatale

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

"Rick DeNatale" <rick.denatale@gmail.com> writes:

I strongly doubt that this method is the most
efficient way to get to a 9-step number; as a trivial adjustment, the
number

  ("1" * 24 + "9" * 975).to_i

is also a 9-step number.

I think you lost me on that step.

Sorry; I didn't show all my work.

irb(main):037:0> 78999.divmod(81)
=> [975, 24]
irb(main):038:0> 81 * 975 + 24
=> 78999

However, if 78999 is the smallest 8-step
happy number, the smallest 9-step happy number must have at least
(78999/81.0).ceil digits. Small wonder that you didn't find one...

Efficient or not, it would seem that generating large happy numbers by
construction beats the hell out of trying to find them.

Probably. I'm reasonably certain that it can be shown that the
smallest 9-step number feeds into the smallest 8-step number, but I'm
not certain about that. I'm also a bit unclear on how to generate
them by construction in an efficient manner to make sure I get them
all. (consider that adding a 0 anywhere in a n-step happy number makes
another n-step happy number; this adds wrinkles I don't want to think
about)

However, if I had hit on the idea of generating happy numbers by
construction earlier in the quiz, I might have spent Saturday working
that out. Oh well.

Incidentally, I'm pretty sure now that the smallest 9-step number is:

("3788" + "9" * 973).to_i

with 977 digits. Note that:

irb(main):020:0> ("3788" + "9"*973).split(//).inject(0){|s,x|s+(x.to_i**2)}
=> 78999

···

On 9/6/06, Daniel Martin <martin@snowplow.org> wrote:

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]