guangzhou



shanghai

Recent posts:
Blog index
About
RSS

Project Euler 45–Triangular, pentagonal, and hexagonal

August 20, 2018     欧拉计划   688   

Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.


三角形数、五边形数和六角形数

三角形数、五边形数和六角形数分别由以下公式给出:

三角形数 Tn=n(n+1)/2 1, 3, 6, 10, 15, …
五边形数 Pn=n(3n−1)/2 1, 5, 12, 22, 35, …
六边形数 Hn=n(2n−1) 1, 6, 15, 28, 45, …

可以验证,T285 = P165 = H143 = 40755。

找出下一个同时是三角形数、五边形数和六角形数的数。

思路(暴力解法):

由三角形数、五边形数和六角形数的公式,因为是二次式,可以利用判别式直接判断

若m是三角形数,则

\(\frac{n(n+1)}{2}=m\)

\(n=\frac{-1+\sqrt{1+8m}}{2}\)

若m是五边形数,则

\(\frac{n(3n-1)}{2}=m\)

\(n=\frac{1+\sqrt{1+24m}}{6}\)

若m是六角形数,则

\(n(2n-1)=m\)

\(n=\frac{1+\sqrt{1+8m}}{4}\)

综上所述,对于一个自然数m,首先判断相应的判别式即可,代码如下:

// Project Euler 45–Triangular, pentagonal, and hexagonal
// Completed on Mon, 20 Aug 2018, 23:12
// Language: C
//
// 版权所有(C)wu yudong
// 博客地址:http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

int main()
{
	long long ans;
	int begintime, endtime;
	int n = 143;
	begintime = clock();		//计时开始
	while (1) {
		n++;
		//Hexagonal
		double h = n * (2 * n - 1);
		double Triangle = (sqrt(1 + 8 * h) - 1) / 2;
		double Pentagonal = (sqrt(1 + 24 * h) + 1) / 6;
		double T = (int)Triangle;
		double P = (int)Pentagonal;

		if (T == Triangle && P == Pentagonal) {
			ans = n * (2 * n - 1);
			printf("%lld\n", ans);
			break;
		}
	}
	endtime = clock();			//计时结束

	printf("Running Time: %dms\n", endtime - begintime);
	return 0;
}

运行结果:

1533776805
Running Time: 1ms

Answer:1533776805
Completed on Mon, 20 Aug 2018, 23:12

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)