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.
- 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.
- 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.
