Digit fifth powers

This post is going to be a pretty short one. Now that I have tasted blood again, I managed to “solve” another Project Euler problem just before hitting the hay last night. I’m still working on the supposed to be easy ones though.

screenshot_2702.png

I put “solved” in quotation marks due to the massive sledgehammer which I used for arriving at the solution…a simple for-loop. Does 1 satisfy the given definition? What about 2? And 3? Bang! Bang! Bang!

Using a dumb loop was the first thought that occurred to me on how I could solve this challenge and I didn’t get any smarter in the end.

I started by consulting Wolfram MathWorld to find out more about this numerical phenomenon. Just to discover Narcissistic Numbers. Which is NOT the solution to this given problem.

An n-digit number that is the sum of the nth powers of its digits is called an n-narcissistic number.

Below this definition MathWorld displays a nice little table of all the numbers that satisfy this definition up to n equals 39.

screenshot_2705.png

That was easy. For n equals 5 the numbers I was looking for are 54748, 92727, 93084.

Unfortunately…

These are not the numbers you’re looking for.

Obi -Wan Kenobi

Or to be a bit more precise, these are not the only numbers required to reach the target sum.

After several failed attempts to submit 240559 (54748 + 92727 + 93084) I came to the conclusion that most likely I am not smarter than Project Euler and started thinking about what I was missing here.

If you read the problem description carefully, it becomes clear that your search is not limited to n-narcissistic numbers only. For example 4150 is just fine as well:

4150: 45 + 15 + 55 + 05 = 4150.

The number doesn’t have to be precisely n-digits long. I hope this helps.

Now I have to read the forum posts as usual. And then move on to the next problem on my list, Coin sums.

Number spiral diagonals

Last year I made the decision to blog less about Project Euler problems. Especially to stop posting full blown solutions including source code. Still, I want to share interesting challenges and my attempts at solving them.

Number 28, Number spiral diagonals, falls into the category of problems I had to study at least three times just to understand what the description actually wanted to tell me. I’m pretty sure that I’m not the only human being on this planet scratching his head after reading the following lines for the first time:

screenshot_2690.png

Get it? No? Let me explain. Start with the number 1 in the center and then continue clockwise with the next number, 2. Just write it next to the first number. Continue with 3 and 4.

screenshot_2693

Keep going and you will have created a 3 x 3 spiral grid.

screenshot_2694

Add even more numbers…

screenshot_2696.png

Done. A 5 x 5 grid of spirally arranged numbers from 1 to 25. That’s all!

Now let’s have a look at all four diagonals.

screenshot_2697.png

Create the sum of all highlighted numbers: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25. The result is 101.

So far so good. But what about the sum of the diagonals of a 1001 x 1001 spiral grid? This is the actual challenge!

Warning: If you just wanted to understand the problem but prefer to figure it out all by yourself, stop reading now! No implementation details will be given, but enough information to spoil all the fun for you.

My first approach was to simply use Excel. Without any coding at all. Just to get the number and to see how big it actually is. But after approximately two dull minutes of typing numbers into a spreadsheet I threw in the towel. Trying to create such a huge spiral manually is just plain dump. Stupid me.

Then I started banging my head against the wall trying to figure out how to create such a grid programatically. Should I use a list of lists? But how to continue? Therefore back to the drawing board.

I started paying closer attention to the properties of the given 5 x 5 spiral grid. Obviously you start with the 1 in the center. This number is part of every diagonal. It will be counted only once. Therefore the solution most likely looks similar to this highly sophisticated snippet of code: int result = 1 + foo;

First, I tried to reduce the challenge to the smallest possible spiral, a 3 x 3 grid. The numbers located along the diagonals are 3, 5, 7, 9.

Back to the 5 x 5 version: 13, 17, 21, 25.

Next, I created a 7 x 7 spiral on paper. The new diagonal numbers are 31, 37, 43 and 49.

Observation 1: It doesn’t matter how big the spiral gets, for every layer only four numbers are of interest, the corner numbers that are part of the diagonal. 

Which is kind of obvious.

Observation 2: The numbers of interest follow a pattern.

3 x 3 spiral: The next relevant number is the current number + 2.
5 x 5 spiral: The next relevant number is the current number + 4.
7 x 7 spiral: The next relevant number is the current number + 6.

For every additional grid layer the gap between these numbers increases by 2 (2, 4, 6…).

But how to continue from here? That’s not enough to implement a solution yet. What happens after I complete the first 3 x 3 spiral. The last number I need to consider is 9? The first number of interest of the 5 x 5 layer is 13. For the 7 x 7 layer it will be 31.

First numbers of each layer: 3, 13, 31…
Last numbers of each layer: 9, 25, 49…

What if I combine these numbers? Because that’s what I actually need. Based on my second observation I can easily compute the missing numbers for each layer, but I need a starting point.

