Happy numbers

From Wikipedia, the free encyclopedia:

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.

Task: Find and print the first 8 happy numbers.

C++

Translation of: Python

<lang cpp>#include <map>

include <set>

bool happy(int number) {

 static std::map<int, bool> cache;

 std::set<int> cycle;
 while (number != 1 && !cycle.count(number)) {
   if (cache.count(number)) {
     number = cache[number] ? 1 : 0;
     break;
   }
   cycle.insert(number);
   int newnumber = 0;
   while (number > 0) {
     int digit = number % 10;
     newnumber += digit * digit;
     number /= 10;
   }
   number = newnumber;
 }
 bool happiness = number == 1;
 for (std::set<int>::const_iterator it = cycle.begin();
      it != cycle.end(); it++)
   cache[*it] = happiness;
 return happiness;

}

include <iostream>

int main() {

 for (int i = 1; i < 50; i++)
   if (happy(i))
     std::cout << i << std::endl;
 return 0;

}</lang>

Forth

next ( n -- n )

 0 swap begin 10 /mod >r  dup * +  r> ?dup 0= until ;

cycle? ( n -- ? )

 here dup @ cells +
 begin dup here >
 while 2dup @ = if 2drop true exit then
       1 cells -
 repeat
 1 over +!  dup @ cells + !  false ;

happy? ( n -- ? )

 0 here !  begin next dup cycle? until  1 = ;

happy-numbers ( n -- )

 0 swap 0 do
   begin 1+ dup happy? until dup .
 loop drop ;

8 happy-numbers \ 1 7 10 13 19 23 28 31 </lang>

JavaScript

<lang javascript> function happy(number) {

   var m, digit ;
   var cycle = new Array() ;

   while(number != 1 && cycle[number] != true) {
       cycle[number] = true ;
       m = 0 ;
       while (number > 0) {
           digit = number % 10 ;
           m += digit * digit ;
           number = (number  - digit) / 10 ;
       }
       number = m ;
   }
   return (number == 1) ;

} ;

var cnt = 8 ; var number = 1 ;

while(cnt-- > 0) {

   while(!happy(number))
       number++ ;
   document.write(number + " ") ;
   number++ ;

} </lang>

Python

Includes a cache of precomputed values. <lang python>>>> def happy(number):

   cycle = set()
   while number != 1 and number not in cycle:
       if number in happy.cache:
           number = 1 if happy.cache[number] else 0
           break
       cycle.add(number)
       newnumber = 0
       while number > 0:
           number, digit = divmod(number, 10)
           newnumber += digit*digit
       number = newnumber
   happiness = number==1
   for n in cycle:     # all in cycle share the same happiness
       happy.cache.setdefault(n, happiness)
   return happiness

>>> happy.cache={} >>> [x for x in range(1,50) if happy(x)] # First few happy numbers [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49] >>> </lang>

Smalltalk

Works with: GNU Smalltalk

Translation of: Python

In addition to the "Python's cache mechanism", the use of a Bag assures that found e.g. the happy 190, we already have in cache also the happy 910 and 109, and so on. <lang smalltalk>Object subclass: HappyNumber [

 |cache negativeCache|
 HappyNumber class >> new [ |me|
   me := super new.
   ^ me init
 ]
 init [ cache := Set new. negativeCache := Set new. ]

 hasSad: aNum [
   ^ (negativeCache includes: (self recycle: aNum))
 ]
 hasHappy: aNum [
   ^ (cache includes: (self recycle: aNum))
 ]
 addHappy: aNum [
   cache add: (self recycle: aNum)
 ]
 addSad: aNum [
   negativeCache add: (self recycle: aNum)
 ]

 recycle: aNum [ |r n| r := Bag new.
   n := aNum.
   [ n > 0 ]
   whileTrue: [ |d|
     d := n rem: 10.
     r add: d.
     n := n // 10.
   ].
   ^r
 ]

 isHappy: aNumber [ |cycle number newnumber|
   number := aNumber.
   cycle := Set new.
   [ (number ~= 1) & ( (cycle includes: number) not ) ]
   whileTrue: [
     (self hasHappy: number)
     ifTrue: [ ^true ]
     ifFalse: [
       (self hasSad: number) ifTrue: [ ^false ].
       cycle add: number.
       newnumber := 0.
       [ number > 0 ]
       whileTrue: [ |digit|
         digit := number rem: 10.
         newnumber := newnumber + (digit * digit).
	  number := (number - digit) // 10.
       ].
       number := newnumber.
     ]
   ].
   (number = 1)
   ifTrue: [
     cycle do: [ :e | self addHappy: e ].
     ^true
   ]
   ifFalse: [ 
     cycle do: [ :e | self addSad: e ].
     ^false 
   ]
 ]

].</lang>

<lang smalltalk>|happy| happy := HappyNumber new.

1 to: 30 do: [ :i |

 (happy isHappy: i)
 ifTrue: [ i displayNl ]

].</lang>

Tcl

using code from Sum of squares#Tcl <lang tcl>proc is_happy n {

   set seen [list]
   while {$n > 1 && [lsearch -exact $seen $n] == -1} {
       lappend seen $n
       set n [sum_of_squares [split $n ""]]
   }
   return [expr {$n == 1}]

}

set happy [list] set n -1 while {[llength $happy] < 8} {

   if {[is_happy $n]} {lappend happy $n}
   incr n

} puts "the first 8 happy numbers are: [list $happy]"</lang>

the first 8 happy numbers are: {1 7 10 13 19 23 28 31}