# Happy Numbers (#93)

**URL:** <https://www.ruby-forum.com/t/happy-numbers-93/67803>\
**Category:** Ruby\
**Created:** [September 6, 2006, 10:19pm UTC](https://www.ruby-forum.com/t/happy-numbers-93/67803 "2006-09-06T22:19:00Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**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:19pm UTC](https://www.ruby-forum.com/t/happy-numbers-93/67803/1 "2006-09-06T22:19:00Z")

</div>

Here’s my solution.

There are arguments which control what the main program does.

-b , or --base is an integer giving the base - this defaults to 10  
-t, or --time-limit is an integer giving the number of seconds to run  
looking for the happiest number in a give base. This defaults to 600  
seconds (10 minutes)  
–levels causes an unlimited time run which prints a “happiest” number  
of numbers with the same number of digits in the base. Use break to  
stop this.

I cache both unhappy numbers and successful paths so that I can  
short-circuit things. Not a small memory solution.

== happynumber.rb ==  
#! /usr/local/bin/ruby

class Integer

```
    def Integer.reset_happiness_cache
            # Integer#to_s(base) works up to a base of 36
            @@cached_unhappy_ints = Array.new(37) {|i| Hash.new }
            @@cached_happiness_paths = Array.new(37) {|i| {1 => 

```

[1]}}

```
            self.cache_unhappy([0, 4, 16, 20, 37, 42, 58, 89, 145], 

```

1. 

```
end

def Integer.show_hc
        puts "unhappies = #{@@cached_unhappy_ints[10].inspect}"
        puts "happies = #{@@cached_happiness_paths[10].inspect}"
end

def squared
        self * self
end

def sum_squares_of_digits(base=10)
        sum = 0
        to_s(base).each_byte do |b|
                sum += (b.chr.to_i(base)).squared
        end
        sum
end

def path_to_happiness(base=10,seen=[])
        return nil if Integer.known_unhappy?(self, base)
        return Integer.cache_unhappy([self], base) if

```

seen.include?(self)  
known\_path = Integer.known\_happiness\_path(self, base)  
return known\_path.dup if known\_path  
rest\_of\_the\_way =  
sum\_squares\_of\_digits(base).path\_to\_happiness(base,seen.dup \<\< self)  
if rest\_of\_the\_way  
ans = rest\_of\_the\_way.unshift(self)  
return Integer.cache\_happiness\_path(ans,  
base).dup  
else  
Integer.cache\_unhappy([self], base)  
return nil  
end  
end

```
    def Integer.known_unhappy?(int, base)
            @@cached_unhappy_ints[base][int]
    end

    def Integer.known_happiness_path(int, base)
            @@cached_happiness_paths[base][int]
    end

    def known_happy?(base)
            Integer.known_happiness_path(self, base)
    end

    def Integer.cache_unhappy(integers, base)
            integers.each do | n |
                    @@cached_unhappy_ints[base][n] = true
            end
            nil
    end

    def Integer.cache_happiness_path(path, base)
            @@cached_happiness_paths[base][path[0]] = path.dup
            path
    end

    def happy?
            !self.path_to_happiness.nil?
    end

    def happiness
            path = path_to_happiness
            path_to_happiness ? path_to_happiness.length : 0
    end

    reset_happiness_cache

```

end

#generates all numbers in the given range whose digits are in  
#nondecreasing order. the order in which the numbers are generated is  
#undefined, so it’s possible for 123 to appear before 23, for  
#example.

# Thanks to Ken B. for this idea, which I generalized to an

arbitrary base

# 

def nondec\_digits(range,base=10,&b)  
yield 0 if range.first\<=0  
(1…base-1).each { |x|  
nondec\_digits\_internal(x,x,range,base,&b) }  
end

def nondec\_digits\_internal(last,accum,range,base,&b)  
(last…base-1).each do |x|  
iaccum=accum\*base+x  
b.call(iaccum) if range.nil? || range.include?(iaccum)  
nondec\_digits\_internal(x,iaccum,range,base,&b) if  
iaccum \<= range.last  
end  
end

# enumerate all numbers whose representation in base _base_

# has increasing digits.

def nondec\_numbers(base, &b)  
start = 0  
ten\_in\_base = “10”.to\_i(base)  
stop = ten\_in\_base  
while true  
nondec\_digits((start…stop-1), base, &b)  
start = stop  
stop \*= ten\_in\_base  
end  
end

def happiest\_in\_range(range, base=10)  
happiest = 1  
max\_path\_length = 1  
probes = 0  
nondec\_digits(range,base) do |i|  
probes += 1  
path = i.path\_to\_happiness(base)  
if path && path.length \> max\_path\_length  
happiest = i  
max\_path\_length = path.length  
end  
end  
[happiest, max\_path\_length, probes]  
end

def base\_levels(base=10)  
ten\_in\_base = “10”.to\_i(base)  
start = 0  
base\_n = ten\_in\_base  
n = 1  
while true  
h, pl, probes = happiest\_in\_range((start…base\_n-1),  
base)  
puts “one of the happiest #{n} digit base #{base}  
numbers is #{h.to\_s(base)}, with #{pl} steps after #{probes} probes”  
start = base\_n  
n += 1  
base\_n \*= ten\_in\_base  
end  
end

# return the happiest number that can be found in time\_limit seconds

def happiest(time\_limit=60, base=10)  
time\_to\_stop = Time.now + time\_limit  
happiest = 1  
max\_path\_length = 1  
probes = 0  
nondec\_numbers(base) do |i|  
break if Time.now \> time\_to\_stop  
probes += 1  
path = i.path\_to\_happiness(base)  
if path && path.length \> max\_path\_length  
happiest = i  
max\_path\_length = path.length  
end  
end

```
    puts "happiest base #{base} number found in #{time_limit}

```

seconds in #{probes} probes"  
puts “was #{happiest.to\_s(base)} which has a happiness of  
#{max\_path\_length}”  
end

require ‘optparse’  
opts = OptionParser.new  
base = 10  
time\_limit = 600 # default to 10 minutes  
happiest\_test = true  
opts.on(“-b”, “–base VAL”, Integer) {|val| base = val}  
opts.on(“–levels”) {happiest\_test = false}  
opts.on(“-t”, “–time-limit VAL”, Integer) {|val| time\_limit = val}  
opts.parse(ARGV)  
happiest(time\_limit, base) if happiest\_test  
base\_levels(base) unless happiest\_test

–  
Rick DeNatale

My blog on Ruby  
[http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/)