欧拉工程第45题：Triangular, pentagonal, and hexagonal_综合

getit
题目链接：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.

找出这数之后的下一个既是五角数又是六角数的三角数。

也就是求下一个： $T(i)=P(j)=H(k)$

直觉上应该是找i,j,k三个的关系式，尝试了，发现很不好找

其实可以这样玩的：
1.先求出一个三角数或者五角数或者六角数
2.在分别判断这个数在不在另外两个数序列中

Java写的跑的很快10ms
在答题论坛中发现欧拉工程45 ，三角数和六角数在相等的时候满足t=2n-1，可以减少一个判断，这个数可能有多个，在程序中去除判断是六角数的时候果然出来问题，输出的第二个数是答案。
上面的不对，是忽略三角数，所有先求一个六角数，再只需判断是五角数就可。
Java 程序：

package projecteuler41to50;import java.util.Date;
import java.util.Set;
import java.util.TreeSet;class level45{
    void solve0(){Long Max_Value=1000000l;for(long i=286;i<Max_Value;++i){long TriNum=getTriangle(i);if(isHexagonal(TriNum) && isPentagonal(TriNum)){System.out.println(TriNum);break;}}}void solve1(){Long Max_Value=1000000l;for(long i=166;i<Max_Value;++i){long TriNum=getPentagonal(i);if( isHexagonal(TriNum)){System.out.println(TriNum);break;}}}void solve2(){Long Max_Value=1000000l;for(long i=144;i<Max_Value;++i){long TriNum=getHexagonal(i);if( isPentagonal(TriNum)){System.out.println(TriNum);break;}}}void solve3(){Long Max_Value=1000000l;for(long i=286;i<Max_Value;++i){long TriNum=getTriangle(i);if( isPentagonal(TriNum)){System.out.println(TriNum);
// break;}}}long getTriangle(long index){return index*(index+1)/2;}long getPentagonal(long index){return index*(3*index-1)/2;}long getHexagonal(long index){return index*(2*index-1);}boolean isTriangle(long num){long delt=1+8*num;if(isSquare(delt)){long member=(long) (-1+Math.sqrt(delt));if(member%2==0 && member/2>0)return true;}return false;}boolean isHexagonal(long num){long delt=1+8*num;if(isSquare(delt)){long member=(long) (1+Math.sqrt(delt));if(member%4==0 && member/4>0)return true;}return false;}boolean isPentagonal(long num){long delt=1+24*num;if(isSquare(delt)){long member=(long) (1+Math.sqrt(delt));if(member%6==0 && member/6>0)return true;}return false;}boolean isSquare(long num){long n=(long) Math.sqrt(num);if(n*n==num)return true;return false;}}
public class Problem45 {
    public static void main(String[] args){Date beginTime=new Date();new level45().solve1();Date endTime=new Date();Long Time=endTime.getTime()-beginTime.getTime();System.out.println("Time="+Time/1000+"秒"+Time%1000+"毫秒");}
}

结果：

1533776805 Time=0秒13毫秒

solve0：求三角数+判断五角数+判断六角数
solve1：求五角数+判断六角数
solve2：求六角数+判断五角数
solve3：求三角数+判断五角数
测试了上面几种，只有solve3，有错误，输出所有结果的第二个是答案
仿照Java写的Python代码：

def getPentagonal(index):return index*(3*index-1)/2def isPentagonal(num):index=(math.sqrt(24*num+1)+1)/6if index==int(index):return Truereturn Falsedef isTriangle(num):index=(math.sqrt(8*num+1)-1)/2if index==int(index):return Truereturn Falsedef isHexagonal(num):index=(math.sqrt(8*num+1)+1)/4if index==int(index):return Truereturn Falsefrom time import time
import matht1=time()
for i in range(286,100000):pet=getPentagonal(i)if isTriangle(pet) and isHexagonal(pet):print str(pet)quit()
t2=time()print t2-t1

当然上面代码写的很搓。

在解答论坛中看到下面的代码：

nLimit = 250000
xnTriangles = [n*(n+1)/2 for n in range(nLimit)]
xnPentagons = [n*(3*n-1)/2 for n in range(nLimit)]
xnHexagons = [n*(2*n-1) for n in range(nLimit)]
xnMatches = list(set(xnTriangles) & set(xnPentagons) & set(xnHexagons))
sorted(xnMatches)
print("Answer: ", int(xnMatches[xnMatches.index(40755) + 1]))

写的简单的，跑的也很快的，定义三个集合，再求三个集合的交集

看到一个R代码，如下：
欧拉工程45
运行结果：

这里只是判断了五角数和六角数相等的，但是用R写也是醉了。。。

增加判断三角数：

p <- function(n) n * (3 * n - 1) / 2
h <- function(n) n * (2 * n - 1)
t <- function(n) n * ( n + 1)/2ta <- c(p(1:100000), h(1:100000),t(1:100000))
t <- table(ta)
t[t == 3]

结果一样：

r1      40755 1533776805 3          3          3