Project Euler – Amicable numbers (Part 1)

Again something I haven’t even heard of before. What the hell are “amicable numbers”?

screenshot_05.pngI had to read the problem twice to understand what it is about. And I had absolutely no idea how to tackle this problem. But as always:

  • brute force solutions are stupid
  • let’s do some research first

Therefore I went over to Wolfram MathWorld for more information on amicable pairs.

The first thing I noticed was that amicable pairs are not that common. At least according to my definition of “common”. The given example of 220 and 284 actually is the first known pair. Below 10.000 only five pairs exist:

  • (220, 284)
  • (1184, 1210)
  • (2620, 2924)
  • (5020, 5564)
  • (6232, 6368)

Add these up and you’ve got the solution to the problem.

But how to calculate pairs of amicable numbers?

Rules for producing amicable pairs include the Thâbit ibn Kurrah rule rediscovered by Fermat and Descartes and extended by Euler to Euler’s rule. A further extension not previously noticed was discovered by Borho (1972).

(Wolfram MathWorld)

Thâbit ibn Kurrah Rule

Thâbit ibn Kurrah’s rules is a beautiful result of Thâbit ibn Kurrah dating back to the tenth century […].

(Wolfram MathWorld)

Wait…did I just read “dating back to the tenth century”? Holy…!

So how to apply this rule? I have to be pragmatic here, my math skills are enough to tackle the “how” but unfortunately not the “why”.

Let’s pick a number n equal to or greater than two. The rule presents us with three equations:

screenshot_07.pngFor n = 2: h = 11, t = 5 and s = 71. Three prime numbers.

Actually h, t and s have to be prime! Otherwise the following formula to calculate an amicable pair is not applicable.

But in case h, t and s are prime, the formula to calculate an amicable pair is:

screenshot_09.png

In case of n = 2:

screenshot_11.png

Which is the first pair (220, 284).

What about n = 3, n = 4 and so on?

For n = 3: h = 23, t = 11 and s = 287. Unfortunately 287 is not prime as it is divisible by 7. No amicable pair can be constructed for n = 3.

For n = 4: h = 47, t = 23 and s = 1151. All three are prime numbers. Therefore a pair of amicable numbers exists, which is (17296, 18416).

But now with the number 17.296 I am  already above the given limit of 10.000. So apparently just applying Thâbit ibn Kurrah’s rule is not sufficient to solve this problem.

Euler’s rule

Euler’s rule is a generalization of Thâbit ibn Kurrah’s rule. Let’s see if this one does the trick.

in case p, q and r are all prime numbers…

screenshot_12.png

…and m satisfies the following condition…

screenshot_13.png

…amicable pairs are constructed using this formula:

screenshot_14.png

Let’s check for m = 1 and n = 2: p = 5, q = 11, r = 71. All prime, which leads to the already known amicable pair of (220, 284). So far so good.

I can now increase either only n, or m and n.

m = 2, n = 3: r = 287 which is not prime. No amicable pair exists here.
m = 3, n = 4: Amicable pair exists (17296, 18416). But I am already above 10.000.
m = 1, n = 3: p = 9 which is not prime. No amicable pair.
m = 1, n = 4: q = 143 which is not prime. No amicable pair. And I am again already above 10.000.

So what to do now? Stuck.

Project Euler – Maximum path sum (Part 2)

Time to pick up a Project Euler problem that was resting on my mental shelf since the beginning of September, “Maximum Path Sum I”. For a quick introduction just jump to the old post.

screenshot_14.png

What about using a tree?

Using a tree and traversing it, most likely recursively, was my first idea.

As one can possibly guess, many possible tree implementations exist.
Here is an example taken from Stanford’s computer science department:

screenshot_13.png

Using such a construct, I started building a tree “by hand”. Something along the lines of…

root = new Node(75);
root.left = new Node(95);
root.left = new Node(64);
root.left.left = new Node(17);
...

Definitely not the way to go. Gave up. Failed.

Pen and paper approaches

I had already figured out that the number I was looking for must be somewhere between 1064 and 1313.
1064: Start at the top and always pick the highest adjacent number.
1313: Just take the highest number of each row and add them all together, even though no connection exists, just to get a very rough estimate.

Then I started browsing the interwebs for “inspiration”, which gave me some ideas, but unfortunately the solution as well.

The amount of new knowledge gained so far: ZERO! But at least I now had access to the Project Euler forum posts for this particular problem. The holy grail of algorithmic knowledge.

Apparently some forum members figured this one out using just “pen and paper”:

I just make a greedy approach with eyes, done in the second try.

Or:

I did this by eye – buffed the triangle with spaces properly and replaced everything under 50 with ’00’ in a text editor, then chose the line that looked the most line-ish 🙂 solved in about 3 minutes.

These were unfortunately not the answers to satisfy my curiosity, but I also found forum posts which looked way more algorithmic:

just paper and pencil, reduce the bottom two lines to one line containing the best sum for each element, then proceed the same with the upper level and so on. at the top you will have the answer. Same algorith will be used at the triangle with 1000 lines. (hope will work) best regards

