In Problem 42 we dealt with triangular problems, in Problem 44 of Project Euler we deal with pentagonal number, I can only wonder if we have to deal with septagonal numbers in Problem 46. Anyway the problem reads

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 is pentagonal and D = |Pk – Pj| is minimised; what is the value of D?

I have found a solution which I will present to you in just a few lines, but I must admit that I haven’t been able to justify why it is the right solution it gives us. The solution I have made just finds a solution to the problem which happens to the right solution.

I did not want to generate a list of pentagonal numbers, so I wanted to make a small function which checks if a given number is pentagonal by checking if the inverse function yields an integer, just like in the solution to  Problem 42. We could rather easily calculate the inverse function as we did with the inverse function for triangular numbers, or we can cheat and peak at the pentagonal number entry at Wikipedia.

The inverse function is

That enables us to make a C# function that checks if a number is pentagonal

1
2
3
4
private bool isPentagonal(int number) {
    double penTest = (Math.Sqrt(1 + 24 * number) + 1.0) / 6.0;
    return penTest == ((int)penTest);
}

Once we have this crucial function we can make two nested loops to check pentagonal numbers until we find two where the sum and difference are pentagonal as well. I am frustrated since I can’t figure out why this one is the first. I can prove that it is indeed minimal by testing other numbers until the difference of two numbers reach the result of this problem. However I haven’t done that.

The outer loop of the algorithm counts upwards generating and the inner loop counting downwards testing all pentagonal numbers less than the one generated by the outer loop. The code looks like

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int result = 0;
bool notFound = true;
int i = 1;
 
while (notFound) {
    i++;
    int n = i * (3 * i - 1) / 2;
 
    for (int j = i-1; j > 0; j--) {
        int m = j * (3 * j - 1) / 2;
        if (isPentagonal(n - m) && isPentagonal(n + m)) {
            result = n-m;
            notFound = false;
            break;
        }
    }
}

and gives the result

1
2
3
k = 2167, j = 1020
The value of D is 5482660
Solution took 35 ms

Wrapping up

I can see that many other people also can’t give the definitive answer to why the result is correct. If you understand the problem better than I do, please let me know exactly why I find the right solution.

You can as usual find the source code for the problem here.

ref

最新文章

  1. C#先序遍历2叉树（非递归）
  2. Java设计模式5：原型模式
  3. github-ssh
  4. 20145308刘昊阳 《Java程序设计》实验五报告
  5. postgresql之ctid的浅谈
  6. spring aop 使用xml方式的简单总结
  7. linux中文乱码问题及locale详解
  8. PDCA循环原理
  9. TurnipBit开发板“趣味赛”：平衡力大比拼
  10. C#删除WebBrowser控件的Session
  11. CentOS7各个版本镜像下载地址
  12. 第二次Srum冲刺
  13. MySQL主从数据同步延时分析
  14. git初始化本地项目及关联github远程库
  15. 深入迁出mybatis系列
  16. iOS NSNotificationCenter 最基本使用
  17. talend 连接mysql数据库没有权限
  18. 连接mysql-front数据库出现‘执行错误1251’的解决办法（有效）
  19. [原][osgearth]osgearthviewer读取earth文件，代码解析（earth文件读取的一帧）
  20. centos编译安装php7

热门文章

  1. redis 数据类型 Hash
  2. git 学习之基本概念
  3. 使用ehCache作为本地缓存
  4. c++类型形参的实参的受限转换
  5. [PY3]——内置数据结构(9)——线性结构与切片/命名切片slice()
  6. 常用命令（Linux、Android、adb）
  7. Python——第一个python程序helloworld
  8. 如何让code变得更易读
  9. ASP.NET之HTML
  10. freemarker学习笔记