## 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 72=49, 42+92=16+81=97, 92+72=81+49=130, 12+32+02=1+9+0=10, and 12+02=1+0=1. But 17 is not a happy number, as 12+72=1+49=50, 52+02=25+0=25, 22+52=4+25=29, 22+92=4+81=85, 82+52=64+25=89, 82+92=64+81=145, 12+42+52=1+16+25=42, 42+22=16+4=20, 22+02=4+0=4, 42=16, 12+62=1+36=37, 32+72=9+49=58, and 52+82=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

### 45 Responses to “Happy Numbers”

1. Remco Niemeijer said

```isHappy :: (Read a, Integral a) => a -> Bool
isHappy = f [] where
f _  1 = True
f xs n = notElem n xs && f (n:xs) (sum . map (^ 2) \$ digits n)
digits = map (read . return) . show

happyUpto :: (Read a, Integral a) => a -> [a]
happyUpto n = filter isHappy [1..n - 1]
```
2. let digits =
let rec go l n =
if n = 0 then l else
go (n mod 10 :: l) (n / 10)
in go []

let sumsqdig = List.fold_left (fun s d -> s + d*d) 0 % digits

let fixpoint f x =
let rec go x y = if x = y then x else go (f (f x)) (f y)
in go (f x) x

let is_happy n = fixpoint sumsqdig n = 1

3. Michael said

Decided to maintain state so that future calls can rely on the calculations of earlier calls.

```import math

class happy:
happy = set([1])
nothappy = set()

def _sum_of_char_squares(self, i):
total = 0
for c in str(i):
total = total + math.pow(int(c),2)
return int(total)

def get_happy_lt_max(self, max):
newhappy = set()
potential = set()
for i in range(2, max):
if i in self.happy:
continue
if i in self.nothappy:
continue

potential.clear()
current = self._sum_of_char_squares(i)

while current not in self.happy \
and current not in self.nothappy \
and current not in potential:
current = self._sum_of_char_squares(i)

if current in self.happy:
else:

return sorted(newhappy)

h = happy()
h.get_happy_lt_max(2000)
```
4. Michael said

[ 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]

5. Michael said

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 :)

6. […] 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 […]

7. jchiu1106 said
```object Happy {
import annotation.tailrec

@tailrec
def isHappyNumber(n:Int, limit:Int, numOfTries:Int, alreadySeen:Set[Int]):Boolean = {
val sos = ((n.toString.toCharArray.map { digit => Math.pow(Integer.valueOf("" + digit).doubleValue, 2) }).foldLeft(0.0) { _ + _ }).toInt
if (sos == 1)
return true
else
}

def isHappyNumber(n:Int):Boolean = isHappyNumber(n, 10, 0, Set[Int]())

def main(args:Array[String]) {
println (1 to 100 filter { isHappyNumber(_) })
}
}

```
8. […] Todays problem had to do with Happy Numbers. […]

9. Gambiteer said
```(define (happy? n)

;; use minimal state hare and tortoise algorithm

(define (next n)
(sum (map square (digits n))))

(let loop ((tortoise n)
(hare (next n)))
(or (= tortoise 1)
(and (not (= tortoise hare))
(loop (next tortoise)
(next (next hare)))))))
```
10. There are 143,070 happy numbers less than 1,000,000.

```#!/usr/bin/env python

#  _  _   _   ___ _____   __
# | || | /_\ | _ \ _ \ \ / /
# | __ |/ _ \|  _/  _/\ V /
# |_||_/_/ \_\_| |_|   |_|
#
# a program to find all the happy numbers less than N
# inspired by a challenge on programming praxis
#

import sys

def sum_digits_squared(n):
s = 0
while n > 0:
n, m = n // 10, n % 10
s = s + m * m
return s

def is_happy(n):
n0, n1 = n, n
while True:
n0 = sum_digits_squared(n0)
if n0 == 1:
return True
n1 = sum_digits_squared(n1)
n1 = sum_digits_squared(n1)
if n0 == n1:
return False

happy =  filter(lambda x : is_happy(x), range(int(sys.argv[1])))

for h in happy:
print h
```
11. Hmmm. Some spaces/tabs got mucked up there. One more try:

```#!/usr/bin/env python

#  _  _   _   ___ _____   __
# | || | /_\ | _ \ _ \ \ / /
# | __ |/ _ \|  _/  _/\ V /
# |_||_/_/ \_\_| |_|   |_|
#
# a program to find all the happy numbers less than N
# inspired by a challenge on programming praxis
#

import sys

def sum_digits_squared(n):
s = 0
while n > 0:
n, m = n // 10, n % 10
s = s + m * m
return s

def is_happy(n):
n0, n1 = n, n
while True:
n0 = sum_digits_squared(n0)
if n0 == 1:
return True
n1 = sum_digits_squared(n1)
n1 = sum_digits_squared(n1)
if n0 == n1:
return False

happy =  filter(lambda x : is_happy(x), range(int(sys.argv[1])))

for h in happy:
print h
```
12. 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.