Someone named “mather” was the first one to post an answer along these lines.

Let’s have a look at his approach using the sample triangle given in the original problem description:

screenshot_16.png

The algorithm starts at the bottom line, not on the top. I stick to the tree language by the way. Each leaf has a parent node. For example 2 is the parent node of leaf 8 and 5. 4 is the parent node of leaf 5 and 9 and so on.

Now, for each node (leaf) we create a the sum of its value and the value of its parent. The higher sum will be kept. We just store it as new value in the parent node.

screenshot_18.png

8 + 2 = 10.
5 + 2 = 7.
10 > 7, keep 10.

screenshot_19.png

Now 5 + 4 = 9.
9 + 4 = 13.
13 > 9, keep 13.

And last 9 + 6 = 15.
3 + 6 = 9.
15 > 9, keep 15.

That’s how to proceed upwards.

screenshot_20.png

The final result is 23, which is exactly the number we are looking for.

And this is an algorithm that can be turned into  a program! Almost there.

Finally a program

Credit goes to a user named “dchuhay”.

This little program follows exactly the approach described above.

screenshot_21.png

The program flow starts in this row of the pyramid:

screenshot_24.png

For each node value in this row the algorithm builds two sums, one for each of the two child-nodes, and stores the higher sum in the original node.

E.g. i = 13, j =0. The node triangle[13][0] is 63.
Now, is triangle[13 + 1][0] < triangle[13 + 1][0 + 1]? 04 < 62? Yes!
Therefore add triangle[13 + 1][0 + 1] to triangle[13][0] and store it as new value in triangle[13][0]. 63 + 62 = 125.

Now proceed with the next node in this row, which is 66, until we run out of values.
Once all values in this row were replaced by new values (= highest sum) proceed on, one row upwards.

screenshot_25.png

for (int i = triangle.length – 2; i >= 0; i–) is correct, as we need to assign a value to triangle[0][0], which will be our final result.

Dynamic programning

One forum post containing a C# solution starts with the following line:

Classical dynamic programming task.

I had to look this up. According to Wikipedia:

In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called “memoization”.

Does this apply to the problem at hand?

Is it a complex problem? For sure. Can it be broken down into a collection of simpler subproblems? Hmmm, what would be a simpler subproblem? Exactly what is done above. For each combination of a node and its two sub-nodes find the higher sum. Keep the result. Wash, rinse, repeat until the root node is reached.

I am glad I did some research on this Project Euler problem. Lots of new knowledge gained.

Ten in the bed

It’s been a while. And yes, I still have to write that follow-up post on the Project Euler problem “Maximum path sum”. I just didn’t work on it anymore. M.u.s.t.n.o.t.g.i.v.e.u.p!

Today’s short post will be on a much lighter note, namely a childrens’s song.

My little boy, two and half years old, loves to watch clips on YouTube. Almost every evening we move over to my little man cave and browse for car cartoons. Fire engine, ambulance, police car….all the stuff that he currently enjoys a lot.

We also watch a lot of children’s songs. “Wheels on the bus” anyone?

Yesterday I was struck by a little song called “Ten in the bed”.

There were 10 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 9 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 8 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

[…]

There were 2 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 1 in the bed
And the little one said
Good night!

I’ve heard this song so many times without realizing that those lyrics are actually all about recursion.

So once my little one went to bed, I fired up my IDE and checked if I know at least a little bit about recursion, enough to hack the song in a couple of minutes.

Et voilà….

screenshot_11.png

This is a very simple problem though.

A little while ago my boy and I started playing a boxed game. A car, a plane, a train and a ship travel through Europe on a map. We don’t follow any rules, just move the pieces along the roads, that connect Europe’s largest capitals.

Like the children’s song this sparked my interest. “How many different routes do exist?” “Can we visit all cities and use each road only once?”

I also remember to have a similar Sam Loyd puzzle somewhere in my bookshelf.

I might turn this into a blog post as well. But first a lot of reading has to be done and also the open Project Euler problem has to be ticked of my list.

Project Euler – Maximum path sum (Part 1)

This is what I am currently working on:

Maximum_path_sum_problem_description.png

I don’t have the solution yet, so this blog post will contain some thoughts that hopefully will at least lead me in the right direction.

Always pick the highest number?

My first idea was to always pick the highest adjacent number. This is what’s done in the given example: 3 + 7 + 4 + 9.

example

 

This would lead to 75 + 95 + 47 + 87 + 82 + 75 + 73 + 28 + 83 + 47 + 43 + 73 + 91 + 67 + 98 = 1064. Unfortunately this is not the correct solution.

Therefore going for the highest number is not the correct strategy.

Is it a tree?

This looks like a tree. But I have to be careful.

tree_1.png

This is not the kind of tree I am looking for, as I could never reach from node “4” to the adjacent node with the same value:

tree_2.png

What I need is a tree that looks like the following:

tree_3.png