9 → 13: A difference of 4.
25 → 31: A differente of 6.
49 → 57: A difference of 8.
81 →  91: A difference of 10.

Observation 3: I am able to compute the first relevant number of each layer based on the last number of the previous layer. The gap between these numbers increases by 2 as well. I need to keep count of the layers though.

And this should actually be enough to implement a working solution.

Unfortunately the third observation just occurred to me while typing these lines. While playing with pen and paper I just didn’t see it. But I still solved the challenge using a fourth observation.

I added a few additional layers to my 7 x 7 spiral grid…

screenshot_2698.png

…with the focus on potential patterns inherited in the diagonals. Let’s have a look at the top left one: (1), 7, 21, 43, 73, 111…

And that’s what I noticed:

7 → 21: 14 (initial gap)
21 → 43: 22 (14 + 8)
43 → 73: 30 (22 + 8)
73 → 111: 38 (30 + 8)

And this pattern is true for each and every diagonal.

Observation 4: Every diagonal follows the same pattern. The first step from the 3 x 3 to the 5 x5 layer is unique for each diagonal but then the current gap is always the previous gap + 8.

And that’s the observation I used for coding my solution.

So far I didn’t have a look at the Project Euler forum. But I’m pretty sure the spiral numbers challenge holds far more secrets than I could figure out by myself.

Project Euler – Amicable numbers (Part 5)

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.

dvmjxqrdu1dyqfbbrsgr.jpeg

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.

screenshot_1783.png

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:screenshot_1860.png

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

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

screenshot_1859.png

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:

screenshot_1864.pngI 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.screenshot_1862.png
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.

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.

Project Euler – Amicable numbers (Part 3)

Back at amicable numbers.

My first solution using two nested for-loops was obviously way too slow. But how to improve? I did some reading on the Project Euler forum therefore.

The nested for-loops are gone, only a single loop remains. Also, as I am only interested in the amicable numbers’ sum, it is time to kick out the totally unnecessary ArrayList.

screenshot_387.png

For every number k between 2 and 9.999 I calculate the sum of its proper divisors j. Only in case j is larger than the input k, I calculate the sum of proper divisors for j as well. And compare it back to k.

If you think about it for a second, the check if (j > k) {…} is kind of obvious. A pair of amicable numbers always consists of a smaller and a larger number. My for-loop runs from 2 to 9.999, I will always “find” the smaller number first. The sum of its proper divisors has to be the larger number therefore.

This improvement causes a dramatic increase in execution speed. 10 minutes down to an instant result!

It looks like my function sumOfProperDivisors(int num) can be improved as well. This will become “Project Euler – Amicable numbers (Part 4)”, most likely my final post about this topic.

Fibonacci Fail

The Non-Programming Programmer

(A meeting room somewhere in a giant office building. Early afternoon. Four people sitting around a table. It’s a typical job interview scene. On the table are coffee cups, a glass of water, pen and paper, a laptop.)

Co-worker: “Talking about Java, let’s start with something easy. What’s the difference between an interface and an abstract class?”
Candidate: “…”
Me: “Ok, let’s forget about the interface for now. What is an abstract class?”
Candidate: “…”
Me: “Ok, back to Java 101. Let’s assume we want to model a zoo. Would you use an abstract class to implement a lion?”
Candidate: “…I…guess…not…”
Me: “Thank you very much.” (start playing with my mobile phone)

Unfortunately, this is not an excerpt from a comedic play written to entertain the holy caste of software developers. This has actually happened less than a week ago. Repeat after me: “This actually happened.”

Last year I stumbled across Jeff Atwood’s blog post The Non-Programming Programmer. Which led to Why Can’t Programmers… Program? Which then led to Reginald Braithwaite’s Don’t Overthink FizzBuzz. All these posts fit in nicely with basically all the stuff Steve Yegge wrote about hiring as part of his Drunken Blog Rants.

Mr. Braithwaite’s conclusion:

I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.

And even worse:

Like me, the author is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

Based on my recent experience I totally have to agree.

When I first read all that stuff about FizzBuzz, I assumed that this must be more or less just a bad joke. Or that it might apply to a specific job market. I would have never guessed what I was about to experience once we included a little exercise into our hiring process.

To be able to better compare applicants we restructured or interviewing process. Less chatter, more content. Identical questions for everybody, not too heavy. A little bit about object oriented programming, JPA, estimation techniques, testing and little coding challenge using pen and paper. Even pseudo code is fine.

Fibonacci Sequence

The coding challenge we are using is to make the candidate write a little function that returns a Fibonacci number.

Co-worker: “Have you heard of the Fibonacci sequence?”
Candidate: “…”
Co-worker: “Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 0 and 1, the first 10 terms will be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Could you please use the whiteboard and a pen to “implement” a function that prints out the n-th number of that sequence.
Candidate: “…”
Co-worker: “Feel free to use recursion.”

The Fibonacci numbers are actually part of a Project Euler problem that asks for the sum of the even-valued terms in a sequence whose values do not exceed four million. Give it a try.

So, what do we actually expect?

An iterative approach

Candidate: “Let’s see…I need a function. What about this? return 0 for now. Otherwise it won’t compile (bonus point).

screenshot_52.png

I assume that using int is fine for now. For the return value as well as for the parameter. OK? (Feedback loop, bonus point.)

So, what shall happen in case we call compute(0) or compute(1)? You said the first two numbers, 0 and 1, are always given?

screenshot_51.png

Hmm, what about compute(-1)? Is this defined? Let’s change this (bonus point again).

screenshot_53.png

Now I need to implement the actual algorithm. Let me introduce two variables here, a and b. Far from perfect variable names, but for now a and b should be sufficient.

screenshot_55.png

I need to loop…n <= 0 and n == 1 is taken care of. What about n == 2 and above?

screenshot_57.png

 I need the sum of a and b

screenshot_58.png

But I am not done yet…What do I want to return instead of 0? And I need to store my sum…Let’s store the sum in b…and return b

screenshot_59.png

Still not done…sum = 0 + 1 = 1b becomes 1…next iteration I need 1 + 1 = 2…and then 1 + 2 = 3 and then 2 + 3 = 5…give me a second here…what about…

screenshot_60.png
This should do the trick…Let me do a quick check…for n = 3…………………no, I guess I am done…that’s it.”

Me: (Tears of joy are running down my face.)

What about recursion?

Candidate: “You said I can use recursion if I want to? (Candidate to herself: “There must be a simple recursive way to do this…otherwise they wouldn’t have asked me.”). Let’s see…”

To speed things up, I skip the part up to the actual implementation. The if-else part remains identical.

screenshot_53.png

Bonus points if the candidate mentions that recursion needs to terminate. This is guaranteed by the if-statements already.

Candidate: “I need to compute(n), which basically is compute(n – 2) + compute(n – 1). So, what about this one?”

screenshot_61.png

Now we are talking. What’s the difference between the iterative approach and the recursive one in regards to speed? What about memory consumption?

Reality check

It took all our applicants ages to implement a function based on the given input. We’ve seen a lot of implementations that did not work at all. Did some candidates realize their code is not working? No, far from.

Only one candidate went for the recursive solution and he literally had to be carried across the finish line.

Conclusion

I put this exercise up on my Facebook page to ask my developer friends for their input. Replies and coding challenges came up all night between different time zones.

Here are my favorite replies from a friend working for Google:

There is a roughly correct solution in constant time. (Hint: Binet)

I heard of a guy at work who was asked to multiply two numbers of arbitrary size (larger than primitive int). He solved it in the most optimal way in 20 minutes.

For reference, the majority of candidates take 40 minutes to add two arbitrarily large numbers with the simplification of storing each digit in a separate array element. Plus, they tend to have bugs in their final solution.

One friend mentioned that this might not be an ideal question to figure out if the candidate is a great fit for a Java Enterprise environment or not. Because that’s what we are currently looking for. What about clean code, architecture skills, team work?

I can see his point BUT

  • This is a fairly trivial exercise. On the job, complexity will rather increase. For example, one of the applications my team is building allows the user to generate an Excel report based on the stored data. User input is simplified and highly dynamic. The report needs to generate permutations of the data though. I can’t expect someone who fails to implement an iterative solution to the Fibonacci sequence to recursively permute lists and lists-of-lists of variable size.
  • It’s not a good sign when one struggles in front of a whiteboard. When was the last time the applicant discussed a topic with his co-workers?  Away from an IDE?
  • We want to hear the candidate thinking. What goes on in his mind? Can he articulate his thoughts?
  • What about stress? And failure? Does the candidate completely break down once he failed this exercise? One of them did. As part of the testing challenges he came up with a test case “1 divided by 0” with the expected result of 0.
  • How does the candidate handle criticism? What about the help we provide?

FizzBuzz is reality! The industry is still booming and I think this is something we have to live with for now. We might have to adapt our hiring process to include a phone screening up front and some coding using a shared Google Doc, as suggested by one of my friends.

And most importantly, I have to keep writing this blog, not to get completely FizzBuzzed as well someday.

Project Euler – Amicable numbers (Part 2)

I did some research and the first thing I need is a function that creates the sum of all proper divisors.

What I just noted is that the problem description lists 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 as proper divisors of 220. But not 220 as well. I have to be careful here.

screenshot_16.png

New IDE by the way. I switched from NetBeans to IntelliJ IDEA CE.

Now I can embed this in two for loops and see how long it runs.

screenshot_18.pngRuns for over 10 minutes. More research to be done.