Project Euler Problem 95 Solution

Project Euler Problem 95 Statement

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of $28$ are $1$, $2$, $4$, $7$, and $14$. As the sum of these divisors is equal to $28$, we call it a perfect number.

Interestingly the sum of the proper divisors of $220$ is $284$ and the sum of the proper divisors of $284$ is $220$, forming a chain of two numbers. For this reason, $220$ and $284$ are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with $12496$, we form a chain of five numbers: $$12496 \to 14288 \to 15472 \to 14536 \to 14264 (\to 12496 \to \cdots)$$

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

Solution

HackerRank Project Euler Problem 95 overview:

Find the longest amicable chain among numbers up to a given upper bound \( L \) and prints the smallest member of that chain. An amicable chain is formed by repeatedly taking the sum of proper divisors of a number until the sequence loops back to the starting number.

Solution Summary

The divisor sums are computed using a sieve-like method. For each $i$ (from 1 to $L/2$), all its multiples up to $L$ have $i$ added to their divisor sum. For each number $i$ not already in the seen{} cache, a chain is built by repeatedly replacing the current number by the sum of its proper divisors (from the ds[] array). If the chain eventually comes back to $i$, then an amicable chain has been found.

Each number that is part of a computed chain is cached in seen{} with its chain length. This prevents reprocessing numbers that have already been explored. The program keeps track of the longest chain length found and updates the answer to the starting number of that chain. In the end, it outputs the smallest member of the longest amicable chain.

Solution Detail

1. Building the Divisor-Sum Array

First, the program reads the integer \( L \) and creates an array ds[] of length \( L+1 \). This array will hold the sum of proper divisors for each integer from 1 to \( L \).

The nested loops update ds[] by iterating from 1 to \( \lfloor L/2 \rfloor \). For each divisor \( i \), the inner loop adds \( i \) to every multiple of \( i \) (starting from \( 2i \) up to \( L \)).

L = int(input()) 
ds = [0] * (L + 1)
for i in range(1, L // 2 + 1):
    for j in range(i * 2, L + 1, i):
        ds[j] += i

2. Detecting Amicable Chains

Next, the program uses an outer loop over all numbers from 1 to \( L \) to find amicable chains. Three main variables are used:

• ans: The smallest member of the longest chain found.
• longest: The length of the longest chain discovered so far.
• seen{}: A dictionary that caches the chain lengths of numbers that have already been processed. This avoids redundant work.

For each number \( i \) that has not been cached in seen{}, the program initializes:

• ch: A set to store the numbers in the current chain for fast membership tests.
• path: A list that records the sequence of numbers visited, in order.
• c: The current value initialized to \( ds[i] \), the sum of proper divisors of \( i \).

The while loop continues as long as:

• \( c \leq L \) (to stay within bounds),
• \( c \geq i \) (to ensure we only process new chains), and
• c is not already in the current chain ch.

In each iteration, c is added to the chain and the path, then updated to \( ds[c] \).

When the loop exits, if c == i then we have found an amicable chain that loops back to the starting number.

ans, longest, seen = 0, 0, {}
for i in range(1, L + 1):
    if i not in seen:
        ch, c, path = {i}, ds[i], [i]
        while c <= L and c >= i and c not in ch:
            ch.add(c); path.append(c); c = ds[c]
        if c == i:
            l = len(ch)
            if l > longest:
                longest, ans = l, i
            for x in path:
                seen[x] = l

3. Output

Finally, the program prints ans, which is the smallest member of the longest amicable chain discovered.

print(ans)

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 95

HackerRank Project Euler 95: Given a set of $m$ distinct digits, $S$, find the largest possible integer $n$ such that each integer from $1$ to $n$ is expressible using elements of $S$ and following the above rules. If $1$ is also not expressible, output $0$ instead.

Last Word

After running this program for different $L$, the following pattern emerged:

n = input()
if n < 284: print 6
elif n < 15472: print 220
elif n < 629072: print 12496
else: print 14316

Here’s a step-by-step explanation:

• For n < 284: Only trivial chains can form when n is very small. The smallest amicable chain in this case is simply the number 6 (which is a perfect number), so the script outputs 6.
• For 284 ≤ n < 15472: In this range, the longest valid chain available is the amicable pair (220, 284). The smallest amicable pair $(220,284)$. Therefore, the script prints 220.
• For 15472 ≤ n < 629072: A longer chain exists in this interval with its smallest member being 12496. Hence, when the input falls in this range, the script outputs 12496.
• For n ≥ 629072: When the range is large enough to include the famously longest chain under one million (of length 28, which is the full solution to Problem 95), the smallest member of that chain is 14316. Thus, the script outputs 14316.

Expressing the Logic in Mathematical Terms

The solution uses the following piecewise function to determine the answer:

Precomputation. Knowing the correct answers for different ranges of n (6, 220, 12496, and 14316) allows for an extremely efficient and simple implementation. When a user inputs a number n, the script simply checks which range it falls into and outputs the corresponding answer. This method is not only fast but also sidesteps the complexity of divisor-sum calculations during runtime.