13. programmingpraxis said

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

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

15. Eddward said

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;

16. Eddward said

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

```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;
```
17. John said

In Redcode, but it took closer to 30 minutes:

```        org    newcand

base   equ 10
limit  equ 100
tries  equ 50

stack   dat    0
happy   dat    1
cand    dat    0
total   dat    0
repeat  dat    0

newcand mov.ba happy,     cand
mov    #tries,    repeat
again   mov    #-1,       total
digits  mov.ab cand,      cand
mod    #base,     cand
div.a  #base,     cand
mul.b  cand,      cand
jmn.a  digits,    cand
jmz    found,     total
mov.ba total,     cand
djn    again,     repeat
nexthap seq    #limit,    happy
jmp    newcand,   >happy
dat    0

found   mov.b  happy,     <stack
writen  mov.b  @stack,    <stack
div    #10,       >stack
mod    #10,       @stack
jmn    writen,    <stack
wloop   sts    >stack,    0
jmn    wloop,     stack
sts.a  #10,       0
jmp    nexthap
```
18. Graham said

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.

```def is_happy(n):
n_sequence = {n : 1}
while n != 1:
n = sum(pow(x,2) for x in _digits(n))
if n in n_sequence: return False
n_sequence[n] = 1
return True

def _digits(n):
if n == 0: return [0]
res = []
while n != 0:
res.append(n % 10)
n //= 10
return res

for h in [x for x in xrange(1, 100) if is_happy(x)]: print h
```
19. itachi_ said

// 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 ] ) )

20. itachi_ said

// 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 ] ) )

21. itachi_ said

// 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

```
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 ] ) )
```
22. Mark said

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

```sub is_happy {
my (\$number) = \$@;
my %seen = ();
while (\$number != 1 && ! \$seen{\$number}) {
\$seen{\$number} = 1;
my \$next = 0;
\$next += \$_**2 foreach split //, \$number;
\$number = \$next;
}
return \$number == 1;
}

for my \$i (1 .. \$ARGV[0]) {
print "\$i\n" if is_happy(\$i);
}
```
23. Saman said

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

```function isHappyNumber(n, limit)
{
var sum = 0, i = 0;
while(i < limit)
{
sum = 0;
for(var j=0; j < String(n).length; j++)
{
n_pos_j = parseInt(String(n)[j]);
sum += (n_pos_j * n_pos_j);
}
n = parseInt(sum);
if (n == 1) return true;
i++;
}
return false;
}

```
24. Jonathan said

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.

```(defun cheer (n)
(multiple-value-bind (rest digit) (floor n 10)
(+ (square digit)
(if (zerop rest) 0
(cheer rest)))))

(let^ (cyclic '())
(defun recycle () cyclic)
(defun happy (n)
(labels ((helper (i history)
(let^ (next (cheer i))
(cond
((member next cyclic) nil)
((= 1 next) t)
((member next history)
(setff union cyclic history)
;(setff sort cyclic #'<)
nil)
(t (helper next (cons next history)))))))
(helper n (list n)))))

(iter (for i from 1 to 1000)
(when (happy i) (collect i)))
```
25. MND said

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); } } } ```

```} ```

26. karijes said

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

```(defn split-digits [n]
(if (< n 10)
(seq [n])
(map
(fn [x] (Integer/parseInt (str x)))
(seq (str n))
)))

(defn sum-pow-digits [seq]
(let [pows (map (fn [x] (Math/pow x 2)) seq)]
(int (apply + pows))
))

(defn seq-has-num? [seq num]
(some (fn [x] (= x num)) seq))

(defn happy-number? [n]
(loop [seen '()
n     n]
(cond
(= n 1) true
;; it forms the closing loop
(seq-has-num seen n) false
:else
(recur (cons n seen)
(sum-pow-digits (split-digits n)))
) ) )
```
27. alexander said

A bit improved version of Mark VandeWettering.

```function is_happy(x)
function step(x)
local s = 0, d;
while x > 0 do
d = math.floor(x % 10);
x = math.floor(x / 10);
s = s + d * d;
end
return s;
end
local x1, x2 = x, x;
while true do
x1 = step(x1);
x2 = step(step(x2));
if 1 == x2 then
return true;
end
if x1 == x2 then
return false;
end
end
end
```
28. Tetha said

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 ;) )

29. Eddward said

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.

```use v6;

sub n(\$num){
[+] \$num.comb(/\d/).map: * ** 2
}

