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

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

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

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

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, )
#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)) {
} else {
isRepeated = true;
}
num = sum;
System.out.println(num);
sum = 0;
// counter++
}
if (isRepeated)
return 0;
}
return sum;
}

46. Rishabh Pipalawa said

Can u do it on Blue-j windows

47. sivachaitanya said

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

48. gillu1997 said

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;
}

}

}

49. sealfin said

July 23rd, 2010.cpp:

```#include "seal_tree.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_tree.h> */
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

bool f_StringToUnsignedInt( const char * const p_string, unsigned int * const p_number );

bool f_StringToUnsignedInt( const char * const p_string, unsigned int * const p_number )
/*
Returns true if:
* p_number != NULL;
* p_string != NULL;
* p_string points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ];
* and the number represented by the string pointed to by p_string is in the range [ 0, UINT_MAX ].
*/
{
if( p_number == NULL )
return false;

size_t i = 0; // The index of the first non-zero digit in p_string.

if( p_string == NULL )
return false;
if( strlen( p_string ) == 0 )
return false;
for( ; i < strlen( p_string ); i ++ )
if( p_string[ i ] != '0' )
break;

size_t k = strlen( p_string );
unsigned long long multiplier = 0, number = 0;

for( ; k > i; k -- )
{
if( multiplier == 0 )
multiplier = 1;
else
{
multiplier *= 10;
if( multiplier > UINT_MAX )
return false;
}

const char digit = p_string[ k - 1 ];

if(( digit >= '0' ) && ( digit <= '9' ))
{
number += (( digit - '0' ) * multiplier );
if( number > UINT_MAX )
return false;
}
else
return false;
}
*p_number = number;
return true;
}

char *f_ReadStringFromFile( FILE * const p );

char *f_ReadStringFromFile( FILE * const p )
{
char c, *s = ( char* )malloc( sizeof( char ));
size_t s_length = 1;

while(( fscanf( p, "%c", &c ) != EOF ) && ( c != '\n' ))
{
s[ s_length - 1 ] = c;
s_length ++;
s = ( char* )realloc( s, sizeof( char ) * s_length );
}
s[ s_length - 1 ] = '\0';
return s;
}

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

unsigned int f_SumOfSquaresOfDigits( unsigned int p )
{
unsigned int sum_of_squares_of_digits = 0;

while( p != 0 )
{
const unsigned int digit = p % 10;

p /= 10;
sum_of_squares_of_digits += ( digit * digit );
}
return sum_of_squares_of_digits;
}

typedef enum
{
k_IsAHappyNumber_Unknown,
k_IsAHappyNumber_Yes,
k_IsAHappyNumber_No
}
t_IsAHappyNumber;

struct t_Number_struct
{
unsigned int m_number;
t_IsAHappyNumber m_isAHappyNumber;
};

class NumberTree : public seal_Tree<struct t_Number_struct*, unsigned int>
{
public:
~NumberTree( void )
{
p_Empty();
}

void p_Set( unsigned int p )
{
struct t_Number_struct *number = ( struct t_Number_struct* )malloc( sizeof( struct t_Number_struct ));

number->m_number = p;
number->m_isAHappyNumber = k_IsAHappyNumber_Unknown;
seal_Tree<struct t_Number_struct*, unsigned int>::p_Set( number );
}

void p_SetIsAHappyNumber( const bool p )
{
p_SetIsAHappyNumber( m_root, p );
}

private:
void p_SetIsAHappyNumber( struct t_seal_TreeNode<struct t_Number_struct*> * const p_n, const bool p_isAHappyNumber )
{
if( p_n != NULL )
{
if( p_n->m_content->m_isAHappyNumber == k_IsAHappyNumber_Unknown )
if( p_isAHappyNumber )
p_n->m_content->m_isAHappyNumber = k_IsAHappyNumber_Yes;
else
p_n->m_content->m_isAHappyNumber = k_IsAHappyNumber_No;
p_SetIsAHappyNumber( p_n->m_l, p_isAHappyNumber );
p_SetIsAHappyNumber( p_n->m_r, p_isAHappyNumber );
}
}

public:
t_IsAHappyNumber f_GetIsAHappyNumber( unsigned int p )
{
struct t_Number_struct *number = f_Get( p );

return number->m_isAHappyNumber;
}

private:
t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( struct t_Number_struct *p_old, struct t_Number_struct *p_new )
{
if( p_new->m_number < p_old->m_number )
return k_seal_TREE_BRANCH_DIRECTION__LEFT;
if( p_new->m_number == p_old->m_number )
return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
}

t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( struct t_Number_struct *p_content, unsigned int p_identifier )
{
if( p_identifier < p_content->m_number )
return k_seal_TREE_BRANCH_DIRECTION__LEFT;
if( p_identifier == p_content->m_number )
return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
}

struct t_Number_struct *f_IsNotInTree( unsigned int p )
{
#ifndef __MWERKS__
FILE * const print_error_message_to = stderr;
const char * const error_message_terminated_by = "\n";
#else
FILE * const print_error_message_to = stdout;
const char * const error_message_terminated_by = "";
#endif

fprintf( print_error_message_to, "\nSorry, an error occurred: number_tree.f_IsInTree( %u ) == false.\n%s", p, error_message_terminated_by );
exit( EXIT_FAILURE );
}

void p_Delete( struct t_Number_struct *p )
{
free( p );
}
};

int main( const int argc, const char * const argv[] )
{
bool error_occurred;
unsigned int limit;

#ifndef __MWERKS__
error_occurred = argc != 2;
if( !error_occurred )
error_occurred = !f_StringToUnsignedInt( argv[ 1 ], &limit );
if( !error_occurred )
error_occurred = limit < 2;
if( error_occurred )
{
printf( "\nThis program must be passed, via the command line, an integer in the range [ 2, %u ]; this program will then determine the \"happy number(s)\" less than that integer.\n\n", UINT_MAX );
exit( EXIT_FAILURE );
}
#else
do
{
printf( "Please enter an integer in the range [ 2, %u ]; this program will then determine the \"happy number(s)\" less than that integer.\n", UINT_MAX );

char *s = f_ReadStringFromFile( stdin );

error_occurred = !f_StringToUnsignedInt( s, &limit );
free( s );
if( !error_occurred )
error_occurred = limit < 2;
if( error_occurred )
{
printf( "\nSorry, an error occurred: your input was not an integer in the range [ 2, %u ].\n", UINT_MAX );
printf( "\nPlease press the Return key to try again." );
printf( "\n" );
}
}
while( error_occurred );
#endif

NumberTree number_tree;
unsigned int i = 1;
size_t number_of_happy_numbers = 0;
unsigned int *happy_numbers = NULL;

number_tree.p_Set( 1 );
number_tree.p_SetIsAHappyNumber( true );
for( ; i < limit; i ++ )
{
t_IsAHappyNumber is_a_happy_number = k_IsAHappyNumber_Unknown;
unsigned int number = i;

while( is_a_happy_number == k_IsAHappyNumber_Unknown )
{
if( number_tree.f_IsInTree( number ))
{
is_a_happy_number = number_tree.f_GetIsAHappyNumber( number );
if( is_a_happy_number == k_IsAHappyNumber_Yes )
{
number_tree.p_SetIsAHappyNumber( true );
if( ++ number_of_happy_numbers == 1 )
happy_numbers = ( unsigned int* )malloc( sizeof( unsigned int ));
else
happy_numbers = ( unsigned int* )realloc( happy_numbers, sizeof( unsigned int ) * number_of_happy_numbers );
happy_numbers[ number_of_happy_numbers - 1 ] = i;
}
else
{
is_a_happy_number = k_IsAHappyNumber_No;
number_tree.p_SetIsAHappyNumber( false );
}
}
else
{
number_tree.p_Set( number );
number = f_SumOfSquaresOfDigits( number );
}
}
}

printf( "\nThere " );
if( number_of_happy_numbers == 1 )
printf( "is" );
else
printf( "are" );
printf( " " );
if( number_of_happy_numbers == 0 )
printf( "no" );
else
printf( "%u", number_of_happy_numbers );
printf( " \"happy number%s\" in the range [ 1, %u )", ( number_of_happy_numbers == 1 )?"":"s", limit );
if( number_of_happy_numbers > 0 )
{
printf( ": " );

size_t i = 0;

for( ; i < number_of_happy_numbers; i ++ )
{
if( i > 0 )
if( number_of_happy_numbers == 2 )
printf( " and " );
else
{
printf( ", " );
if( i + 1 == number_of_happy_numbers )
printf( "and " );
}
printf( "%u", happy_numbers[ i ] );
}
}
printf( ".\n" );
if( happy_numbers != NULL )
free( happy_numbers );

printf( "\n" );
#ifdef __MWERKS__
printf( "This program will now quit.\n" );
#endif
exit( EXIT_SUCCESS );
}```

The program is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition)) and Mac OS X 10.4.11 (the program compiled using Xcode 2.2.1).

(I’ve just completed a gig at London South Bank University and so I’m again just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my `seal_Tree` template class I might use in the fourth version of my SDL2 joystick interrogator utility); I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

50. […] looked at happy numbers in a previous exercise. Recently, Fermat’s Library re-published a proof by Arthur Porges, first published in the […]

51. […] Code, and Sloane’s, so it is well worth a look; we even did a version of this task in a previous exercise. Here is the Project Euler version of the […]