Euler Solution 74

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 74

Define a factorial chain to be the chain of integers created by taking the digits of a number and adding their factorial successively. I.e.

145 => 1! + 4! + 5! = 145
169 => 1! + 6! + 9! = 363601 => 3! + 6! + 3! + 6! + 0! + 1! = 1415 => 1! + 4! + 1! + 5! = 169
871 => 45361 => 871
78 => 45360 => 871 => 45361 (=> 871)

these have chain length 1, 3, 2 and 4 respectively (the number of elements in the chain before an element is repeated).

The longest factorial chain for a number below 1000000 is 60, how many numbers below 1000000 have exactly 60 elements in their factorial chain?

C by SanguineV

Runtime: 70.635 ms

#include <stdio.h>

// All the possible values of factorial sums of up to 6 digits.
// Note: 1000000 has seven digits but is the same as 100002.
long possibles[] = {..};

// The values for factorials in an array, instant lookup.
long factorials[10] = {1,1,2,6,24,120,720,5040,40320,362880};

// Calculate the sum of the factorials of the digits of "n"
long factDigits(long n)
{
  long res = 0;
  while (n > 0)
  {
    res += factorials[n % 10];
    n = n / 10;
  }
  return res;
}

// Find the number of elements before a repeat occurs, we know the
// upper bound is 60 so don't look beyond that.
int noRep(long n)
{
  long chain[60];
  int iter = 0;
  int check;
  while (iter < 60)
  {
    chain[iter] = n;
    n = factDigits(n);
    iter++;
    check = 0;
    while (check < iter)
    {
      if (n == chain[check])
      {
        return iter;
      }
      check++;
    }
  }
  return -1;
}

/* The fun bit!
 * ALGORITHM:
 * 1. Calculate the chain length for each possible result of a one step
 *    factorial sum of the digits.
 * 1b.  If the chain length is 59 then add this to a short list of
 *      numbers that will create chain length 60s.
 * 2. For each "n" do the factorial sum of the digits once.
 * 3. Check the first reduction of "n" against the elements of known
 *    chain length 59 numbers. If it is there (i.e. chain length 60)
 *    then increment the count. */
int main(void* args)
{
  long n,fdn;
  long c59[100];
  int c59size = 0;
  int count = 0;
  int iter;
  while (count < 4014)
  {
    if (noRep(possibles[count]) == 59)
    {
      c59[c59size] = possibles[count];
      c59size++;
    }
    count++;
  }
  count = 0;
  n = 1;
  while (n < 1000001)
  {
    iter = 0;
    fdn = factDigits(n);
    while (iter < c59size)
    {
      if (fdn == c59[iter])
      {
        count++;
        iter = c59size;
      }
      iter++;
    }
    n++;
  }
  printf("Found %u chains of length 60\n",count);
  return 0;
}

There are potential optimisations by recognising that the order of digits is unimportant for the "possibles", they can be trimmed down to nearly half the number. It is not clear that the overhead of reordering the digits of each one step reduction from "n" is going to be a major speed increase. (I might have implemented this if I was writing in a higher level language, but didn't feel like implementing all the details in C!) It is also possible that by using hashtables or some other O(1) lookup data structures the code can be faster still. That said, I don't think I will optimise this further in C... maybe another language next time.

Haskell by SanguineV

Runtime: ~72 seconds

{- Define factorial in the usual way. -}
fact :: Integer -> Integer
fact n | n < 2 = 1
fact n = n * (fact (n - 1))

{- Return the number created by adding the factorial of the digits of a number. -}
facDigs :: Integer -> Integer
facDigs n | n < 10 = fact n
facDigs n = (fact (mod n 10)) + (facDigs (div n 10))

{- Find the length of a factorial chain for a number. -}
facChaLen :: Integer -> Int
facChaLen n = inner [n]
  where
    inner :: [Integer] -> Int
    inner xs | elem (facDigs (head xs)) xs = length xs
    inner xs = inner ([(facDigs (head xs))] ++ xs)

{- Find all the numbers less than 1000000 with factorial chain lengths equal to 60,
 - print how many of them there are. -}
main = print (length (filter (\x -> facChaLen x == 60) [1..1000000]))

Python by Althalus

Revised after realising I'm an idiot. Could possibly optimise further, but this gets it to below a minute. Previous solution left up for continuity. Runtime: 29.8 seconds

import time
start_time = time.time()

total=0
#Why bother calculating? We only need factorials of 0 - 9.
f = [1,1,2,6,24,120,720,5040,40320,362880]
#Let's keep a list of chains that we know the value for already.
chains={}
for i in range(1,1000001):
        chain=[]
        count=0
        n = i
        while not n in chain:
                try:
                        #If we've already found the chain value for this value of n, why recalculate it? Grab from our list, and end.
                        count += chains[n]
                        break
                except KeyError:
                        #Python threw an error, which means we don't know this n's chain value. Keep going.
                        chain.append(n)
                        ns = str(n)
                        n = sum(f[int(d)] for d in ns)
                        count+=1
        #Record the chain value for the first value of n in this chain.
        chains[chain[0]] = count
        if count == 60: total+=1
print total
run_time = time.time() - start_time
print(run_time)


Runtime: 738 seconds

Looks like I found one of thomas's easter eggs...

import time
start_time = time.time()
def f(n):
        result=1
        while n > 0:
                result *= n
                n-=1
        return result

total=0
for i in range(1,1000001):
        chain=[]
        count=0
        n = i
        while not n in chain:
                chain.append(n)
                ns = str(n)
                n = sum(f(int(d)) for d in ns)
                count+=1
        if count == 60: total+=1
print total
run_time = time.time() - start_time
print(run_time)
Personal tools