my \$happy   = 1;
my \$unhappy = 0;
sub isHappy(\$num){
my \$seen = 0;
for \$num, &n ... * {
when any(\$unhappy, \$seen) {
\$unhappy |= \$seen;
return False;
}
when \$happy {
\$happy |= \$seen;
return True;
}
\$seen |= \$_;
}
}

sub happyTo(\$num){
[1 ..^ \$num].grep: &isHappy
}

happyTo(50).perl.say;
```
30. Axio said

;; 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))

31. Jacob Atzen said

A naive ruby version.

```class Fixnum
def digits
if self >= 10
(self / 10).digits << self % 10
else
[self]
end
end

def square
self * self
end

def happy_number?(seen = [])
product = digits.map(&:square).sum
return true if product == 1
return false if seen.include?(product)
product.happy_number?(seen << product)
end
end

class Array
def sum
self.inject(0){|sum, n| sum + n}
end
end

def happy_numbers_upto(n)
(1..n).select{|n| n.happy_number? }
end

p happy_numbers_upto(50)
```
32. kitten said

my c++ solution:

```#include <iostream>
#include <bitset>
using namespace std;

bool is_happy_number (int x) {
bitset<100000> founds;
int itr = x;
do {
founds.set(itr);
int num = 0;
while (itr) {
int factor = itr % 10;
num += factor * factor;
itr /= 10;
}
itr = num;
} while (itr != 1 && !founds.test(itr));

if (itr == 1) return true;
else return false;
}

int main(int argc, char *argv[])
{
int input;
while (cin >> input)
cout << boolalpha << is_happy_number (input) << endl;

return 0;
}
```
33. Peter Eddy said

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

```(defn char-to-int [c]
(- (int c) (int \0)))

(defn to-num-seq [n]
(map char-to-int (seq (str n))))

(defn happy?
([n] (happy? n {}))
([n hist]
(let [sum (apply + (map #(* % %) (to-num-seq n)))]
(cond (= 1 sum) true
(hist sum) false
:default (recur sum (assoc hist sum true))))))

(defn happies [n]
(filter happy? (range 1 (inc n))))
```
34. John said

I wrote a version in Factor and blogged about it:

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

35. […] (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 […]

36. dim said

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)

37. dim said

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

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

38. Andreas said

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

39. Guillaume said

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

```function is_happy(/*integer*/n, /*?object?*/unhappy) {

var visited = {};
unhappy = unhappy || {};

var n0 = n;

while (true) {
n = iter( n );
if (n === 1)
return true;
if (visited[n] || unhappy[n]) {
unhappy[n0] = true;
return false;
}
visited[n] = true;
}

function iter(n) {
var ret = 0;
while (n) {
var p = n % 10;
ret += p * p;
n = (n / 10) >> 0;
}
return ret;
}
}

function find_happy(n) {
var ret = [], unhappy = {};
for (var a = 1; a <= n; a++)
if (is_happy(a, unhappy))
ret.push(a);
return ret;
}

console.log( find_happy(100).join(' '));
// 1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100
```
40. k A r T h I k said

This is my Python version. Is it ok?

```def happynumber(n, lst):
total = sumofsquareofdigits(n)
if total == 1:
return True
elif lst.__contains__(total):
return False

lst.append(total)
return happynumber(total, lst)

def sumofsquareofdigits(n):
return sum([int(data) * int(data) for data in str(n)])
```
41. k A r T h I k said

sorry I missed the inputs:

```print happynumber(7, [7])
#True
```
42. David said

Forth version, works in current BASE.

```: sumsqd ( n1 -- n2 )
0 swap
BEGIN ?dup WHILE
base @ /mod >r dup * + r>
REPEAT ;

: happy?  ( n -- ? )
dup sumsqd
BEGIN 2dup <> WHILE
swap sumsqd
swap sumsqd sumsqd
REPEAT
drop 1 = ;

23 happy? . -1  ok
27 happy? . 0  ok
```
43. Ivan said

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 {
return isHappy(sum);
}
}

public static void main(String[] args) {
HappyNumber hn = new HappyNumber();
hn.printHappyNumbers(50);
}
}

44. vinay singh said

check my code it is very optimized:-
#include
#include
void main()
{
int a,b,c=0;
clrscr();
printf(“enter a number”);
scanf(“%d”,&a);
while(a!=0)
{
{ b=a%10;
c=c+(b*b);
a=a-b;
a=a/10;
}

if(a==0)
if(c>=10)
{
a=c;
c=0;
}
}
if(c==1)
{
}
else
{
printf(“Not a happy number”);
}
getch();
}

45. Suresh Kumar Pathak said

static int calculateHappyNum(int num) {
if (num == 1)
return 1;
int sum = 0;
List lst = new ArrayList();
while (num > 0) {
int x = num % 10;
sum = sum + (x * x);
num = num / 10;
boolean isRepeated = false;
if (sum != 1 && num < 1) {
if (!lst.contains(sum)) {