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):
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]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
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: newhappy.add(i) continue if i in self.nothappy: continue potential.clear() potential.add(i) current = self._sum_of_char_squares(i) while current not in self.happy \ and current not in self.nothappy \ and current not in potential: potential.add(current) current = self._sum_of_char_squares(i) potential.add(current) if current in self.happy: map(self.happy.add, potential) newhappy.add(i) else: map(self.nothappy.add, potential) return sorted(newhappy) h = happy() h.get_happy_lt_max(2000)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/
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 return !alreadySeen.contains(sos) && numOfTries+1 <= limit && isHappyNumber(sos, limit, numOfTries+1, alreadySeen+sos) } def isHappyNumber(n:Int):Boolean = isHappyNumber(n, 10, 0, Set[Int]()) def main(args:Array[String]) { println (1 to 100 filter { isHappyNumber(_) }) } }[...] Todays problem had to do with Happy Numbers. [...]
(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)))))))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 hHmmm. 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 hI 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.
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;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 add.b cand, total jmn.a digits, cand jmz found, total mov.ba total, cand add.a #1, 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 add #48, @stack jmn writen, <stack add #1, stack wloop sts >stack, 0 jmn wloop, stack sts.a #10, 0 jmp nexthapHere’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// 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
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 ] ) )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); }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; } alert(isHappyNumber(17,100));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)))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.
(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))) ) ) )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 endAlright, 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.
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;;; 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.
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)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; }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))))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