loading...
Cover image for Write a script to find "Happy Numbers"

Write a script to find "Happy Numbers"

peter profile image Peter Kim Frank ・1 min read

These challenge posts have been a lot of fun. Another one inspired by Fermat's Library.

Challenge

In the language of your choice, write a script to find "Happy Numbers." Via Wikipedia:

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits in base-ten, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that 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 (or sad numbers).

Looking at the picture in the embedded tweet will probably help solidify the process. Here are the first few happy numbers to help check your work:

1, 7, 10, 13, 19, 23, 28, 31

Have fun!

Posted on by:

peter profile

Peter Kim Frank

@peter

Doing a bit of everything at DEV.

Discussion

pic
Editor guide
 
function isHappy(n) {
    if (n === 4) return false;
    const u = n.toString().split('').reduce(((ac,cv) => ac + Math.pow(cv,2)), 0);
    if (u === 1) return true;
    else return isHappy(u);
}

e: updated to work with all happy numbers

 

Your code in ES2016+ (and a bit less readable):

const isHappy = n => {
  if (n === 4) return false;

  const u = [...n.toString()].reduce((ac, c) => ac + (c ** 2), 0);

  return u === 1 || isHappy(u);
};
 

You could even shorten the toString by replacing it with a template string which will do an implicit toString.

const isHappy = n => {
  if (n === 4) return false;

  const u = [...`${n}`].reduce((ac, c) => ac + (c ** 2), 0);

  return u === 1 || isHappy(u);
};
 

Looking at your solution it actually fails later in the mix. I was pretty sure you couldn't rely on the numbers not adding up to a single digit happy number (which the only other one beyond 1 is 7.)

1111111 is a happy number which will become 7 after the first iteration and 7 is a happy number. This fails your current function. Here is an updated one that would work by testing if these ever hit 4 instead of length of 1.

function isHappy(n) {
    const u = n.toString().split('').reduce(((ac,cv) => ac + Math.pow(cv,2)), 0);
    if (u === 1) return true;
    if (u === 4) return false;
    else return isHappy(u);
}
 

Hmmm, good catch :D Although the fact you found all the sad numbers end in 4 is even more interesting to me.🤔🤔

I read the wikipedia article cause I was like "wait if it's not happy wouldn't that go in to an infinite loop?" :)

The number 42 is also in that loop, by the way. :)

 

Here is a nice solution in JavaScript:

const getDigits = n => Array.from(String(n)).map(c => parseInt(c))

const getSquaredDigitsSum = n =>
  getDigits(n)
    .map(n => n ** 2)
    .reduce((a, b) => a + b, 0)

const isHappy = n => {
  const _isHappy = ([n, ...previousSteps]) =>
    previousSteps.includes(n)
      ? n === 1
      : _isHappy([getSquaredDigitsSum(n), n, ...previousSteps])
  return _isHappy([n])
}

Then you can play with generators for instance:

const nextHappyNumber = n => (isHappy(n) ? n : nextHappyNumber(n + 1))

function* getHappyNumbersIterator() {
  let n = 0
  while (true) {
    n = nextHappyNumber(n + 1)
    yield n
  }
}

const findFirstHappyNumbers = n =>
  [...Array(n)].map(() => iterator.next().value)

const happyNumbers = findFirstHappyNumbers(20)
// => 1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97,100
 

Another quick PHP one. Betting there is a more performant method but will leave that to someone else. :)

<?php

function isHappyNumber ($oldNumber) {
  $numArray = str_split($oldNumber);
  $newNumber = 0;
  foreach ($numArray as $val) {
    $newNumber += $val*$val;
  }
  if ($newNumber === 1) {
    return true;
  } else if ($newNumber === 4) {
    return false;
  } else {
    return isHappyNumber($newNumber);
  }
}



$happyNumbers = array();

for ($i = 1; $i < 100; $i++) {
  if (isHappyNumber($i)) {
    $happyNumbers[] = $i;
  }
}

print_r($happyNumbers);

?>
 

How does this look? I initially had happy memoizing previous numbers, but it seemed like it ran fast enough without it, and the memoizing cluttered things up.

Also, I didn't know about the digits method until now! :)

