Happy Numbers

Here's one that I saw on-line recently in an article on F#, Microsoft's function language (there was actually a nice flame war going on on the site with respect F# vs. Mathmatica's language M). Anyway, from Wikipedia, here's the definition of a happy number:

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers[1]).

I actually used this recently as a programming interview question and was surprised how well it worked out. It's easy enough to work out in 15-20 minutes (or at least to get most of the main ideas), it contains both math and string work, and you need either a hash or a set as a data structure to contain the visited numbers.

The code itself is relatively straightforward. If we start down in the main part of the program, you'll see that we create an array to save the happy numbers and then loop to find all of the happy numbers less than or equal to 500 saving them in the array. Finally we print them out.

The function happy_number? takes a single parameter n and determines if it is a happy number. First, we create a hash table to save values that we've seen before so that we can detect loops. Then we start a loop that goes until we converge on 1 or until we detect a loop. The heart of the program is the next line which (reading the methods left to right) a) converts n to a string, b) creates an array of the digits as strings using split, and finally uses inject to sum the squares of the digits (appropriately converted back to integers). If we detect a loop, the value that we generated is already in the visited hash, then we return false. If not, we add v to visited and set n to v for the next round. If we exit the loop with a 1, we'll return true.

Here's the code ...

# A function that determines whether a number passed in is a happy number or not. From Wikipedia:
#
# A happy number is defined by the following process. Starting with any
# positive integer, replace the number by the sum of the squares of its digits,
# and repeat the process until the number equals 1 (where it will stay), or it
# loops endlessly in a cycle which does not include 1. Those numbers for which
# this process ends in 1 are happy numbers, while those that do not end in 1
# are unhappy numbers (or sad numbers[1]).
#
def happy_number?(n)

    # visited is a Hash that will keep track of numbers we've already found.
    visited = {}

    # Loop until we converge on 1 (or exit in the middle of the loop if 
    # we find a value that we've already visited.
    while n != 1

        # Convert n to a string, then split to get an array of characters.  Use
        # inject to calculate the sum of their squares and put it 
        # in v.
        v = n.to_s.split(//).inject(0) { |sum, digit| sum += digit.to_i ** 2 }

        # If we've already seen this value v, then we're in a
        # loop and should return flase.
        return false if visited.has_key? v
            
        # Add v to the visited list
        visited[v] = true

        # Set n to v for next round.
        n = v
    end

    # n is 1, so it's a original value was a happy number.
    return true
end

# Place where we'll store the happy numbers
happy_numbers = []

# Find and save the happy numbers up to 500.
1.upto(500) do |i|
    happy_numbers << i if happy_number?(i) == true
end

# Print out the happy numbers that we found.
happy_numbers.each { |n| puts "Happy number #{n}" }

If you have questions or comments, be sure to let me know.