Re: Factor

Another recent challenge was to implement a method to check for happy numbers.

“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).”

Many of the solutions listed are short, and this might qualify as a nice question to use when interviewing programmers. Here is one solution in Python from Wikipedia:

def is_happy(k):
    s = set()
    while k != 1:
        digits = [int(i) for i in str(k)]
        k = sum([i**2 for i in digits])
        if k in s:
            return False
        s.add(k)
    return True

We first need a way to compute the “sum of the squares of its digits”. We will be assuming all calculations are in base 10. One method is to use “mod 10” to calculate the last digit, then compute “div 10” and repeat until you’ve exhausted all digits (e.g., the number is zero). We will be using the /mod (“divmod”) word to compute both at once.

: squares ( n -- s )
    0 [ over 0 > ] [ [ 10 /mod sq ] dip + ] while nip ;

You can show this works (e.g., 125 = 1² + 2² + 5² = 30):

IN: scratchpad 125 squares .
30

There are two simple ways to detect a cycle. One involves keeping the “sum of the squares” in a set, checking each to see if its been seen before (like the Python example above). The other is similar to how you might detect a cycle in a singly linked list (also an occasional interview question): allocate two pointers and advance one twice as fast, if they ever point to the same object, it’s a cycle. I chose to implement the latter method.

: (happy?) ( n1 n2 -- ? )
    [ squares ] [ squares squares ] bi* {
        { [ dup 1 = ] [ 2drop t ] }
        { [ 2dup = ] [ 2drop f ] }
        [ (happy?) ]
    } cond ;

: happy? ( n -- ? )
    dup (happy?) ;

The happy numbers under 50 can be easily calculated:

IN: scratchpad 50 <iota> [ happy? ] filter .
V{ 1 7 10 13 19 23 28 31 32 44 49 }

We can use the math.primes vocabulary to check for “happy primes” under 200:

IN: scratchpad 200 <iota> [ [ happy? ] [ prime? ] bi and ] filter .
V{ 7 13 19 23 31 79 97 103 109 139 167 193 }

Using Factor’s support for large numbers, we can even check one of the large number claims that are made on the Wikipedia page:

“The palindromic prime 10^150,006 + 7426247 × 10^75,000 + 1 is also a happy prime with 150,007 digits…”

Waiting just a little while for the result (since its a rather large number), we see that it is indeed a happy number:

IN: scratchpad 10 150006 ^ 7426247 10 75000 ^ * 1 + + happy? .
t

The code for this is in my GitHub.