def happy_numbers
  Enumerator.new do |out|
    1.step do |i|
      out << i if happy?(i)
    end
  end
end

def happy?(num)
  already_seen = []
  current_step = num
  until current_step == 1 || already_seen.include?(current_step)
    already_seen << current_step
    current_step = square_digit_sum(current_step)
  end
  current_step == 1
end

def square_digit_sum(num)
  num
    .digits
    .map { |x| x**2 }
    .sum
end

emitter = happy_numbers
puts emitter.first(10)

# => 1, 7, 10, 13, 19, 23, 28, 31, 32, 44
 

Adding a solution in Haskell:

-- core function; read from bottom to top

f :: Int -> Int
f = sum          -- Sum up the squares
  . map ((^2)    -- Compute squares
         .read   -- Convert digit strings to Ints
         .(:[])) -- Explode number string to list of digit strings
  . show         -- Convert input number to string

-- This is a folding pattern with a tricky break condition,
-- depending on the list element and the accumulator.

foldP :: (a -> b -> b) -> (a -> b -> Bool) -> b -> [a] -> b
foldP f p acc [] = acc
foldP f p acc (x:xs) | p x acc = acc
                     | otherwise = foldP f p (f x acc) xs

-- Cut off a list's tail, once a number is repeating.
-- (reverts the preserved part of the list)

cut :: Eq a => [a] -> [a]
cut = foldP (:) elem [] -- fold by appending and checking if x is already in list

-- Iterate the core function, cut the result list and check if the final
-- result is 1.

isHappy :: Int -> Bool
isHappy = (== 1) . head . cut . iterate f

main = print $ filter isHappy [1..200]

Note that Haskell function composition with the (.) operator is read from right to left (or from bottom to top, respectively). The hardest part for FP is folding with a non-trivial break condition, here.

 

And now that I have learned a simpler break condition for the problem, it is easier:

f :: Int -> Int
f = sum          -- Sum up the squares
  . map ((^2)    -- Compute squares
         .read   -- Convert digits to Ints
         .(:[])) -- Explode number string to list of digit strings
  . show         -- Convert input number to string

isHappy :: Int -> Bool
isHappy n | n == 4 = False
          | n == 1 = True
          | otherwise = isHappy (f n)

main = print $ filter isHappy [1..200]

On the other hand, I like the possibility of my original code to see the list of intermediate results to get a feeling for the problem.

 

Here is my solution, to keep me fresh in haskell (I rarely have the possibility to use it in projects and thus never learned it properly):

-- Square summation
squareSum :: [Integer] -> Integer
squareSum = sum . map (^2)

-- Splitting n into its digits
splitNum :: Integer -> [Integer]
splitNum n
  | n < 10 = [n]
  | otherwise = (splitNum $ quot n 10) ++ [n `mod` 10]

-- Check for happiness
isHappy :: Integer -> Bool
isHappy 1 = True
isHappy 4 = False -- 4 is in every unhappy cycle
isHappy n = (isHappy . squareSum . splitNum) n

main = print $ filter isHappy [1..200]
 

I'm glad to see some Haskell here. :) I somehow prefer your computational approach to split the number over my quick string hack. You can easily change the base.

I have done a lot of parsing stuff in Haskell with parsec, attoparsec and readP, lately. So I instantly think of parsing when I see the problem of splitting a number into digits. The detour via strings is comfortable, because it uses the read parser. but

"Challenge" accepted to solve it computationally. :)

To import as few / basic libraries as reasonably achievable, I decided not to use the parsec library but to write a homemade digit parser.

What you do in splitNum reminds me of the quotRem function (that I found when I coded for the Challenge about Kaprekar numbers, here). quotRem just needs a swap to make for a nice digit parser in a very organic way: When dividing by 10 the integer quotient is the state of the state monad (that's still to parse) and the remainder is a parsed digit.

import Control.Monad.State
import Control.Monad.Loops(untilM)

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

-- digit parser
digit :: Integral a => State a a
digit = state $ \s -> swap $ quotRem s 10

-- eof condition
eof :: Integral a => State a Bool
eof = get >>= \s -> return $ s == 0

-- parsing the digits of a number into a (reversed) list of digits
digits :: Integral a => a -> [a]
digits = evalState (digit `untilM` eof)

-- core function
f = sum . map (^2) . digits

-- iteration of f by recursion of isHappy 
isHappy n | n == 4 = False
          | n == 1 = True
          | otherwise = isHappy (f n)

I am a bit biased to use (faster) Ints in my prototypes, and use Integers where really needed, but I adopt your approach with Integers by at least generalizing the code to Integral types.

Although I learned to prefer folds over homemade recursion, I'm afraid the abstractness of foldP is a little bit hard to read, so perhaps I stick with the homemade recursion, this time. :)

 

Can’t resist, here’s a solution in Reason: (Try it)

let rec digits = (n) => n === 0 ? [] : [n mod 10, ...digits(n / 10)];

let squaresSum = (digits) =>
  digits |> List.map((n) => n * n) |> List.fold_left((a, b) => a + b, 0);

let rec isHappy = (n) =>
  switch n {
  | 1 => true
  | 4 => false
  | _ => isHappy(n |> digits |> squaresSum)
  };

let rec nextHappyNumber = (n) => isHappy(n) ? n : nextHappyNumber(n + 1);

let firstHappyNumbers = (nb) => {
  let rec firstHappyNumbersFrom = (nb, found) =>
    if (nb === 0) {
      found
    } else {
      let from = List.length(found) === 0 ? 1 : List.hd(found) + 1;
      let next = nextHappyNumber(from);
      firstHappyNumbersFrom(nb - 1, [next, ...found])
    };
  firstHappyNumbersFrom(nb, [])
};

Js.log(firstHappyNumbers(20));
 

Here is my C# implementation:

private static bool IsHappy(int n)
{
    var u = n
        .ToString()
        .Select(c => int.Parse(c.ToString()))
        .Sum(d => d * d);

    if (u == 1) return true;
    if (u == 4) return false;
    return IsHappy(u);
}
 

Here's a golang implementation, optimized for speed. It takes about 200ms on my machine to find all the happy numbers from 1 to a million on my machine if you take out the prints.

package main

import (
    "fmt"
)

func sumDigitsSquare(n int) int {
    sum := 0
    for n != 0 {
        digit := n % 10
        sum += digit * digit
        n /= 10
    }
    return sum
}

func isHappy(n int, memo map[int]bool) bool {
    if result, seen := memo[n]; !seen {
        result = isHappy(sumDigitsSquare(n), memo)
        memo[n] = result
    }
    return memo[n]
}

func main() {
    memo := make(map[int]bool, 1000000)
    memo[1] = true
    memo[4] = false

    for i := 1; i <= 1000000; i++ {
        if isHappy(i, memo) {
            fmt.Println(i)
        }
    }
}
 
 private static string FindHappyNumbers()
        {
            Console.WriteLine("How many happy numbers do you want to find?");


            int NumbersToFind = int.Parse(Console.ReadLine());
            int[] NumbersFound = new int[NumbersToFind];
            int HappyNumbersFound = 0;
            int startingNum = 1;
            int num = 1;
            const int searchLoopLimit = 10;
            int searchLoops = 0;
            string numAsString = String.Empty;
            bool searchEnded = false;

            while (HappyNumbersFound < NumbersToFind)
            {
                if (searchLoops == searchLoopLimit)
                {
                    searchEnded = true;
                }

                if (searchEnded)
                {
                    ResetLoopWithNextNumber(ref startingNum, ref num, ref searchLoops, ref searchEnded);

                }

                numAsString = num.ToString();
                int sum = 0;
                foreach (var digitChar in numAsString)
                {
                    int digit = int.Parse(digitChar.ToString());
                    sum += (int)Math.Pow(digit, 2);
                }

                if (sum == 1)
                {
                    NumbersFound[HappyNumbersFound] = startingNum;
                    HappyNumbersFound += 1;
                    searchEnded = true;
                }
                else
                {
                    num = sum;
                    searchLoops += 1;
                }
            }

            string FormattedArray = TurnArrayIntoWellFormattedString(NumbersFound);
            return FormattedArray;

        }

 private static void ResetLoopWithNextNumber(ref int startingNum, ref int num, ref int searchLoops, ref bool searchEnded)
        {
            startingNum += 1;
            num = startingNum;
            searchLoops = 0;
            searchEnded = false;
        }

        private static string TurnArrayIntoWellFormattedString(int[] numbersFound)
        {
            string StringToReturn = "";
            int length = numbersFound.Length;

            for (int i = 0; i < length; i++)
            {
                if (i < length - 1)
                {
                    StringToReturn += numbersFound[i] + ", ";
                }
                else
                {
                    StringToReturn += numbersFound[i];
                }
            }

            return StringToReturn;
        }

Here's mine in C#. I feel like this could have been way shorter though. Oh well :p

 
sub happy($value) {
    state %cache = ( 1 => True );
    my $summed = [+] ($value.comb.map(*²));
    return %cache{$summed} with %cache{$summed};
    %cache{$summed} = False;
    %cache{$summed} = happy($summed);
};

(1..200)>>.&{ happy($_)&&.say }

Here's my previously golfed version in perl6 made slightly more readable. Includes a state based cache to reduce recursion. The final line prints the happy numbers up to 200 (well up to the last befor 200)

 

Elm solution which does not use strings. Hopefully quite understandable.

sumDigitSquares sum num =
  if num == 0 then -- exit condition, processed all digits
    sum
  else
    let
      digit = rem num 10 -- get right-most digit
      square = digit * digit
      newNum = num // 10 -- remove right-most digit
    in
      sumDigitSquares (sum + square) newNum


isHappy i =
  if 0 <= i && i <= 9 then -- exit condition, single digit number
    i == 1 || i == 7
  else
    let sum = sumDigitSquares 0 i
    in isHappy sum

Two recursive functions. Exit conditions are getting a number between 0 and 9. Zero is impossible to actually get from other numbers, but there if someone input 0. The only happy numbers in that range are 1 and 7. Should work with negative numbers too.


Here is a runnable solution with UI to test a range of numbers. Try it at elm-lang.org/try.

import Html exposing (..)
import Html.Attributes exposing (..)
import Html.Events exposing (..)
import Task
import Result


sumDigitSquares sum num =
  if num == 0 then
    sum
  else
    let
      digit = rem num 10
      square = digit * digit
      newNum = num // 10
    in
      sumDigitSquares (sum + square) newNum


isHappy i =
  if 0 <= i && i <= 9 then
    i == 1 || i == 7
  else
    let sum = sumDigitSquares 0 i
    in isHappy sum


calculateUpTo i =
  List.range 1 i
    |> List.filter isHappy
    |> CalculateCompleted i


-- UI


type Msg =
  NumberInput String
  | Calculate Int
  | CalculateCompleted Int (List Int)


type Calculation =
  NotStarted
  | Calculating Int
  | Calculated Int (List Int)


type alias Model =
  { userInput : String
  , validatedNumber : Result String Int
  , calculation : Calculation
  }


init =
  { userInput = ""
  , validatedNumber = Err ""
  , calculation = NotStarted
  } ! []


update msg model =
  case msg of
    NumberInput s ->
      { model
        | userInput = s
        , validatedNumber = String.toInt s
      } ! []

    Calculate i ->
      { model | calculation = Calculating i }
        ! [ Task.perform calculateUpTo (Task.succeed i) ]

    CalculateCompleted i list ->
      { model | calculation = Calculated i list } ! []


view model =
  div []
    [ div [] [ text "Check for happy numbers up to" ]
    , div [] [ input [type_ "text", onInput NumberInput, value model.userInput ] [] ]
    , div [] 
      [ case model.validatedNumber of
          Err err ->
            button [ type_ "button", disabled True ] [ text "Calculate" ]
          Ok i ->
            button [ type_ "button", onClick (Calculate i) ] [ text "Calculate" ]
      ]
    , case model.calculation of
        NotStarted ->
          text ""

        Calculating i ->
          div [] [ hr [] [], text ("Calculating up to " ++ toString i) ]

        Calculated i list ->
          div []
            ( [ hr [] [], div [] [ text ("Happy numbers up to " ++ toString i) ] ]
              ++ List.map (\num -> div [] [ text (toString num) ]) list
            )

    ]


main =
  Html.program
    { init = init
    , view = view
    , update = update
    , subscriptions = \_ -> Sub.none
    }
 

A simple Rust Solution

fn is_happy(mut n :i32) -> bool {
    let mut sum = 0;

    while n > 0 {
        let a = n%10;
        n = n/10;
        sum += a*a;
    }

    if sum == 1 {
        return true;
    } else if sum == 4 {
        return false
    }
    is_happy(sum)
}
 

The obvious pythonic way:

from happy import find_happy_numbers

if __name__ == "__main__":
    for number in find_happy_numbers(100):
        print(number)

Jokes aside, here's a Python implementation using simple memoization:

def memoize(fn):
    cache = {}

    def memoized_fn(*args):
        if args in cache.keys():
            return cache[args]

        cache[args] = apply(fn, args)

        return cache[args]

    return memoized_fn


@memoize
def is_happy(n):
    next = sum([int(i)**2 for i in str(n)])

    if next == 1:
        return True
    elif next > 9:
        return is_happy(next)
    else:
        return False


def find_happy_numbers(n):
    for i in range(n):
        if is_happy(i):
            yield i
 

A work in two parts. First, Happy.pm, a Perl5 Module.

package Happy ;

use strict ;
use warnings ;
use utf8 ;
use feature qw{ postderef say signatures state } ;
no warnings qw{ experimental::postderef experimental::signatures } ;

use Carp ;
use Exporter qw( import ) ;
use List::Util qw( sum0 ) ;

our @EXPORT = qw( is_happy ) ;
our %EXPORT_TAGS = ( 'all' => [ @EXPORT ], ) ;
our @EXPORT_OK = ( @{ $EXPORT_TAGS{ 'all' } } ) ;
our $VERSION = 0.0.1 ;

sub is_happy ( $number ) {
    croak 'Not a number' if $number =~ m{\D} ;
    croak 'Not anything' if !defined $number ;
    my %done ;
    while ( $number != 0 && $number != 1 ) {
        return 0 if $done{ $number } ;
        my $output = sum0 map { $_ ** 2 } split m{}, $number ;
        $done{ $number } = $output ;
        $number = $output ;
        }
    return $number ;
    }
1 ;

Which is called by a program.

#!/usr/bin/env perl

use strict ;
use warnings ;
use utf8 ;
use feature qw{ say } ;

use lib '/home/jacoby/lib' ;
use Happy ;

for my $i ( 0 .. 1_000_000 ) {
    say $i if is_happy( $i ) ;
    }

Not particularly golfy, because I like reading and understanding things.

 

F#

let rec extractDigits acc input = 
    if input <= 9 then input::acc  
    else extractDigits (input % 10::acc) (input/10)

let sumOfSquares input = 
    input
    |> List.fold(fun acc i -> acc + i*i) 0

let rec isHappy input =
    if input = 1 then true
    else if input >= 2 && input <=6 then false
    else 
        let newInput = 
            input
            |> extractDigits List.empty
            |> sumOfSquares
        isHappy newInput

[<EntryPoint>]
let main argv =
    [1..10000]
    |> List.filter(fun i -> isHappy i)
    |> List.iter(fun i -> printfn "%d" i)        
    0
 

Here is a ruby implementation.

def is_happy?(number)
  tmp = []

  while (number > 1) && (!tmp.include?(number))
    tmp << number
    # with ruby >=2.4 you can use number.digits
    digits = number.to_s.chars.map(&:to_i)
    number = digits.inject(0) { |total, value| total += value ** 2 }
  end

  number == 1
end
 

Golang Solution

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func isHappyNumber(num int) bool {
    newNum := 0
    switch num {
    case 1:
        return true
    case 4:
        return false
    default:
        s := strconv.Itoa(num)
        digits := strings.Split(s, "")
        for _, i := range digits {
            n, _ := strconv.Atoi(i)
            newNum += n * n
        }
    }
    return isHappyNumber(newNum)
}

func main() {
    fmt.Println(isHappyNumber(94))
}