So how to do I create such a structure programmatically?

The problem shows a root node plus 14 additional node levels. This might result in heavy typing which I want to avoid.

Work from top or bottom?

Once I have a tree, how do I process it? Looks like a call for recursion? Top-down? Bottom-up?

Sanity check

I know that 1064 is not the correct solution. Therefore the solution must be a larger number. Also it cannot be more than 1313. Most likely the solution is closer to 1064.

 

Find the max value

Another open university assignment. Again Pascal.

Write a program max that reads integer values from standard input and returns the max value.
0 terminates the input.

This is my solution:

screenshot_93.png

And this is the university’s solution:

screenshot_92.png

So what’s the difference?

A bit nicer structure. But basically the same program.

screenshot_95.png

Why do we need an additional readln (Number)?

screenshot_96.png

This is an optimization. E.g. in case I enter the number 8 first and then the number 0, the while-loop will not be executed. Otherwise (without readln (Number)) we enter the while-loop, perform an unnecessary check (if Number > MaxNumber; if 8 > 8), then read the 0 and exit the while-loop. My solution actually performs this unnecessary step as well.

Understood.

Pascal

I am learning Pascal. Pascal? Pascal in 2016? Yes, Pascal!

I enrolled in an Open University course on imperative programming and unfortunately the university’s language of choice is Pascal. Currently I’m really struggling with the language’s syntax. All those begins and ends, semicolons, no semicolons…

But I’m in no position to judge a programming language. And let’s not forget, Pascal was used by Donald E. Knuth to create Tex!!

So I either give up or I better get my sh… together.

The first exercise is a simple merge program. Two already sorted lists have to be merged into a single result list.

List1 = [11, 14, 18, 80, 100]
List2 = [8, 11, 11, 17, 22, 30, 55, 70]
ResultList = [8, 11, 11, 11, 14, 17, 18, 22, 30, 55, 70, 80, 100]

It’s not allowed to…

  • …copy both lists to the result list and then sort its elements.
  • …copy one list to the result list and then insert the elements of the second list in the correct order.

This is the given program frame without implementation of the merge algorithm:

screenshot_84.png

And this is a possible implementation of the merge algorithm:

screenshot_85.png

We start by comparing the first value of the first list with the first value of the second list.
Either the value of Field1[1] is less than the value of Field2[1], equal to the value of Field2[1] or greater than the value of Field2[1].

List1[1] < List2[1] → Copy the value of List1[1] to the result list at first position (ResultList[1] := List1[1]).
Increase the counter i for List1 and k for ResultList.

List1[1] >= List2[1] → Copy the value of List2[1] to the result list at first position (ResultList[1] := List2[1]).
Increase the counter j for List2 and k for ResultList.

Wash, rinse, repeat until one of the two lists (List1List2) runs out of elements:
while (i <= LISTLENGTH1) and (j <= LISTLENGTH2) do

That’s how we start:

screenshot_86.png

First step:

screenshot_87.png

Second step:

screenshot_88.png

And so on.

This is how the while loop ends. List2 runs out of elements first:

screenshot_89.png

We are out of the while loop, but do not know which one of our two lists still holds some elements. This is done by if i > LISTLENGTH1 then.
4 > 5? No, so it must be List2.

We iterate over the remaining elements in List2 and add each element to our result list. Let’s not forget to increase the counter for j and k each time we copy an element.

Et voilà. Done.

Project Euler – Largest product in a grid

Another Project Euler problem. This time about adjacent numbers in a grid.

screenshot_35.png

Failed attempt…too complicated

The 20 x 20 grid did look intimidating at first. Therefore I started experimenting with a smaller 5 x 5 grid and three three adjacent numbers.screenshot_36.png

My idea was to iterate over the grid and create horizontal…

screenshot_37.png

…vertical…

screenshot_38.png…and diagonal groups…

screenshot_39.png

…calculate the product for each group to find the largest one.

That’s what my first attempt to find the largest product in a row looked like.

screenshot_54.png

I quickly came up with algorithms to create horizontal and vertical groups but struggled with the diagonal ones.

Also I realized that diagonal does not necessarily mean top left to bottom right only. Diagonal can actually go in four directions.

That’s when I scrapped my first attempt, and started looking for another solution.

Simple but…

screenshot_56.png

Again I iterate over the grid. For each number I can go in eight different directions…

  • (1) Up: Column number fix, row number – 1
  • (2) Diagonal right up: Column number + 1, row number – 1
  • (3) Right: Row number fix, column number + 1
  • (4) Diagonal right down: Column number + 1, row number + 1
  • (5) Down: Column number fix, row number + 1
  • (6) Diagonal left down: Column number – 1, row number + 1
  • (7) Left: Row number fix, column number  – 1
  • (8): Diagonal up left: Row number – 1, column number  – 1

I only had to be careful not to leave the boundaries of the 20 x 20 grid.

screenshot_57.png

That’s my solution:

screenshot_74.png

screenshot_75.png

screenshot_76.png