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

欧拉计划 · 发表于 2015-5-16 23:21:34

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 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, ...

可以证实

.

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

jerryxjr1220 · 发表于 2016-9-22 23:55:49

Tn= T 55385
Pn= P 31977
Hn= H 27693
1533776805.0
[Finished in 36.8s]

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

jerryxjr1220 · 发表于 2016-10-12 14:28:47

换了个算法，通过六角数反过来测试五角数和三角数，快了近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:16:04

本帖最后由飘飞的白杨于 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

愤怒的大头菇 · 发表于 2016-11-17 19:47:32

本帖最后由永恒的蓝色梦想于 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)

愤怒的大头菇 · 发表于 2016-11-17 19:48:38

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

芒果加黄桃 · 发表于 2017-1-16 10:22:40

# 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

芒果加黄桃 · 发表于 2017-1-16 10:34:27

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

渡风 · 发表于 2017-6-13 09:48:17

此代码使用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);
    if  IsPentagon(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

najin · 发表于 2017-9-30 10:56:13

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

永恒的蓝色梦想 · 发表于 2020-6-6 09:32:36

本帖最后由永恒的蓝色梦想于 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;
}

debuggerzh · 发表于 2020-8-14 10:57:12

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[M] = {0},h[M] = {0};

int main(){

  for (int i = 1;i < M;i++){
    p[i] = (ll)i*(3*i-1)/2;
    h[i] = (ll)i*(2*i-1);
        }

        for (int i = 166;i < M;i++){
    if (binary_search(h,h+M,p[i]))
      cout << i << " " << p[i] << endl;
        }

        return 0;
}

a1351468657 · 发表于 2021-3-20 19:02:31

#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

ft215378 · 发表于 2021-10-22 15:10:06

#在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 · 发表于 2022-10-24 22:41:02

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

账号		自动登录	找回密码
密码			立即注册