I took quite a leave of absence from my little dev blog. The fun thing is that I actually got a hell lot of coding done in the meantime. I completed a couple of Project Euler challenges and was very active on freeCodeCamp where I stumbled through 330 lessons, scripting tasks and full blown projects so far. After achieving the camp’s Front End Development Certification as well as its Data Visualization Certification I left CodePen for good and moved on to GitHub and Glitch, “the friendly community where you’ll build the app of your dreams”, to work on API projects like a timestamp microservice or an URL shortener. Ah, and I was fighting some Flexbox Zombies and joined Wes Bos’ fantastic JavaScript30 online course. Not to forget my full time gig as a developer and project lead in the telco industry. Meaning that I have a lot of unwritten posts in my queue.

I actually stopped blogging more than half a year ago when I threw in the towel trying to understand a fellow Project Eulerian’s solution to this amicable numbers problem. But now it’s finally time to finish what I started.

As this is already the fifth post on amicable numbers you can get the full story here, here, here and here.

The following quote…

In fact this can be even improved on using the prime factorisation of n.
If we know the prime factorisation if n it is easy to calculate the sum of the divisors of n from that.

…pointed my attention to an article on mathschallenge.net about working out the sum of divisors. This is when my monkey brain gave in.

The part I just couldn’t figure out was the line starting with “Hence…” until it finally made click a couple of days ago. And it is so simple that I’m still angry about my own stupidity and giving up so easily.

This part is obvious:

Looking at the left-hand side of the equation, all I have to do is to factor out σ(p^a) and divide by (p−1). That’s it. Struck by blindness.

mathchallenge doesn’t provide a proof, which I would not have understood anyway, but gives a sample calculation instead:

I now have a handy formula to calculate the sum of divisors but I am still working with powers of prime numbers only. What about the sum of divisors of a non-prime e.g. 72?

[…] the usefulness of the function, σ(n), is its multiplicativity, which means that σ(a×b×…)=σ(a)×σ(b)×…, where a, b, …, are relatively prime.

mathchallenge’s example:

I see, all I have to do is to factorize a number until I remain solely with factors, which itself are relatively prime.

How can this be used to further improve my code? This is the sample solution provided by the Eulerian hk, which I translated to a bit more verbose Java code.
What am I doing here? A dry-run of this algorithm is pretty boring. So I will stick to one sample run using 72 as input number, as I already know the result, which should be 195.

Therefore I start with 72 as num, 1 as sum and 2 as p.

First let’s see if 2 times 2 is less or equal to num or num greater than 1. This prevents me from checking prime factors greater than num itself and of course I have to terminate my while-loop somehow.

Now, I check if 72 can be divided by p without remainder. As 72 % 2 == 0 is true I will continue.

I introduce a variable j and give it the value of 2 times 2 equals 4. And I divide 72 by 36, which is my new value for num.

As long as num can be divided by p without remainder I will be stuck in the inner while-loop. 36 % 2 == 0 → true, 18 % 2 == 0 → true, 9 % 2 == 0 → false. I am out of here. Meanwhile j got increased to 16.

I am now able to calculate the first part of the sum. This is where the formula shown above comes in. 1 * (16 – 1) / (2 – 1) = 15.

Having the number 2 factored out, I will continue with 3 as new value for p.

Note that num is now only 9. But we are still caught in the outer while-loop, as 3 times 3 equals 9, which is less or equal to 9 and greater than 1.

Because 9 can be divided by 3 without remainder, we calculate a new value for j, which is 3 times 3 equals 9. num becomes 9 / 3 = 3 and we enter the inner while-loop again.

j turns into 27.

15 * (27 – 1) / (3 – 1) = 195.

And now we are out of the outer while-loop.

The line if (num > 1) {sum=sum * (num + 1);} only covers the case that one prime factor greater than num remains. This is not the case this time as num got reduced to 1.

Finally done! Party time, excellent!

I guess this will be my last post about Project Euler problems. I just had to finish this. Remember “Always be closing”. But I highly doubt the usefulness of posts like this one. (A) It’s very unlikely that anyone who is smart enough to figure this stuff out will actually read my blog. (B) I’m just a stupid guy trying to get better at what I do. There are already way better resources available online. I know, ’cause I used them myself. (C) I really should respect Project Euler’s advice:

[…] It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.