题目45：在40755之后最小的既是五角数又是六角数的三角数是多少？
本帖最后由 欧拉计划 于 2015-5-16 23:25 编辑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, ...
可以证实.
找出这之后的下一个既是五角数又是六角数的三角数。 Tn= T 55385
Pn= P 31977
Hn= H 27693
1533776805.0
Tn, Pn, Hn = [],[],[]
for n in range(286,100000):
Tn.append (n * (n+1) / 2)
for n in range(286,100000):
if n * (2 * n - 1) <= Tn[-1]:
Pn.append (n * (3 * n - 1) / 2)
Hn.append (n * (2 * n - 1))
for each in Tn:
if each in Pn and each in Hn:
print ('Tn= T',Tn.index(each)+286)
print ('Pn= P',Pn.index(each)+286)
print ('Hn= H',Hn.index(each)+286)
print (each)
break
换了个算法，通过六角数反过来测试五角数和三角数，快了近1000倍！！！
大概30多毫秒出结果~
import time
def triangular(n): # Function to test if a number is triangular
if ((8*n + 1)**0.5 - 1) % 2 == 0:
return True
else:
return False
def pentagonal(n): # Function to test if a number is pentagonal
if (1 + (24*n + 1)**0.5) % 6 == 0:
return True
else:
return False
def hexagonal(n): # Function to test if a number is hexagonal
if (1 + (8*n + 1)**0.5) % 4 == 0:
return True
else:
return False
p = 41328 # This number is the 144th hexagonal number. This is why f = 144.
f = 144
start = time.time()
while True:
if triangular(p) == True and pentagonal(p) == True and hexagonal(p) == True:
break
f += 1
p = f*(2*f - 1) # Change p into the next hexagonal number
print(str(p) + " found in an amazing %s milliseconds!" % ("{0:.2f}".format((time.time() - start) * 1000))) 本帖最后由 飘飞的白杨 于 2016-10-25 20:17 编辑
六角数一定是三角数
第 n个六边形数同时是第 2n-1个三角形数
n = 144
while True:
m = n*(2*n-1)
if ((m*24+1)**0.5+1)%6 == 0:
print(m)
break
n += 1
答案：1533776805 本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:40 编辑
s = set((i*(i+1)/2) for i in range(1,250000))
t = set((i*(3*i-1)/2) for i in range(1,250000))
n = set((i*(2*i-1)) for i in range(1,250000))
for i in s:
if i in t and i in n:
print(i) s = set((i*(i+1)/2) for i in range(1,250000))
t = set((i*(3*i-1)/2) for i in range(1,250000))
n = set((i*(2*i-1)) for i in range(1,250000))
for i in s:
if i in t and i in n:
print(i)
1.0
40755.0
1533776805.0
# encoding:utf-8
# 找出40755下一个既是三角数、又是六角数和五角数的数字
from time import time
def euler045():
h_n = 143
p_n = 165
t_n = 185
while True:
h_n += 1
Hn = h_n * (2 * h_n - 1)
Pn = int(p_n * (3 * p_n - 1) / 2)
while Pn < Hn:
p_n += 1
t_n += 1
Pn = int(p_n * (3 * p_n - 1) / 2)
if Pn == Hn:
Tn = int(t_n * (t_n + 1) / 2)
while Tn < Hn:
t_n += 1
Tn = int(t_n * (t_n + 1) / 2)
if Tn == Hn:
print('T(%d) = P(%d) = H(%d) = %d' % (t_n, p_n, h_n, Hn))
return
if __name__ == '__main__':
start = time()
euler045()
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
%% Problem45.m
%最后编辑时间：2017-06-13 9:51 版本1.0
%找出40755后的数，这个数满足同时为三角型，五角型，六角形数
%由于六角形数必定为三角性数，所以不需要搜索三角型数
% Problem45所用时间为1.8334秒
% Problem45的答案为1533776805
function Output = Problem45()
tic
Meet = 0;
Start = 144;
while (Meet == 0)
Hexa = Start * (2*Start - 1);
ifIsPentagon(Hexa) == 1
Meet = 1;
break
end
Start = Start + 1;
end
Output = Hexa;
toc
disp('此代码使用matlab编程')
disp(['Problem45所用时间为',num2str(toc),'秒'])
disp(['Problem45的答案为',num2str(Output)])
end
%% IsPentagon.m
% 测试一个数是否为五角星
% 最后编辑时间：17-06-13 9:03 版本：1.0
% 是五角型数则返回 1，否则返回 0
function Judge = IsPentagon(n)
if nargin == 0
n = 22;
end
if n == 1
Judge = 1;
else
front = floor(sqrt(2*n)/2);
after = ceil(sqrt(2*n)/1.7);
Judge = 0;
for ii = after:-1:front
if n == ((3*ii - 1) * ii)/2
Judge = 1;
break
end
end
end
end 用的matlab
结果是：
1533776805
时间已过 0.002740 秒。
>> 本帖最后由 永恒的蓝色梦想 于 2021-9-1 10:39 编辑
#include<iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
unsigned int pentagonal = 40755, pentagonal_n = 165, hexagonal = 40755, hexagonal_n = 143;
do {
if (hexagonal > pentagonal) {
pentagonal += 3 * pentagonal_n + 1;
pentagonal_n++;
}
else {
hexagonal += (hexagonal_n << 2) + 1;
hexagonal_n++;
}
} while (hexagonal - pentagonal);
cout << hexagonal << endl;
return 0;
} 31977 1533776805
Process returned 0 (0x0) execution time : 0.053 s
Press any key to continue.
分析可知六角数一定是三角数，有H_k=T_2k-1
因此只需验证五角数是否为六角数
暴力打表，二分搜索
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M = 50000;
ll p = {0},h = {0};
int main(){
for (int i = 1;i < M;i++){
p = (ll)i*(3*i-1)/2;
h = (ll)i*(2*i-1);
}
for (int i = 166;i < M;i++){
if (binary_search(h,h+M,p))
cout << i << " " << p << endl;
}
return 0;
}
#include <stdio.h>
#include <math.h>
int check_Pentagonal(int);
int check_Pentagonal(int num)
{
double j;
int i;
j = (sqrt(24 * (double)num + 1) + 1) / 6;
i = (sqrt(24 * (double)num + 1) + 1) / 6;
if ((double)i == j)
{
return 1;
}
else
{
return 0;
}
}
main()
{
int i = 143, j;
while (1)
{
i++;
j = i * (2 * i - 1);
if (check_Pentagonal(j))
{
printf("%u", j);
break;
}
}
}
1533776805 #在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)
break
else:
n *= 10
e = time()
print("用时%.4f秒" % (e-s))
import time as t
import numpy as np
start = t.perf_counter()
n_t = 285
while True:
n_t += 1
Tn = n_t * (n_t + 1) / 2
n_p = int(np.sqrt(2 / 3 * Tn)) + 1
n_h = int(np.sqrt(1 / 2 * Tn)) + 1
Pn = n_p * (3 * n_p - 1) / 2
Hn = n_h * (2 * n_h - 1)
if Tn == Pn == Hn:
break
print(Tn)
print("It costs %f s" % (t.perf_counter() - start))
1533776805.0
It costs 0.119939 s
页:
[1]