ProjectEuler Problem 45: Triangular, pentagonal, and hexagonal

Apr 7, 2014

Coding

Problem 45: Triangular, pentagonal, and hexagonal #

https://projecteuler.net/problem=45

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.

分析 #

一个数既是三角形数，又是五边形数，同时又是六边形数。

思路：利用求根公式。

三角形数： y = n(n+1)/2，则 n = [sqrt(8y+1) – 1] / 2
五边形数： y = n(3n-1)/2，则 n =[sqrt(24y+1) + 1] / 6
六边形数： y = n(2n-1)，则 n= [sqrt(8y+1) + 1] / 4

由于Tn、Pn、Hn中Hn 变化最快。所以从n=143 +1 开始，求出对应的y = Hn。然后将y带入其它两个公式的求根，如果根是整数，则表明y也是对应的类型的数（三角形数或五边形数）

方法遍历六边形数，判断其是不是三角形和五边形数 #

C++ #

#include <stdio.h>
#include <math.h>

int main()
{
    for(int i = 143 + 1; ; i++){

        double h = i * (2 * i - 1); // hexagonal numbers
        double rootT = (sqrt(1 + 8 * h) - 1) / 2;
        double rootP = (sqrt(1 + 24 * h) + 1) / 6;

        double t = (int)rootT;
        double p = (int)rootP;
        if( t == rootT && p == rootP){
            printf("%.0f\n", h);
            break;
        }
    }
    return 0;
}

Golang #

package main

import (
	"fmt"
	"math"
)

func main() {

	for i := 143 + 1; ; i++ {
		h := float64(i * (2*i - 1)) // hexagonal numbers
		rootT := (math.Sqrt(1+8*h) - 1) / 2
		rootP := (math.Sqrt(1+24*h) + 1) / 6

		if rootT == float64(int64(rootT)) && rootP == float64(int64(rootP)) {
			fmt.Println(int64(h))
			break
		}
	}
}

Python #

from math import sqrt

i = 143 + 1
while True:
    h = i * (2 * i - 1); # hexagonal numbers
    rootT = (sqrt(1 + 8 * h) - 1) / 2
    rootP = (sqrt(1 + 24 * h) + 1) / 6

    if rootT == float(int(rootT)) and rootP == float(int(rootP)):
        print(h)
        break
    i = i + 1

答案 #

1533776805