Project Euler #95: Amicable chains

  • + 0 comments

    Very easy after all the training from previous problems. At the beginning, generate a list of all sums of factors in a manner similar to how we use Sieve of Eratosthenes. You may refer to Problem 21 which is related to amicable numbers.

    Then use a queue to trace the chain for every iteration, and only update the answer if an occurrence of the first element in the chain is found (though you would still have to break the chain if there is any repeating element, otherwise it will never quit). You may refer to Problem 74 which is related to measuring the length of a chain.

    Note that every member in the same chain has the same length, so once you are done with the smallest member, you won't have to care about the rest. As a result, you should store the intermediate elements you've gone through so you don't have to do the same thing again, as they are definitely not a smallest element in the chain, or you would have seen them before (because you've finished every candidate smaller than it before this iteration step).

    And, you may have noticed, that not every number can form a chain in this case. For example, when you hit a prime number, it goes to and stops at .