Monday, 5 July 2010

Happy numbers

Consider the sequence obtained by summing the squares of the digits of a number and then repeating with the result. If this sequence ends with the number one then the numbers in the sequence are Happy Numbers.

One of the challenges on Rosetta code is to compute the first eight Happy Numbers. The current F# solution weighs in at 26 lines of code. Let's see if we can do better...

We begin by writing a next function that computes the next happy number after the given number:

> let rec next (m: Set<_>) n i = if i=1 then n else if m.Contains i then next Set.empty (n+1) (n+1) else Seq.sumBy (fun d -> pown (int d - int '0') 2) (string i) |> next (m.Add i) n;; val next : Set<int> -> int -> int -> int

Note the use of the string function to convert an int into its string representation and then the use of the int function to convert each char back into an int.

Finally, we use the List.scan function to build a list of accumulated results as the next function finds each of the happy numbers in turn:

> List.scan (fun n _ -> next Set.empty (n+1) (n+1)) 1 [1..7];; val it : int list = [1; 7; 10; 13; 19; 23; 28; 31]

The scan function is relatively new and, consequently, not as widely appreciated as perhaps it should be.

Our whole program weighs in at only 6 lines of code, much shorter than the original!

No comments: