Part Two - Pentagonal Numbers
Nested C++ Recursion - Introduction (Main Article Page)
Part One - Recursion Basics presented a basic description of the recursion idea. Part Two here will explore the problem we'll solve with nested recursion.
Awhile back, I took an Udemy Golang class taught by Prof. McLeod. Early on, he suggested that the students pick a problem at Project Euler, and solve it with Golang. I saw Problem 44, the Pentagonal Numbers problem. It states
and it did not look like an overwhelming challenge. Nested loop software would solve the problem.
This diagram shows the overall solution behavior:
The outer while loop controls “i,” the n‑value line on the right. The inner for-loop controls “j,” the n‑value line on the left. Both values map to pentagonal numbers through this equation:
When the program starts, the left-hand n value starts at 1, and the right-hand n value starts at 2. The outer while loop moves the right-hand n value to the right by 1. The inner loop moves the left-hand n value to 1 less than the larger value. Starting with these two n values, the software finds their Pentagonal numbers – the vertical axis. The inner loop tests whether or not the sum and difference of these numbers themselves are Pentagonal numbers. If true for both the sum and difference, the software found the solution pair. If false for at least one calculation, the inner for loop moves the left‑hand n value down by 1, and tests the new sum and difference. If necessary, the inner loop ends at 1. The software proceeds this way until it finds the solution pair.
To start, a nested loop C++ solution for Project Euler #44 might look like this:
#include "stdafx.h"
#include <chrono>
#include <ctime>
#include <iostream>
#include <math.h>
#include <set>
bool is_pentnum(int x) {
// Test if parameter "x" is a pentagonal number.
// http://www.divye.in/2012/07/how-do-you-determine-if-number-n-is.html
float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
return (((testval - trunc(testval)) == 0.0) ? true : false);
};
int main() {
int i = 2, j;
int ptNum1 = 0, ptNum2 = 0, ptNumSum = 0, ptNumDiff = 0;
bool first = true;
bool notFound = true;
auto startTime = std::chrono::high_resolution_clock::now();
while (notFound) {
i++;
ptNum1 = i * ((3 * i) - 1) / 2;
for (j = (i - 1); j > 0; j--) {
ptNum2 = j * ((3 * j) - 1) / 2;
if (is_pentnum(ptNum1 - ptNum2) && is_pentnum(ptNum1 + ptNum2)) {
ptNumSum = ptNum1 + ptNum2;
ptNumDiff = ptNum1 - ptNum2;
notFound = false;
break;
}
}
}
std::cout << std::boolalpha;
// For std::cout, format the boolean values as "true" or "false":
auto endTime = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> timeDifference = endTime - startTime;
std::cout << "\n\tLoop solution for Euler Project #44: pentagonal numbers: ";
std::cout << "\n\n";
std::cout << "\ti = " << i << " --> pentNum(i) = pentNum(" << i << ") = ";
std::cout << ptNum1 << "\n";
std::cout << "\tj = " << j << " --> pentNum(j) = pentNum(" << j << ") = ";
std::cout << ptNum2 << "\n\n";
std::cout << "\t\t\t\t pentNumSum =\n";
std::cout << "\t\t pentNum(" << i << ") + pentNum(" << j << ") =\n";
std::cout << "\t\t\t " << ptNum1 << " + " << ptNum2 << " = ";
std::cout << (ptNum1 + ptNum2) << "\n\n";
std::cout << "\t\t" << (ptNum1 + ptNum2) << " is a pentagonal number: ";
std::cout << is_pentnum(ptNum1 + ptNum2) << "\n\n";
std::cout << "\t______________________________________________\n";
std::cout << "\t______________________________________________\n\n\n";
std::cout << "\t\t\t\t pentNumDiff =\n";
std::cout << "\t\t pentNum(" << i << ") - pentNum(" << j << ") =\n";
std::cout << "\t\t\t " << ptNum1 << " - " << ptNum2 << " = ";
std::cout << (ptNum1 - ptNum2) << "\n\n";
std::cout << "\t\t" << (ptNum1 - ptNum2) << " is a pentagonal number: ";
std::cout << is_pentnum(ptNum1 - ptNum2) << "\n\n";
std::cout << "\n\tCalculation Time = " << timeDifference.count();
std::cout << " seconds\n\n";
}
I did not build a loop solution first. Instead, I started thinking that maybe I could build a strictly recursive solution.
In theory, a recursive function can substitute for a conditional loop. A loop has at least one condition that defines its ending state. This works like a recursive function base case. A loop also has a way to move itself towards its ending state, in a finite number of iterations, or steps. This works like a recursive software call. All software, especially recursive software, directly and / or indirectly needs the stack for its operations. However, compared to loop-based solutions, recursive software stack limitations become much more important issues. I vaguely knew that even if I built a recursive solution with correct engineering, it could overflow the stack. However, I tried and succeeded. My solution levered anonymous functions, and this made the technique highly flexible. See the Golang solution I built here, and read a BitVectors article I wrote about it here. I discovered that Euler Project, Problem 44 became ideal for research about recursion engineering and nested recursion. We can build recursive solutions for it, and because of its simplicity, it won’t overshadow the solution engineering. I then built what became a group of nested recursion engineering C++ solutions to Problem 44.
Here, we learned about Euler 44 Pentagonal Numbers - the problem we'll solve with nested C++ recursion. In Part Three - Euler 44 Solution Groundwork, we’ll examine the engineering of those solutions.
Part One - Recursion Basics presented a basic description of the recursion idea. Part Two here will explore the problem we'll solve with nested recursion.
Awhile back, I took an Udemy Golang class taught by Prof. McLeod. Early on, he suggested that the students pick a problem at Project Euler, and solve it with Golang. I saw Problem 44, the Pentagonal Numbers problem. It states
Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?
and it did not look like an overwhelming challenge. Nested loop software would solve the problem.
This diagram shows the overall solution behavior:
The outer while loop controls “i,” the n‑value line on the right. The inner for-loop controls “j,” the n‑value line on the left. Both values map to pentagonal numbers through this equation:
pn = (3n2 – n) / 2
When the program starts, the left-hand n value starts at 1, and the right-hand n value starts at 2. The outer while loop moves the right-hand n value to the right by 1. The inner loop moves the left-hand n value to 1 less than the larger value. Starting with these two n values, the software finds their Pentagonal numbers – the vertical axis. The inner loop tests whether or not the sum and difference of these numbers themselves are Pentagonal numbers. If true for both the sum and difference, the software found the solution pair. If false for at least one calculation, the inner for loop moves the left‑hand n value down by 1, and tests the new sum and difference. If necessary, the inner loop ends at 1. The software proceeds this way until it finds the solution pair.
To start, a nested loop C++ solution for Project Euler #44 might look like this:
#include "stdafx.h"
#include <chrono>
#include <ctime>
#include <iostream>
#include <math.h>
#include <set>
bool is_pentnum(int x) {
// Test if parameter "x" is a pentagonal number.
// http://www.divye.in/2012/07/how-do-you-determine-if-number-n-is.html
float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
return (((testval - trunc(testval)) == 0.0) ? true : false);
};
int main() {
int i = 2, j;
int ptNum1 = 0, ptNum2 = 0, ptNumSum = 0, ptNumDiff = 0;
bool first = true;
bool notFound = true;
auto startTime = std::chrono::high_resolution_clock::now();
while (notFound) {
i++;
ptNum1 = i * ((3 * i) - 1) / 2;
for (j = (i - 1); j > 0; j--) {
ptNum2 = j * ((3 * j) - 1) / 2;
if (is_pentnum(ptNum1 - ptNum2) && is_pentnum(ptNum1 + ptNum2)) {
ptNumSum = ptNum1 + ptNum2;
ptNumDiff = ptNum1 - ptNum2;
notFound = false;
break;
}
}
}
std::cout << std::boolalpha;
// For std::cout, format the boolean values as "true" or "false":
auto endTime = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> timeDifference = endTime - startTime;
std::cout << "\n\tLoop solution for Euler Project #44: pentagonal numbers: ";
std::cout << "\n\n";
std::cout << "\ti = " << i << " --> pentNum(i) = pentNum(" << i << ") = ";
std::cout << ptNum1 << "\n";
std::cout << "\tj = " << j << " --> pentNum(j) = pentNum(" << j << ") = ";
std::cout << ptNum2 << "\n\n";
std::cout << "\t\t\t\t pentNumSum =\n";
std::cout << "\t\t pentNum(" << i << ") + pentNum(" << j << ") =\n";
std::cout << "\t\t\t " << ptNum1 << " + " << ptNum2 << " = ";
std::cout << (ptNum1 + ptNum2) << "\n\n";
std::cout << "\t\t" << (ptNum1 + ptNum2) << " is a pentagonal number: ";
std::cout << is_pentnum(ptNum1 + ptNum2) << "\n\n";
std::cout << "\t______________________________________________\n";
std::cout << "\t______________________________________________\n\n\n";
std::cout << "\t\t\t\t pentNumDiff =\n";
std::cout << "\t\t pentNum(" << i << ") - pentNum(" << j << ") =\n";
std::cout << "\t\t\t " << ptNum1 << " - " << ptNum2 << " = ";
std::cout << (ptNum1 - ptNum2) << "\n\n";
std::cout << "\t\t" << (ptNum1 - ptNum2) << " is a pentagonal number: ";
std::cout << is_pentnum(ptNum1 - ptNum2) << "\n\n";
std::cout << "\n\tCalculation Time = " << timeDifference.count();
std::cout << " seconds\n\n";
}
I did not build a loop solution first. Instead, I started thinking that maybe I could build a strictly recursive solution.
In theory, a recursive function can substitute for a conditional loop. A loop has at least one condition that defines its ending state. This works like a recursive function base case. A loop also has a way to move itself towards its ending state, in a finite number of iterations, or steps. This works like a recursive software call. All software, especially recursive software, directly and / or indirectly needs the stack for its operations. However, compared to loop-based solutions, recursive software stack limitations become much more important issues. I vaguely knew that even if I built a recursive solution with correct engineering, it could overflow the stack. However, I tried and succeeded. My solution levered anonymous functions, and this made the technique highly flexible. See the Golang solution I built here, and read a BitVectors article I wrote about it here. I discovered that Euler Project, Problem 44 became ideal for research about recursion engineering and nested recursion. We can build recursive solutions for it, and because of its simplicity, it won’t overshadow the solution engineering. I then built what became a group of nested recursion engineering C++ solutions to Problem 44.
Here, we learned about Euler 44 Pentagonal Numbers - the problem we'll solve with nested C++ recursion. In Part Three - Euler 44 Solution Groundwork, we’ll examine the engineering of those solutions.