Sum Square Digits Sequence

April 27, 2018

Here is our solution, with help from the Standard Prelude; we short-circuit the loop by stopping as soon as any member of the loop is found:

(define (ssds n) ; sum square digits sequence
  (let loop ((n n) (ns (list)))
    (if (or (= n 1) (member n '(4 16 37 58 89 145 42 20)))
        (reverse (cons n ns))
        (let ((x (sum (map square (digits n)))))
          (loop x (cons n ns))))))

Here are two examples:

> (ssds 19)
(19 82 68 100 1)
> (ssds 18)
(18 65 61 37)

You can run the program at https://ideone.com/Ro26ys. There is more to the topic of Happy Numbers than we have discussed here; oeis.org is a good place to learn more.

Advertisements

Pages: 1 2

9 Responses to “Sum Square Digits Sequence”

  1. Zack said

    Although the problem is ill-defined (there is a case of a number being neutral, i.e. neither happy or sad), we’ll look at the case where the number is happy if and only if the end result is 1. Here is my take with Julia.

    global sad = [4, 16, 37, 58, 89, 145, 42, 20];

    function DigitsOf(n::Int64)
    digits = split(string(n), “”)
    z = length(digits)
    Z = Array{Int64}(z)

    for i = 1:z
        Z[i] = parse(Int64, digits[i])
    end
    
    return Z, z
    

    end

    function IsHappy(n::Int64)
    D, nd = DigitsOf(n)
    S = [n]

    while nd != 1              
        s = 0
    
        for d in D
            s += d^2
        end
    
        D, nd = DigitsOf(s)
        push!(S, s)
    
        if S[end] in sad; return false, S; end
    end
    
    if S[end] == 1
        return true, S
    else
        return false, S
    end
    

    end

    IsHappy(19)
    (true, [19, 82, 68, 100, 1])

    IsHappy(18)
    (false, [18, 65, 61, 37])

    IsHappy(111)
    (false, [111, 3])

    Whatever the case, creative problems like this can make someone quite happy, for sure. Happy weekend everyone!

  2. mcmillhj said

    Perl6 solution with a simple loop:

    #!perl6
    
    sub is-happy(Int:D $n --> Bool) {
      $n == 1;
    }
    
    sub is-sad(Int:D $n --> Bool) {
      ?(4, 16, 37, 58, 89, 145, 42, 20).first: * == $n;
    }
    
    sub ssds(Int:D $n --> List) {
      my @seq = (($n),);
      repeat {
        @seq.push([+] @seq[* - 1].polymod(10 xx *).map({ $_ * $_ }));
      } while !(is-happy(@seq[* - 1]) or is-sad(@seq[* - 1]));
    
      @seq;
    }
    
    say ssds(19); # [19 82 68 100 1]
    say ssds(18); # [18 65 61 37]
    
  3. Scott McMaster said

    Here is my Golang solution, with a disclaimer that I’m just learning Go and so far don’t like it very much:

    package main

    import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
    "strings"
    )

    func main() {
    reader := bufio.NewReader(os.Stdin)

    for {
    fmt.Println("Enter a positive number >= 1, or negative number to quit: ")
    text, _ := reader.ReadString(‘\n’)

    i, err := strconv.Atoi(strings.TrimSpace(text))
    if err != nil {
    fmt.Println("Please enter a number")
    continue
    }

    if i <= 1 {
    fmt.Println("Bye")
    break
    }

    typ, sequence := happyOrSad(i)
    fmt.Printf("%d is %s and the sequence is %v\n", i, typ, sequence)
    }
    }

    func happyOrSad(num int) (string, []int) {
    seen := make(map[int]bool)
    seq := []int{num}
    for num != 1 && !seen[num] {
    seen[num] = true
    cur := num
    num = 0
    for cur > 0 {
    num += int(math.Pow(float64(cur%10), float64(2)))
    cur /= 10
    }
    seq = append(seq, num)
    }
    var typ string
    if num == 1 {
    typ = "happy"
    } else {
    typ = "sad"
    }
    return typ, seq
    }

  4. Scott McMaster said

    Here is a pastebin of the above code (thought WordPress formatted Go these days).

  5. Globules said

    Here’s a Haskell solution. (I’m calling the sequence a “Porges sequence”.)

    import Data.Bool (bool)
    import Data.List (intercalate, unfoldr)
    import Data.Tuple (swap)
    
    -- The infinite "Porges" sequence starting at the given number.
    porges :: Integral a => a -> [a]
    porges = iterate (sum . map (\i -> i * i) . digits)
    
    -- The prefix of the Porges sequence starting at 'n' and ending on the first
    -- repeated number.
    finitePorges :: Integral a => a -> [a]
    finitePorges n = let (is, j:_) = break (\i -> i == 1 || i `elem` cyc) $ porges n
                     in is ++ bool (take (length cyc + 1) (porges j)) [j] (j == 1)
    
    showPorges :: (Integral a, Show a) => a -> String
    showPorges n = intercalate ", " (map show $ finitePorges n) ++ ", ..."
    
    -- The cycle into which a Porges sequence might fall.
    cyc :: Integral a => [a]
    cyc = [4, 16, 37, 58, 89, 145, 42, 20]
    
    -- The list of a number's base-10 digits, from least to most significant.
    digits :: Integral a => a -> [a]
    digits = unfoldr (\i -> bool Nothing (Just . swap $ i `quotRem` 10) (i /= 0))
    
    main :: IO ()
    main = do
      putStrLn $ showPorges 1
      putStrLn $ showPorges 18
      putStrLn $ showPorges 19
    
    $ ./porges
    1, ...
    18, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, ...
    19, 82, 68, 100, 1, ...
    
  6. Alex B said

    Python 3 version, one function to generate the sequence, terminating with either a known sad number or 1, and one function to check the ‘happiness’ of a number:
    I used mathematical operations to find the sum of squared digits, rather than casting to string, although Python does make that easy :)

    def happy_seq(n):
    	terminators = {1, 4, 16, 37, 58, 89, 145, 42, 20}
    	seq = [n]
    	while seq[-1] not in terminators:
    		n, r = seq[-1], 0
    		while n:
    			r, n = r + (n%10)**2, n // 10
    		seq.append(r)
    	return seq
    
    def is_happy(n):
    	return happy_seq(n)[-1] == 1
    
  7. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char* argv[]) {
      if (argc != 2) {
        fprintf(stderr, "Usage: sum_square <NUMBER>\n");
        return EXIT_FAILURE;
      }
      int num = atoi(argv[1]);
      int terminals[] = {1,4,16,37,58,89,145,42,20};
      size_t n_terminals = sizeof(terminals) / sizeof(int);
      while (1) {
        printf("%d\n", num);
        for (size_t i = 0; i < n_terminals; ++i) {
          if (num == terminals[i]) goto exit;
        }
        int sum = 0;
        while (num != 0) {
          int digit = num % 10;
          sum += digit * digit;
          num /= 10;
        }
        num = sum;
      }
    exit:
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./sum_square 19
    19
    82
    68
    100
    1
    ./sum_square 18
    18
    65
    61
    37
    
  8. Daniel said

    “Although the problem is ill-defined (there is a case of a number being neutral, i.e. neither happy or sad)…”
    – Zach @ April 27, 2018 at 1:19 PM

    @Zach, the problem mentions and links to a proof that all natural numbers are either “happy” or “sad”. I think this contradicts there being any “neutral” numbers.

  9. Daniel said

    Zach -> Zack

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: