Euler Solution 14

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 14

What number in the range 1...1000000 creates the longest chain of steps using the following rules:

  • n is even => n/2
  • n is odd => 3*n + 1

C by SanguineV

Runtime: 231.5ms

/* Brute force approach! */
#include <stdio.h>

unsigned long chain(unsigned long n) {
  unsigned long res = 1;
  while(n > 1) {
    if(n % 2 == 0) {
      n = n/2;
      res++;
    }
    else {
      n = (3*n) + 1;
      res++;
    }
  }
  return res;
}

int main( void )
{
  unsigned long n = 0;
  unsigned long max = 0;
  unsigned long lmax;
  unsigned long i = 800000; /* Assume the number is not below 800000 (correctly)! */
  while(i <= 1000000) {
    lmax = chain(i);
    if (lmax > max) {
      n = i;
      max = lmax;
    }
    i++;
  }
  printf("%u\n",n);
  return 0;
}

Python by Althalus

Runtime: 73 seconds

from math import sqrt
import time
start_time = time.time()

longest = 0
result = 0
for i in range(800000,1000000):
        #I am impatient. Skipping arbirtrary amount.
        #Tried to skip straight to 900,000, lowered it when my answer was wrong.
        n = i
        length=0
        while n > 1:
                if n%2 == 0:
                        n = n/2
                else:
                        n=(3*n)+1
                length+=1
        if length > longest:
                longest = length
                result = i
print(result)
print(length)
run_time = time.time() - start_time
print (run_time)
Personal tools