## Happy Numbers

### July 23, 2010

Over at SteamCode, Scott LaBounty suggests that writing a program to compute the happy numbers less than *n* makes a good interview question. According to 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).

For example, 7 is a happy number, as 7^{2}=49, 4^{2}+9^{2}=16+81=97, 9^{2}+7^{2}=81+49=130, 1^{2}+3^{2}+0^{2}=1+9+0=10, and 1^{2}+0^{2}=1+0=1. But 17 is not a happy number, as 1^{2}+7^{2}=1+49=50, 5^{2}+0^{2}=25+0=25, 2^{2}+5^{2}=4+25=29, 2^{2}+9^{2}=4+81=85, 8^{2}+5^{2}=64+25=89, 8^{2}+9^{2}=64+81=145, 1^{2}+4^{2}+5^{2}=1+16+25=42, 4^{2}+2^{2}=16+4=20, 2^{2}+0^{2}=4+0=4, 4^{2}=16, 1^{2}+6^{2}=1+36=37, 3^{2}+7^{2}=9+49=58, and 5^{2}+8^{2}=25+64=89, which forms a loop.

Your task is to write a function to identify the happy numbers less than a given limit; you should work at the level of a programming interview, taking no more than about fifteen minutes, and giving a short explanation of your work to the interviewer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

My Haskell solution (see http://bonsaicode.wordpress.com/2010/07/23/programming-praxis-happy-numbers/ for a version with comments):

letdigits=letrecgo l n=ifn=0thenlelsego

(nmod10::l)(n/10)ingo[]letsumsqdig=List.fold_left(funs d->s+d*d)0%digitsletfixpoint f x=letrecgo x y=ifx=ythenxelsego(f(f x))(f y)ingo(f x)xletis_happy n=fixpoint sumsqdig n=1Decided to maintain state so that future calls can rely on the calculations of earlier calls.

Bad whitespace removing function, bad.

[ I fixed your previous comment. See the instructions in the HOWTO at the top of the page so you can do it yourself next time. PP]

Thanks for the fix. I also introduced a bug; line 31 should be sum of (current), not (i). Ability to edit comments would be really nice, since I saw the FAQ on code posting after I messed up my code :)

[...] July 23, 2010 jchiu1106 Leave a comment Go to comments The problem was posted on Programming Praxis. The algorithm itself is pretty straightforward, anyone can do it with a few if/else/fors, but to [...]

My Scala version: http://reminiscential.wordpress.com/2010/07/23/finding-happy-numbers-using-scala/

[...] Todays problem had to do with Happy Numbers. [...]

There are 143,070 happy numbers less than 1,000,000.

Hmmm. Some spaces/tabs got mucked up there. One more try:

I was hoping I’d be the first to use this particular “cycle detector”, but I see that Gambiteer and Giovanni both beat me to the punch. Quel dommage.

Mark: And 12005034444292997293 less than 10^20. See A068571.

To see such concise implementations in languages like Scala and Haskell is humbling. Awesome, guys! A “larger” Java solution can be seen here.

use v6;

sub n($num){

[+] $num.split(”).map: * ** 2

}

sub isHappy($num){

my @seen;

for $num, {n($^a)} … * {

when any(@seen) { return False }

when 1 { return True }

@seen.push($_);

}

}

sub happyTo($num){

[1 ..^ $num].grep: {isHappy($^a)}

}

say happyTo(50).perl;

Oops. Didn’t realize there was magic to formatting submissions. Let’s see how cpp formats it.

In Redcode, but it took closer to 30 minutes:

Here’s the shorter version I made in Python. Similar to other ones already posted, but uses a dictionary (hash) instead of a set for the sequence generated from n (still maintains constant search time, though).

A longer, well-documented version with multiple definitions of is_happy() is available on codepad.org here.

// took a LOT of time

// and also copied filter and sys stuff

// from others here

import sys

def sumSqrs( num ):

retVal = 0

while num:

retVal += pow( num % 10, 2 )

num /= 10

return retVal

def isHN( num ):

d = {}

while num != 1:

num = sumSqrs( num )

if num in d:

return False

d[ num ] = True

return True

def HN( num ):

l = []

for i in range( 1, num ):

if isHN( i ):

l.append( i )

print l

return l

def HNUsingFilter( num ):

l = filter(lambda n: isHN(n), range( 1, num ) )

print l

return l

if __name__ == ‘__main__':

HN( int( sys.argv[ 1 ] ) )

// sorry about the formatting

// my first post @programmingpraxis

// took a LOT of time

// and also copied filter and sys stuff

// from others here

import sys

def sumSqrs( num ):

retVal = 0

while num:

retVal += pow( num % 10, 2 )

num /= 10

return retVal

def isHN( num ):

d = {}

while num != 1:

num = sumSqrs( num )

if num in d:

return False

d[ num ] = True

return True

def HN( num ):

l = []

for i in range( 1, num ):

if isHN( i ):

l.append( i )

print l

return l

def HNUsingFilter( num ):

l = filter(lambda n: isHN(n), range( 1, num ) )

print l

return l

if __name__ == ‘__main__’:

HN( int( sys.argv[ 1 ] ) )

// sorry for the mistakes in formatting

// trying one more time….

// please delete the previous posts

// took a LOT of time

// and also copied filter and sys stuff

// from others here

The ability to switch between treating Perl variables as strings and numbers is a neat parlor trick.

A JavaScript version… Short, no tricks, easy to understand. Took me ’bout 15 minutes, mostly because of the syntax in JS…

Here’s a Common Lisp version with a bit of memoization. It looks a bit long now that I’ve seen the other solutions… probably took me 30 minutes.

This is the java version that i have wrote:

public abstract class HappyNumbers {

public static ArrayList TRIED_NUMBERS;

public static void main(String args[]) {

System.out.println("HAPPY NUMBERS");

for(int i = 0; i < 10000; i++) {

TRIED_NUMBERS = new ArrayList();

if(isHappy(i, 0)) {

System.out.println("The number is happy : " + i);

}

}

}

public static boolean isHappy(int p_nNumber, int p_nTries) {

TRIED_NUMBERS.add(new Integer(p_nNumber));

int nSums = 0;

while(p_nNumber > 0) {

int nSquare = p_nNumber % 10;

nSquare *= nSquare;

nSums += nSquare;

p_nNumber /= 10;

}

if(nSums == 1) {

return true;

} else {

if(TRIED_NUMBERS.contains(new Integer(nSums))){

return false;

} else {

return isHappy(nSums, p_nTries + 1);

}

}

}

`}`

Clojure naive version. Tested against list of known Happy numbers below 500, found at http://en.wikipedia.org/wiki/Happy_number.

A bit improved version of Mark VandeWettering.

Alright, I have done this, too.

Implemented in Java. Granted, I am not entirely sure if I went overboard or not, as I ended up with 3 classes in total. However, each of theses classes is pretty short and to the point, so that is quite nice again :)

In more detailed fashion, I have an iterator which implements the sequence of numbers starting at a certain number. This is consistent with what others did, like generators in python or lazy lists in haskell. I have a second class, which overall performs the check if a sequence cycles or stops. I put this in a separate class, because that allowed me to keep everything I need for this algorithm in attributes, which cuts down the boilerplate of parameters, which is kinda nice, I guess. The third class is just a tiny class to tie everything together into a nice package.

Anyway, stats:

– Used about 40 minutes in total, 30 minutes writing precise unit tests, and 10 minutes actually programming everything.

– 200 loc in java (with comments)

– almost 100% test coverage (could not bother to check that remove really throws an error on the iterator ;) )

After talking to the folks on #perl6 I cleaned up the perl6 version to make it a little more idiomatic and to add manual memoizing. The new version is about 30% longer because of the memoizing, but it runs in 1/3 of the time.

;; Common Lisp, with memoization and a hack (knowing that all loops necessarily go through the number 4)

(defparameter *memo* (make-hash-table))

