Project Euler #44: a recursive Golang solution - Part One


few weeks ago, I started the Udemy Go (Golang) class taught by Professor McLeod. He knows his stuff and at roughly a quarter of the way through, he suggested that we pick a problem at Project Euler and build a Golang solution for it. I randomly chose Project Euler #44 - Pentagonal Numbers. A nested for-loop approach, in Go or any other language, would probably work. Then I got a bright idea: maybe I could build a strictly recursive Golang solution instead. Obviously, we should not rely on recursion as a first choice to solve problems. It has a large resource overhead and expense. A recursive solution can become tricky to build, and it can easily blow the stack. However, I wanted to push both myself and the Golang product. I built the solution with Go 1.7.4 and Webstorm 2016.3 on a Windows 7 PC. See the solution here at GitHub.

For Project Euler #44, we have to find two pentagonal numbers that together, obey three rules:

        The sum of the numbers must form a pentagonal number

        The subtracted value (larger number - smaller number) must
        form a pentagonal number

        The absolute value of the subtracted numbers must be

The first two rules made perfect sense but I wondered about the third rule. Maybe a later pair of larger numbers might have a smaller distance between them. Then I looked at the pentagonal number

p_n = \tfrac{3n^2-n}{2}

equation. If we start the search from this number pair

        P1 = 1

        P2 = 5

as known pentagonal numbers, I decided that since the equation has a monotonic increasing derivative

p_n = \tfrac{3n^2-n}{2}

for n > 0, the first number pair

        (P0, P1)

that satisfies all the rules would solve the problem.

Based on the P
n equation above, the integers "n" map to pentagonal numbers like so:

        n pentagonal number (P

        1          1
        2          5
        3        12
        4        22
        5        35
        6        51
        7        70
        8        92
        9      117
       10     145
        .          .
        .          .
        .          .

To solve the problem, we can start with a pair of integers

        (P0, P1)

as shown in the table. Pseudo-code for search would look like this:

        (outer loop)

              increment P1 by one
              set Pto (P1 - 1)

              (inner nested loop)

                    with P1 fixed, decrement Pby one until we hit P0 = 1
                    at each decrement of P0, test the (P0, P1) pair against
                          the rules

Inside the inner loop, each time P0 decrements, map the (P0, P1) pair into pentagonal numbers. IP0  hits 1 and the (P0, P1) pair did not satisfy the listed conditions, then leave the inner loop, run the outer loop once

        increment P1 by one
        set P0  to (P1 - 1)

and proceed. When the integer pair satisfies the conditions

        P1 is a pentagonal number
        P0 is a pentagonal number
        (P1 + P0) is a pentagonal number
        (P1 - P0) is a pentagonal number

we solved the problem. The Project Euler folks probably expected a nested loop solution. I had other ideas as we'll see in Part Two.