Euleryx Project 21 – Amicable Numbers

[Pilsner]

Euleryx Problem 21 – Amicable Numbers

My workflow:

Spoiler

 Workflow:

Answer: 31626

Last Week's Favourite Solution:

It was great to see the different adaptations of the macros from earlier projects. The solution that stood out most was by @AncientPandaman, for not just creating a big int calculator macro, but also separating the process out into two additional macros, one of which can separate out the digits into a single column, and another which can reconstruct the final Big INT answer. This separation will most likely prove useful in future problems. Please find their solutions on page one of last week's post or click here.

Mathematical Theory:

Like several other, this problem focuses on factors. The first problem is to list all factors of a given number. If you were doing this by hand, one of the most reliable ways to get all the factors would be as follows.

Approach 1:

Firstly, list all the prime factors. We first discussed how you can do this back in Project 3. The reason this is useful is that we know that, unlike other factors, the prime factors cannot be broken down anymore. Following this thought process, we know that all other factors must be products of the prime factors. Lets take 24 as an example:

24 has prime factors 2,2,2,3

If we multiply all the prime factors by each other, we should get all the factors of 24:

• 2 X 2 = 4
• 2 x 3 = 6
• 2 x 2 x 2 = 8
• 2 x 2 x 3 = 12

Meaning, that all the factors of 24, are 2, 3, 4, 6, 8, 12 (which is correct).

Now I would love to plug the prime factor macro from problem 3 in here, to get off to a flying start; however, it is important to consider all options. Another way of finding the factors is simply to test different numbers. But, as some of you have pointed out in the past, instead of testing all numbers, we only need to test those, less than the square root of our starting value. This is because all factors come in pairs.

Approach 2:

 

Knowing that all factors come in pairs, if we can find just one of the numbers in the pair, it is then easy to find the other (simply divide the starting number by the one known factor). A key fact is that one factor, is always less than the square root, and the other is greater than the square root (unless it's exactly equal to the root). Lets take 100 as an example.

The square root of 100, is 10. The factor pairs of 100 are:

• 2, 50
• 4, 25
• 5, 20
• 10, 10

As you can see, all factor pairs have one number greater than (or equal to) and one number less than (or equal to) the square root.

A more mathematical way to consider this is as follows. Let's say we have a number “n” and it has a square root = x, we can then state that

Let's say we want to test another factor. To do so, we will add one to one of the x values, so we are testing to see if (x+1) is a factor.

But if we do (x+1) * x, we will end up with:

We already know that n = x * x, so we know for sure that (x * x) + x will be bigger than n. This means that the factor pair for (x+1) must be less than x.

This same idea follows whether you add 1, 10, 500 etc to the square root, so we can say with confidence that in a factor pair, one number is always greater than, and the other less than, the square root. If we can therefore find one factor, below the square root, we can easily calculate the other. 

Which approach is best:

Whilst I think the first approach is easier by hand, the second approach of just testing all factors less than a number's square root, is likely to be quicker using a computer (at least for small data), as it avoids the need for an iterative macro. In this particular case, we only need to worry about numbers from 1 – 10,000 (relatively small data), so I decided to take approach 2.  

Method:

1) Step one was to create a list of all whole numbers up to 10,000.

2) Now, for each of those numbers, generate rows up to and including the square root of the number.

3) Find the factor pair for all of these potential factors, then confirm it is a valid factor pair, by filtering to pairs where both numbers are integer values.

4) Next pivot the data so we have a single column, containing all the factors.

5) Remove any factors equal to the starting number, and them sum all the remaining unique factors (per starting number).

6) Join the data back to itself to see where the number = factor sum and factor sum = number. These are the amicable number pairs.

7) Sum the amicable numbers to get to the answer.

8) Submit your answer to the Project Euler Website!

 

Summary:

Another problem testing our ability to deal with factors. This time round there were a couple of approaches, by weighing up the options in terms of worklfow optimisation lead us to the final solution.

Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.