# Happy Numbers #93 How happy can you get? (was Re: \[QUIZ SOLU **URL:** \ **Category:** Ruby\ **Created:** [September 6, 2006, 6:10pm UTC](https://www.ruby-forum.com/t/happy-numbers-93-how-happy-can-you-get-was-re-quiz-solu/67774 "2006-09-06T18:10:28Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [September 6, 2006, 6:10pm UTC](https://www.ruby-forum.com/t/happy-numbers-93-how-happy-can-you-get-was-re-quiz-solu/67774/1 "2006-09-06T18:10:28Z")
On 9/5/06, Ken B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 B.'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/](http://talklikeaduck.denhaven2.com/) ---
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [September 6, 2006, 10:47pm UTC](https://www.ruby-forum.com/t/happy-numbers-93-how-happy-can-you-get-was-re-quiz-solu/67774/2 "2006-09-06T22:47:04Z")
“Rick DeNatale” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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… ---
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [September 6, 2006, 11:07pm UTC](https://www.ruby-forum.com/t/happy-numbers-93-how-happy-can-you-get-was-re-quiz-solu/67774/3 "2006-09-06T23:07:06Z")
On 9/6/06, Daniel M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > Of course it might just be a lack of patience on my part. > > 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. Rick DeNatale My blog on Ruby [http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/) ---
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [September 7, 2006, 2:47am UTC](https://www.ruby-forum.com/t/happy-numbers-93-how-happy-can-you-get-was-re-quiz-solu/67774/4 "2006-09-07T02:47:27Z")
“Rick DeNatale” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes: > On 9/6/06, Daniel M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > 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