### 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
minimized

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

equation. If we start the search from this number pair

P1 = 1
and

P2 = 5

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

$\huge dp / dn = 3n - 1/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
n)
____________________________

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.