题目45：在40755之后最小的既是五角数又是六角数的三角数是多少？

欧拉计划

Triangular, pentagonal, and hexagonal

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

Triangle                               1, 3, 6, 10, 15, ...
Pentagonal                         1, 5, 12, 22, 35, ...
Hexagonal                             1, 6, 15, 28, 45, ...

It can be verified that .

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

题目：

三角数，五角数和六角数分别通过以下公式定义：

三角数                                1, 3, 6, 10, 15, ...
五角数                               1, 5, 12, 22, 35, ...
六角数                                  1, 6, 15, 28, 45, ...

可以证实 .

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

jerryxjr1220

1. Tn= T 55385
   
2. Pn= P 31977
   
3. Hn= H 27693
   
4. 1533776805.0
   
5. [Finished in 36.8s]
   
6. 
   
7. Tn, Pn, Hn = [],[],[]
   
8. for n in range(286,100000):
   
9.         Tn.append (n * (n+1) / 2)
   
10. for n in range(286,100000):
    
11.         if n * (2 * n - 1) <= Tn[-1]:
    
12.                 Pn.append (n * (3 * n - 1) / 2)
    
13.                 Hn.append (n * (2 * n - 1))
    
14. for each in Tn:
    
15.         if each in Pn and each in Hn:
    
16.                 print ('Tn= T',Tn.index(each)+286)
    
17.                 print ('Pn= P',Pn.index(each)+286)
    
18.                 print ('Hn= H',Hn.index(each)+286)
    
19.                 print (each)
    
20.                 break
    

复制代码

jerryxjr1220

换了个算法，通过六角数反过来测试五角数和三角数，快了近1000倍！！！
大概30多毫秒出结果~

1. import time
   
2. 
   
3. def triangular(n): # Function to test if a number is triangular
   
4.     if ((8*n + 1)**0.5 - 1) % 2 == 0:
   
5.         return True
   
6.     else:
   
7.         return False
   
8. 
   
9. def pentagonal(n): # Function to test if a number is pentagonal
   
10.     if (1 + (24*n + 1)**0.5) % 6 == 0:
    
11.         return True
    
12.     else:
    
13.         return False
    
14. 
    
15. def hexagonal(n): # Function to test if a number is hexagonal
    
16.     if (1 + (8*n + 1)**0.5) % 4 == 0:
    
17.         return True
    
18.     else:
    
19.         return False
    
20. p = 41328 # This number is the 144th hexagonal number. This is why f = 144.
    
21. f = 144
    
22. start = time.time()
    
23. while True:
    
24.     if triangular(p) == True and pentagonal(p) == True and hexagonal(p) == True:
    
25.         break
    
26.     f += 1
    
27.     p = f*(2*f - 1) # Change p into the next hexagonal number
    
28. print(str(p) + " found in an amazing %s milliseconds!" % ("{0:.2f}".format((time.time() - start) * 1000)))

复制代码

飘飞的白杨

六角数一定是三角数
第 n个六边形数同时是第 2n-1个三角形数

1. n = 144
   
2. while True:
   
3.     m = n*(2*n-1)
   
4.     if ((m*24+1)**0.5+1)%6 == 0:
   
5.         print(m)
   
6.         break
   
7.     n += 1

复制代码

答案：1533776805

愤怒的大头菇

1. s = set((i*(i+1)/2) for i in range(1,250000))
   
2. 
   
3. t = set((i*(3*i-1)/2) for i in range(1,250000))
   
4. 
   
5. n = set((i*(2*i-1)) for i in range(1,250000))
   
6. 
   
7. for i in s:
   
8.     if i in t and i in n:
   
9.         print(i)

复制代码

愤怒的大头菇

1. s = set((i*(i+1)/2) for i in range(1,250000))
   
2. 
   
3. t = set((i*(3*i-1)/2) for i in range(1,250000))
   
4. 
   
5. n = set((i*(2*i-1)) for i in range(1,250000))
   
6. 
   
7. for i in s:
   
8.     if i in t and i in n:
   
9.         print(i)

复制代码

1.0
40755.0
1533776805.0

芒果加黄桃

1. # encoding:utf-8
   
2. # 找出40755下一个既是三角数、又是六角数和五角数的数字
   
3. from time import time
   
4. def euler045():
   
5.     h_n = 143
   
6.     p_n = 165
   
7.     t_n = 185
   
8.     while True:
   
9.         h_n += 1
   
10.         Hn = h_n * (2 * h_n - 1)
    
11.         Pn = int(p_n * (3 * p_n - 1) / 2)
    
12.         while Pn < Hn:
    
13.             p_n += 1
    
14.             t_n += 1
    
15.             Pn = int(p_n * (3 * p_n - 1) / 2)
    
16.         if Pn == Hn:
    
17.             Tn = int(t_n * (t_n + 1) / 2)
    
18.             while Tn < Hn:
    
19.                 t_n += 1
    
20.                 Tn = int(t_n * (t_n + 1) / 2)
    
21.             if Tn == Hn:
    
22.                 print('T(%d) = P(%d) = H(%d) = %d' % (t_n, p_n, h_n, Hn))
    
23.                 return
    
24. if __name__ == '__main__':
    
25.     start = time()
    
26.     euler045()
    
27.     print('cost %.6f sec' % (time() - start))
    

复制代码

T(55385) = P(31977) = H(27693) = 1533776805
cost 0.046000 sec

芒果加黄桃

百度了一下，才明白了3、4楼两位老大的公式，一元二次方程求解完全忘掉了...

渡风

此代码使用matlab编程
Problem45所用时间为1.8334秒
Problem45的答案为1533776805

1. %% Problem45.m
   
2. %最后编辑时间：2017-06-13 9:51 版本1.0
   
3. %找出40755后的数，这个数满足同时为三角型，五角型，六角形数
   
4. %由于六角形数必定为三角性数，所以不需要搜索三角型数
   
5. % Problem45所用时间为1.8334秒
   
6. % Problem45的答案为1533776805
   
7. function Output = Problem45()
   
8. tic
   
9. 
   
10. Meet = 0;
    
11. 
    
12. Start = 144;
    
13. 
    
14. while (Meet == 0)
    
15.     Hexa = Start * (2*Start - 1);
    
16.     if  IsPentagon(Hexa) == 1
    
17.         Meet = 1;
    
18.         break
    
19.     end
    
20.     Start = Start + 1;
    
21. end
    
22. 
    
23. Output = Hexa;
    
24. toc
    
25. 
    
26. disp('此代码使用matlab编程')
    
27. disp(['Problem45所用时间为',num2str(toc),'秒'])
    
28. disp(['Problem45的答案为',num2str(Output)])
    
29. end
    
30. %% IsPentagon.m
    
31. % 测试一个数是否为五角星
    
32. % 最后编辑时间：17-06-13 9:03 版本：1.0
    
33. % 是五角型数则返回 1，否则返回 0
    
34. function Judge = IsPentagon(n)
    
35. if nargin == 0
    
36. n = 22;
    
37. end
    
38. if n == 1
    
39.     Judge = 1;
    
40. else
    
41.     front = floor(sqrt(2*n)/2);
    
42.     after = ceil(sqrt(2*n)/1.7);
    
43.     Judge = 0;
    
44.     for ii = after:-1:front
    
45.         if n == ((3*ii - 1) * ii)/2
    
46.             Judge = 1;
    
47.             break
    
48.         end
    
49.     end
    
50. end
    
51. end

复制代码

najin

用的matlab
结果是：
1533776805
时间已过 0.002740 秒。
>>

永恒的蓝色梦想

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     ios::sync_with_stdio(false);
   
8.     unsigned int pentagonal = 40755, pentagonal_n = 165, hexagonal = 40755, hexagonal_n = 143;
   
9. 
   
10. 
    
