## Happy Numbers

### July 23, 2010

`Sum`, `square` and `digits` are all provided by the Standard Prelude, which makes it easy to write a function to identify happy numbers; LaBounty used a hash table to collect the set of previously-seen iterates, but we simply `cons` them onto a list and use `member` to spot duplicates:

```(define (happy? n)   (let loop ((n n) (ns '()))     (cond ((= n 1) #t)           ((member n ns) #f)           (else (loop (sum (map square (digits n)))                       (cons n ns))))))```

Then it is easy to find the happy numbers less than a limit; again we call on the Standard Prelude, this time for the definitions of `filter` and `range`:

`(define (happy n) (filter happy? (range n)))`

Here are the first eleven happy numbers:

```> (happy 50) (1 7 10 13 19 23 28 31 32 44 49)```

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