Project Euler – Amicable numbers (Part 4)

Apparently my function to get the sum of all proper divisors can be highly improved. Full credit goes to a Project Euler member running by the name “hk”. Yesterday evening was well spent working through his solution and explanations.

This was my first shot…

screenshot_388.png

Now, looking at the code snippet above, I guess that I must have had a bit of a bad day (sum = sum + 1; instead of plain and simple int sum = 1;). Let’s scrap this one. It’s a brand new day.

Next try…this is a “naive” version “hk” starts iterating on.

screenshot_390.png

At least to me it looks like some ambiguity exists about the nature of proper divisors. For example, given the number 54, is 1 a proper divisor or not? What about 54 itself? As I am not a mathematician but majored in Japanese Studies, let’s have look at Wolfram MathWorld.

A positive proper divisor is a positive divisor of a number n, excluding n itself

Ok…I didn’t know that. New knowledge gained. 1 is a proper divisor of 54, 54 itself is not. Perfect!

But back to improving my function. Let’s use the number 40 as an example. Its proper divisors are 1, 2, 4, 5, 8, 10 and 20. Do I really have to check every single number between 2 and 40? No. Why?

In case I have already figured out that 2 is a proper divisor of 40, I know that 20 is a proper divisor as well. Same for 4 and 10. And so on…Therefore I only need to iterate up to the square root of my input number. My previous attempt i <= num / 2 was a step in the right direction but still did check too many unnecessary numbers. Given my example of num = 40, I only have to go up to 6 instead of 20.

1
2, 20
4, 10
5, 8

Using some fancy language I found on codereview.stackexchange.com:

You can actually stop checking at Math.sqrt(num)because the current divisor always yields its conjugate.

That’s how my function has changed.

screenshot_391.png

Given num = 40 everything looks fine. But what about 36? How does my function handle duplicates, namely twice the number 6 (6 * 6 = 36)?

The proper divisors of 36 are, 1, 2, 3, 4, 6, 9, 12 and 18. Therefore the return value should be 55. Ups, I got 61 (55 + 6). Duplicates are not yet taken into account. Temporary fail.

screenshot_393.png

sumOfProperDivisiors(40) = 50, sumOfProperDivisiors(36) = 55. Nice.

But I am still not done improving.

A second improvement comes from the realisation that odd numbers cannot have even numbers as divisors. (The converse is not true: even numbers can have odd divisors).

screenshot_394.png

What does “hk” want to tell me here? First part is easy, in case the input is 1 simply return 0. No proper divisors of 1 exist.

screenshot_394 Kopie.png

Also, there seems to be no new information regarding the range of numbers to check, up to the square root is enough.

screenshot_394 Kopie.png

Now handing the perfect square case.

screenshot_394 Kopie.png

sum = 1 + r: In case of a perfect square I can increase the value of sum immediately by the square root of n (which is r). Plus 1, as I am dealing with a number larger than one. I can be certain that 1 is a proper divisor as well.

sum = 1: Regarding all other cases, I have to start with a sum of value 1.

r = r – 1: And, I do not have to iterate up to the square root value of r anymore, as this is already covered. Therefore r = r -1.

Now it gets interesting.

screenshot_394 Kopie.png

f is the number to start the while-loop with. Either 3 for odd numbers, or 2 for even ones. For odd numbers the step size will be 2, for even numbers 1. Remember “that odd numbers cannot have even numbers as divisors”. For an odd one it does not make any sense to check 2, 3, 4, 5 and so on. Only 3, 5, 7, 9…are relevant.

And now all I have to do is to iterate, check for a proper divisor and increase the return value accordingly. Done!

screenshot_394 Kopie.png

screenshot_396.png

But wait. What did “hk” just say?

In fact this can be even improved on using the prime factorisation of n.

Hmmmm…..I have to understand this first. “Project Euler – Amicable numbers (Part 5)” is in the making. Quite a journey.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s