Friday, January 24, 2014

Project Euler 21-25

Project Euler Solutions for Questions 21-25

Two of the problems require finding the sum of all proper divisors of a number.   The algorithm needs to be reasonably efficient, since it is iterated over a non-trivial set of numbers (e.g. all integers from 1 to 10,000).

The approach I've implemented runs well enough (about 1 second for all integers from 1 to 10,000), but I suspect there's a much faster approach to part 2.
  1. As an optimization step, pre-generate a list of primes via a sieve.  Decompose each number into its prime factors, e.g. [2, 2, 7]  for the number 28.

  2. For each number, generate the list of proper divisors from the list of prime factors via the following steps:

    • Generate the power set of the list of prime factors.  Trim the head (the empty element) and the tail (the sum product of which is the number itself).  Using [2, 2, 7] as an example, the trimmed power set  is [[2], [2, 2], [7], [2, 7]].

    • For each list in the power set, find the sum product. Including the number 1 as a divisor, this results in [1, 2, 4, 7, 14].

    Given the list of proper divisors, take its sum, e.g. 1 + 2 + 4 + 7 + 14 = 28.