Project Euler Problem 14

Problem 14

05 April 2002

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Answer: 837799

 

 

Memoization

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    class Program {
        static Dictionary<long, int> lengths = new Dictionary<long, int>();
        static int chainLength(long value) {
            int count = 0;
            long v = value;
            while (true) {
                if (v == 1) {
                    lengths[value] = count + 1;
                    return count + 1;
                }
                if (lengths.ContainsKey(v)) {
                    lengths[value] = count + lengths[v];
                    return count + lengths[v];
                }
                if (v % 2 == 0)
                    v /= 2;
                else
                    v = 3 * v + 1;
                count++;
            }
        }

        static void Main(string[] args) {
            int maxLength = 0;
            long result = 0;
            for (long i = 1; i < 1000000; i++) {
                int c = chainLength(i);
                if (c > maxLength) {
                    maxLength = c;
                    result = i;
                }
            }
            Console.WriteLine(result + " " + maxLength);
            Console.ReadKey();
        }
    }
}

Python

lengths = {}
def chainLength(value):
    count = 0
    v = value
    while True:
        if v == 1:
            lengths[value] = count + 1
            return count + 1
        
        if lengths.has_key(v):
            lengths[value] = count + lengths[v]
            return count + lengths[v]
        
        if v % 2 == 0:
            v /= 2
        else:
            v = 3 * v + 1
        count+=1

def problem14():
    maxLength = 0
    result = 0
    for i in xrange(1, 1000000):
        c = chainLength(i)
        if c > maxLength:
            maxLength = c
            result = i
    print result, maxLength    

problem14()

Racket

#lang racket

(define lengths (make-hash))
(define (chainLength value)
  (define count 0)  
  (let loop ([v value])
    (cond 
      [(= v 1) (hash-set! lengths value (add1 count)) (add1 count)]
      [(hash-has-key? lengths v) (hash-set! lengths value (+ count (hash-ref lengths v)))(+ count (hash-ref lengths v))]
      [else        
       (set! count (add1 count))
       (loop (if (= (remainder v 2) 0)
                 (/ v 2)
                 (add1 (* 3 v))))])))

(define (problem14)
  (define maxLength 0)
  (define result 0)
  (let loop ([i 1])
    (cond [(< i 1000000) (define c (chainLength i))
                         (cond ((> c maxLength) (set! maxLength c) (set! result i)))    
                         (loop (add1 i))]))
  (display (list result maxLength)))

(problem14)

Go

var lengths map[int64]int

func chainLength(value int64) int {
    count := 0
    var v int64 = value
    for {
        if v == 1 {
            lengths[value] = count + 1
            return count + 1
        }
        lv, ok := lengths[v]
        if ok {
            lengths[value] = count + lv
            return count + lv
        }
        if v%2 == 0 {
            v /= 2
        } else {
            v = 3*v + 1
        }
        count++
    }
    return 0
}

func problem14() {
    lengths = make(map[int64]int)
    maxLength := 0
    result := int64(0)
    for i := int64(1); i < 1000000; i++ {
        c := chainLength(i)
        if c > maxLength {
            maxLength = c
            result = i
        }
    }
    fmt.Println(result, maxLength)
}

func main() {
    problem14()
}

C++

map<long long, int> lengths;
int chainLength(long long value) {
    int count = 0;
    long long v = value;
    while (true) {
        if (v == 1) {
            lengths[value] = count + 1;
            return count + 1;
        }
        if (lengths.find(v) != lengths.end()) {
            lengths[value] = count + lengths[v];
            return count + lengths[v];
        }
        if (v % 2 == 0)
            v /= 2;
        else
            v = 3 * v + 1;
        count++;
    }
    return 0;
}

void problem14() {
    int maxLength = 0;
    long long result = 0;
    for (long long i = 1; i < 1000000; i++) {
        int c = chainLength(i);
        if (c > maxLength) {
            maxLength = c;
            result = i;
        }
    }
    cout << result << " " << maxLength;    
}

Javascript

var lengths = {}
function chainLength(value) {
  var count=0
  var v=value
  while(true) {
    if (v==1) {
      lengths[value]=count+1
      return count+1
    }
    lv = lengths[v]
    if (lv!=undefined) {
      lengths[value]=count+lv
      return count+lv
    }
    if (v%2==0) v/=2; else v=3*v+1
    count++
  }
  return 0
}

function problem14() {
    var lengths = {}
    var maxLength = 0
    var result = 0
    for (var i = 1; i < 1000000; i++) {
        c = chainLength(i)
        if (c > maxLength) {
            maxLength = c
            result = i
        }
    }
    alert(result+" "+maxLength)
}

problem14()