DEV Community

Write a script to find "Happy Numbers"

Peter Kim Frank on February 05, 2018

These challenge posts have been a lot of fun. Another one inspired by Fermat's Library. // Detect dark theme var iframe = document.getElem...

Read full post

Sebastien Castiel • Feb 6 '18 • Edited

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

Richard Orelup • Feb 5 '18 • Edited

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

?>

Ryan Palo • Feb 6 '18 • Edited

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

Meghan (she/her) • Feb 5 '18 • Edited

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

RevanProdigalKnight • Feb 6 '18 • Edited

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

Nick Taylor • Feb 6 '18

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

Richard Orelup • Feb 5 '18

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

Meghan (she/her) • Feb 6 '18

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

Richard Orelup • Feb 6 '18

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

Heiko Dudzus • Feb 6 '18 • Edited

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.

Heiko Dudzus • Feb 7 '18 • Edited

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.

Jay • Feb 6 '18

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

Kasey Speakman • Feb 6 '18 • Edited

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
    }

Michael Neu • Feb 6 '18

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

Jan • Feb 6 '18

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

Dave Jacoby • Feb 6 '18

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.

Heiko Dudzus • Feb 7 '18 • Edited

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

Sebastien Castiel • Feb 7 '18 • Edited

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

Colin Kiama • Feb 12 '18

 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

NAVID MANSURI • Feb 4 '21

bro log code is not good......

Colin Kiama • Feb 4 '21

Thanks for letting me know.

What should I change so that my code improves?

NAVID MANSURI • May 28 '21

your feedback...
your code write is good and logic is also good , but you code very long ,,,

so, listen ,try to write code small, simpal

Vinay Pai • Feb 13 '18

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

Simon Proctor • Feb 6 '18

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)

Vikas Uikey • Feb 9 '18 • Edited

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

Bohdan Stupak • Feb 7 '18

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

Davide Santangelo • Feb 6 '18 • Edited

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