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

To learn more about happy numbers, look at MathWorld or the OEIS. You can run the program at http://programmingpraxis.codepad.org/eLVpRpM9.

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

;;

;; https://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);

}

}

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)

{

printf(“your number is happy”);

}

else

{

printf(“Not a happy number”);

}

getch();

}

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

lst.add(sum);

} else {

isRepeated = true;

}

num = sum;

System.out.println(num);

sum = 0;

// counter++

}

if (isRepeated)

return 0;

}

return sum;

}

Can u do it on Blue-j windows

thank you so much brooo………………………. vinay singh

can anybody tell me whats the problem in this code

/*Question : Write your code to find whether the number is a happy number or not (for max 10 cycles).

int number : The number to be determined whether it is happy or not

int finalNumber : Store the resultant value in this variable

int cycle_no : Store the number of iterations done to determine whether the ‘number’ is happy or not */

void detectHappy(int number, int &finalNumber, int &cycle_no) {

for(int c=1;c0)

{

int rem;

rem=number%10;

squareSum += rem*rem;

}

return squareSum;

}

if(squareSum==1){

cycle_no=c;

finalNumber=1;

break;

}

else{

finalNumber=squareSum;

number=squareSum;

}

}

}