Happy numbers
From Wikipedia, the free encyclopedia:
You are encouraged to solve this task according to the task description, using any language you may know.
- 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.
Ada
<lang Ada>with Ada.Text_IO; use Ada.Text_IO; with Ada.Containers.Ordered_Sets;
procedure Test_Happy_Digits is
function Is_Happy (N : Positive) return Boolean is package Sets_Of_Positive is new Ada.Containers.Ordered_Sets (Positive); use Sets_Of_Positive; function Next (N : Positive) return Natural is Sum : Natural := 0; Accum : Natural := N; begin while Accum > 0 loop Sum := Sum + (Accum mod 10) ** 2; Accum := Accum / 10; end loop; return Sum; end Next; Current : Positive := N; Visited : Set; begin loop if Current = 1 then return True; elsif Visited.Contains (Current) then return False; else Visited.Insert (Current); Current := Next (Current); end if; end loop; end Is_Happy; Found : Natural := 0;
begin
for N in Positive'Range loop if Is_Happy (N) then Put (Integer'Image (N)); Found := Found + 1; exit when Found = 8; end if; end loop;
end Test_Happy_Digits;</lang> Sample output:
1 7 10 13 19 23 28 31
ALGOL 68
<lang algol68>INT base10 = 10, num happy = 8;
PROC next = (INT in n)INT: (
INT n := in n; INT out := 0; WHILE n NE 0 DO out +:= ( n MOD base10 ) ** 2; n := n OVER base10 OD; out
);
PROC is happy = (INT in n)BOOL: (
INT n := in n; FOR i WHILE n NE 1 AND n NE 4 DO n := next(n) OD; n=1
);
INT count := 0; FOR i WHILE count NE num happy DO
IF is happy(i) THEN count +:= 1; print((i, new line)) FI
OD</lang> Output:
+1 +7 +10 +13 +19 +23 +28 +31
AutoHotkey
<lang AutoHotkey>Loop {
If isHappy(A_Index) { out .= (out="" ? "" : ",") . A_Index i ++ If (i = 8) { MsgBox, The first 8 happy numbers are: %out% ExitApp } }
}
isHappy(num, list="") {
list .= (list="" ? "" : ",") . num Loop, Parse, num sum += A_LoopField ** 2 If (sum = 1) Return true Else If sum in %list% Return false Else Return isHappy(sum, list)
}</lang>
AWK
<lang awk>function is_happy(n) {
if ( n in happy ) return 1; if ( n in unhappy ) return 0; cycle[""] = 0 while( (n!=1) && !(n in cycle) ) { cycle[n] = n new_n = 0 while(n>0) { d = n % 10 new_n += d*d n = int(n/10) } n = new_n } if ( n == 1 ) { for (i_ in cycle) { happy[cycle[i_]] = 1 delete cycle[i_] } return 1 } else { for (i_ in cycle) { unhappy[cycle[i_]] = 1 delete cycle[i_] } return 0 }
}
BEGIN {
cnt = 0 happy[""] = 0 unhappy[""] = 0 for(j=1; (cnt < 8); j++) { if ( is_happy(j) == 1 ) { cnt++ print j } }
}</lang>
C
<lang c>#include "stdio.h"
- include "stdlib.h"
int is_in(int item, int arr[], int arr_len) {
int i; for (i = 0; i < arr_len; i++) if (arr[i] == item) return 1; // found return 0;
}
int is_happy(int n) {
#define SEEN_LEN 100 static int seen[SEEN_LEN]; int n_seen = 0;
while (!is_in(n, seen, n_seen)) { if (n_seen >= SEEN_LEN) { fprintf(stderr, "Error: out of seen[]\n"); exit(EXIT_FAILURE); } seen[n_seen] = n; n_seen++;
int tot = 0; while (n) { int digit = n % 10; n /= 10; tot += digit * digit; } n = tot; }
return n == 1; #undef SEEN_LEN
}
int main() {
int to_show = 8;
int n_shown = 0; int n = 1; while (n_shown < to_show) { if (is_happy(n)) { printf("%d ", n); n_shown++; } n++; } printf("\n");
return EXIT_SUCCESS;
}</lang>
C++
<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>
Alternative version without caching:
<lang cpp>unsigned int happy_iteration(unsigned int n) {
unsigned int result = 0; while (n > 0) { unsigned int lastdig = n % 10; result += lastdig*lastdig; n /= 10; } return result;
}
bool is_happy(unsigned int n) {
unsigned int n2 = happy_iteration(n); while (n != n2) { n = happy_iteration(n); n2 = happy_iteration(happy_iteration(n2)); } return n == 1;
}
- include <iostream>
int main() {
unsigned int current_number = 1;
unsigned int happy_count = 0; while (happy_count != 8) { if (is_happy(current_number)) { std::cout << current_number << " "; ++happy_count; } ++current_number; } std::cout << std::endl;
}</lang>
Cycle detection in is_happy()
above is done using Floyd's cycle-finding algorithm.
Clojure
<lang clojure>(defn- digit-to-num [d] (Character/digit d 10)) (defn- square [n] (* n n))
(defn happy? [n]
(loop [n n, seen #{}] (cond (= n 1) true (seen n) false :else (recur (reduce + (map (comp square digit-to-num) (str n))) (conj seen n)))))
(def happy-numbers (filter happy? (iterate inc 1)))
(println (take 8 happy-numbers))</lang>
Common Lisp
<lang lisp>(defun happyp (n &aux (seen ()))
(loop (when (= n 1) (return t)) (when (find n seen) (return nil)) (push n seen) (setf n (reduce #'+ (map 'list (lambda (c &aux (x (position c "0123456789"))) (* x x)) (format nil "~d" n))))))
(loop
with happy = 0 for n from 0 until (= 8 happy) when (happyp n) do (incf happy) and do (format t "~d~%" n))</lang>
F#
This requires the F# power pack to be referenced and the 2010 beta of F# <lang fsharp>open System.Collections.Generic open Microsoft.FSharp.Collections
let answer =
let sqr x = x*x // Classic square definition let rec AddDigitSquare n = match n with | 0 -> 0 // Sum of squares for 0 is 0 | _ -> sqr(n % 10) + (AddDigitSquare (n / 10)) // otherwise add square of bottom digit to recursive call let dict = new Dictionary<int, bool>() // Dictionary to memoize values let IsHappy n = if dict.ContainsKey(n) then // If we've already discovered it dict.[n] // Return previously discovered value else let cycle = new HashSet<_>(HashIdentity.Structural) // Set to keep cycle values in let rec isHappyLoop n = if cycle.Contains n then n = 1 // If there's a loop, return true if it's 1 else cycle.Add n |> ignore // else add this value to the cycle isHappyLoop (AddDigitSquare n) // and check the next number in the cycle let f = isHappyLoop n // Keep track of whether we're happy or not cycle |> Seq.iter (fun i -> dict.[i] <- f) // and apply it to all the values in the cycle f // Return the boolean
1 // Starting with 1, |> Seq.unfold (fun i -> Some (i, i + 1)) // make an infinite sequence of consecutive integers |> Seq.filter IsHappy // Keep only the happy ones |> Seq.truncate 8 // Stop when we've found 8</lang>
E
<lang e>def isHappyNumber(var x :int) {
var seen := [].asSet() while (!seen.contains(x)) { seen with= x var sum := 0 while (x > 0) { sum += (x % 10) ** 2 x //= 10 } x := sum if (x == 1) { return true } } return false
}
var count := 0 for x ? (isHappyNumber(x)) in (int >= 1) {
println(x) if ((count += 1) >= 8) { break }
}</lang>
Forth
<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>
Haskell
<lang haskell>import Data.Char (digitToInt) import Data.Set (member, insert, empty)
isHappy :: Integer -> Bool isHappy = p empty
where p _ 1 = True p s n | n `member` s = False | otherwise = p (insert n s) (f n) f = sum . map ((^2) . toInteger . digitToInt) . show
main = mapM_ print $ take 8 $ filter isHappy [1..]</lang>
J
<lang j> 8{. (#~1=+/@(*:@(,.&.":))^:(1&~:*.4&~:)^:_ "0) 1+i.100 1 7 10 13 19 23 28 31</lang>
This is a repeat while construction <lang j> f ^: cond ^: _ <input></lang> that produces an array of 1's and 4's, which is converted to 1's and 0's forming a binary array having a 1 for a happy number. Finally the happy numbers are extracted by a binary selector. <lang j> (binary array) # 1..100</lang>
So for easier reading the solution could be expressed as: <lang j> cond=: 1&~: *. 4&~: NB. not equal to 1 and not equal to 4
sumSqrDigits=: +/@(*:@(,.&.":))
sumSqrDigits 123 NB. test sum of squared digits
14
8{. (#~ 1 = sumSqrDigits ^: cond ^:_ "0) 1 + i.100
1 7 10 13 19 23 28 31</lang>
Java
<lang java5>import java.util.HashSet; public class Happy{
public static boolean happy(long number){ long m = 0; int digit = 0; HashSet<Long> cycle = new HashSet<Long>(); while(number != 1 && cycle.add(number)){ m = 0; while(number > 0){ digit = (int)(number % 10); m += digit*digit; number /= 10; } number = m; } return number == 1; }
public static void main(String[] args){ for(long num = 1,count = 0;count<8;num++){ if(happy(num)){ System.out.println(num); count++; } } }
}</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>
Lua
<lang lua>function digits(n)
if n > 0 then return n % 10, digits(math.floor(n/10)) end
end function sumsq(a, ...)
return a and a ^ 2 + sumsq(...) or 0
end local happy = setmetatable({true, false, false, false}, {
__index = function(self, n) self[n] = self[sumsq(digits(n))] return self[n] end } )
i, j = 0, 1 repeat
i, j = happy[j] and (print(j) or i+1) or i, j + 1
until i == 8</lang>
Mathematica
Custom function HappyQ: <lang Mathematica>AddSumSquare[input_]:=Append[input,Total[IntegerDigits[Last[input]]^2]] NestUntilRepeat[a_,f_]:=NestWhile[f,{a},!MemberQ[Most[Last[{##}]],Last[Last[{##}]]]&,All] HappyQ[a_]:=Last[NestUntilRepeat[a,AddSumSquare]]==1</lang> Examples for a specific number: <lang Mathematica>HappyQ[1337] HappyQ[137]</lang> gives back: <lang Mathematica>True False</lang> Example finding the first 8: <lang Mathematica>m = 8; n = 1; i = 0; happynumbers = {}; While[n <= m,
i++; If[HappyQ[i], n++; AppendTo[happynumbers, i] ] ]
happynumbers</lang> gives back: <lang Mathematica>{1, 7, 10, 13, 19, 23, 28, 31}</lang>
Oz
<lang oz>declare
fun {IsHappy N} {IsHappy2 N nil} end fun {IsHappy2 N Seen} if N == 1 then true elseif {Member N Seen} then false else
Next = {Sum {Map {Digits N} Square}}
in
{IsHappy2 Next N|Seen}
end end
fun {Sum Xs} {FoldL Xs Number.'+' 0} end fun {Digits N} {Map {Int.toString N} fun {$ D} D - &0 end} end fun {Square N} N*N end
fun lazy {Nat I} I|{Nat I+1} end %% List.filter is eager. But we need a lazy Filter: fun lazy {LFilter Xs P} case Xs of X|Xr andthen {P X} then X|{LFilter Xr P} [] _|Xr then {LFilter Xr P} [] nil then nil end end
HappyNumbers = {LFilter {Nat 1} IsHappy}
in
{Show {List.take HappyNumbers 8}}</lang>
Perl
<lang perl>use List::Util qw(sum);
sub is_happy ($)
{for (my ($n, %seen) = shift ;; $n = sum map {$_**2} split //, $n) {$n == 1 and return 1; $seen{$n}++ and return 0;}}
for (my ($n, $happy) = (1, 0) ; $happy < 8 ; ++$n)
{is_happy $n or next; print "$n\n"; ++$happy;}</lang>
Perl 6
<lang perl6>sub happy (Int $n is copy returns Bool) {
my %seen; loop { ($n = [+] map * ** 2, $n.comb) == 1 and return True; %seen{$n}++ and return False; }
}
my $happy = 0; for 1 .. 100 {
happy $_ or next; .say; ++$happy == 8 and last;
}</lang>
PHP5
<lang php> class happynumber {
/* For example, 7 is happy, as the associated sequence is: 7² = 4 4² + 9² = 97 9² + 7² = 130 1² + 3² + 0² = 10 1² + 0² = 1. */
var $list,$num; static $cache;
function __construct() { $this->list=array(); } static function run($anz,$beg=1) { for($i=0,$x=$beg;$i < $anz;$i++) { while(!$z=happynumber::num($x)) $x++; $x++; echo "\n".$z; } }
function ishappy($num) { $sum=0; $this->list[]=$num; foreach(str_split($num) as $v) { $sum+=($v*$v); } ### if($sum==1)return true; elseif(in_array($sum,$this->list))return false; else return $this->ishappy($sum); }
static function num($p) { $obj=new happynumber(); $out= ($obj->ishappy($p))? $p : false; return $out; }
}
for($a=1;$a<10;$a++) happynumber::run(10,$a*10000);
</lang>
PicoLisp
<lang PicoLisp>(de happy? (N)
(let Seen NIL (loop (T (= N 1) T) (T (member N Seen)) (setq N (apply + (mapcar '((C) (** (format C) 2)) (chop (push 'Seen N)) ) ) ) ) ) )
(let H 0
(do 8 (until (happy? (inc 'H))) (printsp H) ) )</lang>
Output:
1 7 10 13 19 23 28 31
PL/I
<lang PL/I> get list (n); put skip list ('The number is ', n); do i = 1 to 100;
m = 0; do until (n = 0); m = m + mod(n, 10)**2; n = n/10; end; if m = 1 then do; put (' and is a happy number'); stop; end;
end; </lang>
PureBasic
When compiled for Windows x86, this code is only 5.5 kB.
<lang PureBasic>#ToFind=8
- MaxTests=100
Declare is_happy(n)
If OpenConsole()
Define i=1,Happy Repeat If is_happy(i) Happy+1 PrintN("#"+Str(Happy)+RSet(Str(i),3)) EndIf i+1 Until Happy>=#ToFind ; Print(#CRLF$+#CRLF$+"Press ENTER to exit"): Input() CloseConsole()
EndIf
Procedure is_happy(n)
Protected i,j=n,dig,sum Repeat sum=0 While j dig=j%10 j/10 sum+dig*dig Wend If sum=1: ProcedureReturn #True: EndIf j=sum i+1 Until i>#MaxTests ProcedureReturn #False
EndProcedure</lang>
Python
<lang python>>>> def happy(n):
past = set() while True: total = sum(int(i)**2 for i in str(n)) if total == 1 or total in past: return total not in past n = total past.add(total)
>>> [x for x in range(1,500) if happy(x)][:8]</lang>
R
<lang R>is.happy <- function(n) {
stopifnot(is.numeric(n) && length(n)==1) getdigits <- function(n) { as.integer(unlist(strsplit(as.character(n), ""))) } digits <- getdigits(n) previous <- c() repeat { sumsq <- sum(digits^2, na.rm=TRUE) if(sumsq==1L) { happy <- TRUE break } else if(sumsq %in% previous) { happy <- FALSE attr(happy, "cycle") <- previous break } else { previous <- c(previous, sumsq) digits <- getdigits(sumsq) } } happy
}</lang> Example usage <lang R>is.happy(2)</lang>
[1] FALSE attr(,"cycle") [1] 4 16 37 58 89 145 42 20
<lang R>#Find happy numbers between 1 and 50 which(apply(rbind(1:50), 2, is.happy))</lang>
1 7 10 13 19 23 28 31 32 44 49
<lang R>#Find the first 8 happy numbers happies <- c() i <- 1L while(length(happies) < 8L) {
if(is.happy(i)) happies <- c(happies, i) i <- i + 1L
} happies</lang>
1 7 10 13 19 23 28 31
REXX
<lang rexx>count = 0 do zahl = 1 by 1 until count = 8
t = zahl all_sums = "" do forever sum = 0 do i = 1 to length(t) z = substr(t,i,1) sum = sum + z*z end if t = 1 | pos(sum,all_sums) > 0 then leave t = sum all_sums = all_sums sum end if sum = 1 then do say zahl count = count + 1 end
end</lang>
Ruby
Use of cache from Python <lang ruby>require 'set'
def happy?(n)
seen = Set[] state = while n>1 and not seen.include?(n) if $happy_cache[:happy].include?(n): break :happy elsif $happy_cache[:sad].include?(n): break :sad end seen << n n = sum_of_squares_of_digits(n) end state.nil? and state = n == 1 ? :happy : :sad $happy_cache[state] += seen state == :happy
end
def sum_of_squares_of_digits(n)
n.to_s.each_char.inject(0) {|sum,c| sum += (c.to_i)**2}
end
$happy_cache = Hash.new(Set[]) happy_numbers = [] i = 1 while happy_numbers.length < 8
happy_numbers << i if happy? i i += 1
end p happy_numbers p $happy_cache</lang>
[1, 7, 10, 13, 19, 23, 28, 31] {:happy=>[7, 49, 97, 130, 10, 13, 19, 82, 68, 100, 23, 28, 31], :sad=>[2, 4, 16, 37, 58, 89, 145, 42, 20, 3, 9, 81, 65, 61, 5, 25, 29, 85, 6, 36, 45, 41, 17, 50, 8, 64, 52, 11, 12, 14, 15, 26, 40, 18, 21, 22, 24, 27, 53, 34, 30]}
Scala
<lang scala>scala> def isHappy(n: Int) = {
| new Iterator[Int] { | val seen = scala.collection.mutable.Set[Int]() | var curr = n | def next = { | val res = curr | curr = res.toString.map(_.asDigit).map(n => n * n).sum | seen += res | res | } | def hasNext = !seen.contains(curr) | }.toList.last == 1 | }
isHappy: (n: Int)Boolean
scala> Iterator from 1 filter isHappy take 8 foreach println 1 7 10 13 19 23 28 31 </lang>
Scheme
<lang scheme>(define (number->list num)
(do ((num num (quotient num 10)) (lst '() (cons (remainder num 10) lst))) ((zero? num) lst)))
(define (happy? num)
(let loop ((num num) (seen '())) (cond ((= num 1) #t) ((memv num seen) #f) (else (loop (apply + (map (lambda (x) (* x x)) (number->list num))) (cons num seen))))))
(display "happy numbers:") (let loop ((n 1) (more 8))
(cond ((= more 0) (newline)) ((happy? n) (display " ") (display n) (loop (+ n 1) (- more 1))) (else (loop (+ n 1) more))))</lang>
The output is:
happy numbers: 1 7 10 13 19 23 28 31
Smalltalk
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}
Ursala
The happy function is a predicate testing whether a given number is happy, and first(p) defines a function mapping a number n to the first n positive naturals having property p. <lang Ursala>#import std
- import nat
happy = ==1+ ^== sum:-0+ product*iip+ %np*hiNCNCS+ %nP
first "p" = ~&i&& iota; ~&lrtPX/&; leql@lrPrX->lrx ^|\~& ^/successor@l ^|T\~& "p"&& ~&iNC
- cast %nL
main = (first happy) 8</lang> output:
<1,7,10,13,19,23,28,31>