(defun happy (n &optional (it 50) (seen ‘()) (now n))

(let ((the-sum (loop for d across (write-to-string n)

sum (expt (parse-integer (string d)) 2))))

(cond

((or (= 1 the-sum) (eq t (gethash the-sum *memo*)))

(dolist (elt seen) (setf (gethash elt *memo*) t))

now)

((or (zerop it) (= 4 the-sum) (eq ‘nope (gethash the-sum *memo*)))

(dolist (elt seen) (setf (gethash elt *memo*) ‘nope)))

(t (happy the-sum (1- it) (cons the-sum seen) now)))))

(defun main (&optional (up-to 500) (it 50))

(loop for n from 1 to up-to when (happy n it) collect n))

A naive ruby version.

my c++ solution:

A different Clojure implementation, tested against Wikipedia’s list of happy numbers under 500.

I wrote a version in Factor and blogged about it:

http://re-factor.blogspot.com/2010/08/happy-numbers.html

[...] (mostly numeric ones) to be solved in any programming language. I was implementing the solution for Happy Numbers and something strange happened, first let’s see my Ruby [...]

Hi, as I do much Emacs Lisp these days, here’s it (30 mins)

;;; happy-numbers.el — Dimitri Fontaine

;;

;; http://programmingpraxis.com/2010/07/23/happy-numbers/

;;

(require ‘cl) ; subseq

(defun happy? (&optional n seen)

“return true when n is a happy number”

(interactive)

(let* ((number (or n (read-from-minibuffer “Is this number happy: “)))

(digits (mapcar ‘string-to-int (subseq (split-string number “”) 1 -1)))

(squares (mapcar (lambda (x) (* x x)) digits))

(happiness (apply ‘+ squares)))

(cond ((eq 1 happiness) t)

((memq happiness seen) nil)

(t (happy? (number-to-string happiness)

(push happiness seen))))))

(defun find-happy-numbers (&optional limit)

“find all happy numbers from 1 to limit”

(interactive)

(let ((count (or limit (read-from-minibuffer “List of happy numbers from 1 to: “)))

happy)

(dotimes (n (string-to-int count))

(when (happy? (number-to-string (1+ n)))

(push (1+ n) happy)))

(nreverse happy)))

ELISP> (happy? “7”)

t

ELISP> (happy? “17”)

nil

ELISP> (find-happy-numbers “50”)

(1 7 10 13 19 23 28 31 32 44 49)

Oh, and the plain SQL version too, thanks to PostgreSQL.

http://tapoueh.org/articles/blog/_Happy_Numbers.html

A couple of ruby versions which are closer to what a ruby programmer actually would write. The first looping and the second recursive. Should perhaps be methods on the integer class though.

def happy?(n)

seen={}

begin

seen[n] = true

n = n.to_s.each_char.map { |x| x.to_i ** 2 }.reduce { |x,y| x + y }

end until seen[n]

return n == 1

end

def happy?(n, seen={})

sum = n.to_s.each_char.map { |x| x.to_i ** 2 }.reduce { |x,y| x + y }

return true if n == 1

return false if seen[sum]

seen[sum] = true

return happy?(sum, seen)

end

Javascript version that shares unhappy numbers between calls to `is_happy`

This is my Python version. Is it ok?

sorry I missed the inputs:

Forth version, works in current BASE.

and a Java solution:

import java.util.HashSet;

import java.util.Set;

public class HappyNumber {

String str;

Set checkedValues = new HashSet();

int sum = 0;

public void printHappyNumbers(int limit) {

for (int i = 1; i <= limit; i++) {

checkedValues = new HashSet();

if (isHappy(i))

System.out.println(i);

}

}

public boolean isHappy(int value) {

sum = 0;

str = Integer.toString(value);

for (int i = 0; i < str.length(); i++) {

sum = sum

+ (int) Math.pow(Character.getNumericValue(str.charAt(i)),

2);

}

if (sum == 1) {

return true;

} else if (checkedValues.contains(sum)) {

return false;

} else {

checkedValues.add(sum);

return isHappy(sum);

}

}

public static void main(String[] args) {

HappyNumber hn = new HappyNumber();

hn.printHappyNumbers(50);

}

}