11.     do {
    
12.         if (hexagonal > pentagonal) {
    
13.             pentagonal += 3 * pentagonal_n + 1;
    
14.             pentagonal_n++;
    
15.         }
    
16.         else {
    
17.             hexagonal += (hexagonal_n << 2) + 1;
    
18.             hexagonal_n++;
    
19.         }
    
20.     } while (hexagonal - pentagonal);
    
21. 
    
22. 
    
23.     cout << hexagonal << endl;
    
24.     return 0;
    
25. }

复制代码

debuggerzh

31977 1533776805

Process returned 0 (0x0)   execution time : 0.053 s
Press any key to continue.
分析可知六角数一定是三角数，有H_k=T_2k-1
因此只需验证五角数是否为六角数
暴力打表，二分搜索

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. typedef long long ll;
   
5. 
   
6. const int M = 50000;
   
7. ll p[M] = {0},h[M] = {0};
   
8. 
   
9. int main(){
   
10. 
    
11.   for (int i = 1;i < M;i++){
    
12.     p[i] = (ll)i*(3*i-1)/2;
    
13.     h[i] = (ll)i*(2*i-1);
    
14.         }
    
15. 
    
16.         for (int i = 166;i < M;i++){
    
17.     if (binary_search(h,h+M,p[i]))
    
18.       cout << i << " " << p[i] << endl;
    
19.         }
    
20. 
    
21.         return 0;
    
22. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int check_Pentagonal(int);
   
5. int check_Pentagonal(int num)
   
6. {
   
7.         double j;
   
8.         int i;
   
9.         j = (sqrt(24 * (double)num + 1) + 1) / 6;
   
10.         i = (sqrt(24 * (double)num + 1) + 1) / 6;
    
11.        
    
12.         if ((double)i == j)
    
13.         {
    
14.                 return 1;
    
15.         }
    
16.         else
    
17.         {
    
18.                 return 0;
    
19.         }
    
20. }
    
21. 
    
22. 
    
23. main()
    
24. {
    
25.         int i = 143, j;
    
26.         while (1)
    
27.         {
    
28.                 i++;
    
29.                 j = i * (2 * i - 1);
    
30.                 if (check_Pentagonal(j))
    
31.                 {
    
32.                         printf("%u", j);
    
33.                         break;
    
34.                 }
    
35.         }
    
36. }

复制代码

1533776805

ft215378

#在40755之后最小的既是五角数又是六角数的三角数是多少
from time import *
'''三角数，五角数和六角数分别通过以下公式定义：
三角数： 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
找出这之后的下一个既是五角数又是六角数的三角数。
'''
#三角数
def triangle(n):
    i = 286
    t = []
    while i < n:
        t.append(i*(i+1)//2)
        i += 1
    return t
        

#五角数
def pentagonal(n):
    i = 166
    p = []
    while i < n:
        p.append(i*(3*i-1)//2)
        i += 1
    return p
        

#六角数
def hexagonal(n):
    i = 144
    h = []
    while i < n:
        h.append(i*(2*i-1))
        i += 1
    return h
s = time()
n = 1000
while n:
    result = list(set(triangle(n)) & set(pentagonal(n)) & set(hexagonal(n)))
    if result != []:
        print(result[0])
        break
    else:
        n *= 10
e = time()
print("用时%.4f秒" % (e-s))

B1tetheDust

1. import time as t
   
2. import numpy as np
   
3. 
   
4. start = t.perf_counter()
   
5. 
   
6. n_t = 285
   
7. while True:
   
8.     n_t += 1
   
9.     Tn = n_t * (n_t + 1) / 2
   
10.     n_p = int(np.sqrt(2 / 3 * Tn)) + 1
    
11.     n_h = int(np.sqrt(1 / 2 * Tn)) + 1
    
12.     Pn = n_p * (3 * n_p - 1) / 2
    
13.     Hn = n_h * (2 * n_h - 1)
    
14.     if Tn == Pn == Hn:
    
15.         break
    
16. 
    
17. print(Tn)
    
18. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

1533776805.0
It costs 0.119939 s