# Pentagonal Numbers

**C++.** This is the Problem 44 from Project Euler.

**Question:** Pentagonal numbers are generated by the formula, P_{n}=`n`(3`n`−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P_{4} + P_{7} = 22 + 70 = 92 = P_{8}. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_{j} and P_{k}, for which their sum and difference are pentagonal and D = |P_{k} − P_{j}| is minimised; what is the value of D? Link to the page.

**Solution: **My approach is to increment the sum value in order to create a pentagonal numbers domain so that we can track those two numbers. I call them P1 and P2 for easy track where P2 > P1. While sum (P2+P1) increases by n going to infinity, the algorithm paces P1 from the start of the domain to the edge of the first half of the domain since P1 is always less than P2. Thus, P2 becomes observable by sum – P1. Then, the algorithm checks if P2 is pentagonal or not by quadratic equation formula. If yes, it checks the difference between P2 and P1 next. If the difference is pentagonal as well, it becomes the first hit and the minimised difference. Its running time is less than a second.

Answer is 5482660 where P1 = 1560090 and P2 = 7042750.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <vector> #include <cmath> class Pentagonal { public: Pentagonal() : n(1), p1(1), p2(1), sum(0), diff(0) {} ~Pentagonal() {} int searchPentagonalPair() { pentagonal.push_back(1); // creating an infinite loop until it hits the value while(true) { n++; sum = n * (3*n - 1) / 2; pentagonal.push_back(sum); //boundry is half of the domain where p2 > p1 //search will be made inside the boundry int boundry = (int)ceil(pentagonal.size() / 2); for(int i = 0; i < boundry; ++i) { p2 = sum - pentagonal[i]; //where p1 = pentagonal[i] //checking if p2 and the difference are pentagonal or not //x and y are other positive roots of quadratic equation //if x and y are integers, so are p2 and the difference //if x is not pentagonal, no need to check the difference float x = (1 + sqrt(1 + 24 * p2)) / 6; if(x == floor(x)) { diff = p2 - pentagonal[i]; float y = (1 + sqrt(1 + 24 * diff)) / 6; if(y == floor(y)) { p1 = pentagonal[i]; std::cout << "The pentagonal numbers are " << p1 << " and " << p2 << std::endl; std::cout << "Their difference is " << diff << std::endl; return 0; } } } } } private: // n is an integer creating a pentagonal number while going to infinity int n, p1, p2, sum, diff; std::vector<int> pentagonal; }; int main() { Pentagonal p_obj; p_obj.searchPentagonalPair(); return 0; } |