题目44：找出最小的和与差都是五角数的五角数对

欧拉计划 · 发表于 2015-5-16 22:40:44

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

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

x

Pentagon numbers

Pentagonal numbers are generated by the formula, . The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that . However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, , for which their sum and difference are pentagonal and is minimised; what is the value of D?

题目：

五角数通过如下公式定义：

。前十个五角数是：

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

可以看出

. 但是它们的差 70 − 22 = 48 却不是五角数。

找出最小的五角数对

，使得它们的和与差都是五角数，并且

取到最小。这时 D 的值是多少?

迷雾少年 · 发表于 2016-8-30 18:05:30

看不懂。。

jerryxjr1220 · 发表于 2016-10-6 10:40:30

本帖最后由 jerryxjr1220 于 2016-10-12 14:07 编辑

Find: P1:7042750,P2:1560090,D:5482660,S:8602840

def isRoot(x): #根的求解方程，判别是否是整数
if (1+(1+24*x)**0.5) % 6 == 0:
return 1
else:
return 0
for i in range(1,10000):
P1 = int(i*(3*i-1)/2)
for j in range(i,1,-1):
P2 = int(j*(3*j-1)/2)
if isRoot(P1+P2) and isRoot(P1-P2):
print ('Find: P1:%d,P2:%d,D:%d,S:%d' % (P1,P2,P1-P2,P1+P2))
exit()

复制代码

jerryxjr1220 · 发表于 2016-10-12 14:17:33

利用set（）元组去搜索，更快速 0.3 sec出结果

from time import time
start = time()
def generatePentagonals(n):
pentagonals = [0]
x=1
while pentagonals[len(pentagonals)-1] < n:
pentagonals.append(x*(3*x-1)/2)
x+=1
pentagonals.pop(0)
return pentagonals
def findPair(p):
pSet = set(p)
for i in range (1,len(p)):
for j in range(0,i):
if (p[i]-p[j] in pSet) and (p[i]+p[j] in pSet):
return p[i] - p[j]
return "Pair not in range"
print (findPair(generatePentagonals(10000000)))
print("Time: {0} secs".format(time()-start))

复制代码

飘飞的白杨 · 发表于 2016-10-25 18:59:03

def progrem44():
s = set(i*(3*i-1)//2 for i in range(1,2501))
for i in s:
for j in s:
if i < j: continue
if i+j in s and i+2*j in s:
return j,i+j
print(progrem44())

复制代码

芒果加黄桃 · 发表于 2017-1-16 09:45:58

没有好办法，学习4楼老大代码

愤怒的大头菇 · 发表于 2017-6-5 22:55:02

本帖最后由永恒的蓝色梦想于 2020-7-2 18:26 编辑

def Pentagon(n):
numbers = n*(3*n-1)/2
return numbers
def Judg(x, i):
for n in range(1, 2*i-1):
if x == n*(3*n-1)/2:
return True
return False
i = 2
temps = True
while temps:
for n in range(1, i):
temp = Pentagon(i) - Pentagon(n)
tmp = Pentagon(i) + Pentagon(n)
if Judg(temp, i) and Judg(tmp, i):
print(temp)
temps = False
i += 1

复制代码

能算出来，但是速度很慢

渡风 · 发表于 2017-6-13 09:20:00

本帖最后由渡风于 2017-6-13 09:33 编辑

%% Problem44.m
%最后编辑时间：2017-06-13 9:21 版本1.0
%找出两个五角星数，使得它们的和为五角星数，差为五角星数且为最小
% Problem44所用时间为28.294秒
% Problem44的答案为5482660

%% Problem44.m
%最后编辑时间：2017-06-13 9:21 版本1.0
%找出两个五角星数，使得它们的和为五角星数，差为五角星数且为最小
% Problem44所用时间为28.294秒
% Problem44的答案为5482660
function Output = Problem44()
tic
Start = 3;
Meet = 0;
while (Meet == 0)
Bignum = (Start * (3*Start - 1))/2;
for ii = Start - 1: -1 : 1
Smallnum = (ii * (3*ii - 1))/2;
if IsPentagon(Bignum - Smallnum) == 1 && IsPentagon(Bignum + Smallnum) == 1
Meet = 1;
break
end
end
Start = Start + 1;
disp(Start)
end
Output = Bignum - Smallnum;
toc
disp('此代码使用matlab编程')
disp(['Problem44所用时间为',num2str(toc),'秒'])
disp(['Problem44的答案为',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

复制代码

cq_xuke · 发表于 2017-8-18 23:24:12

import time
s=time.clock()
from itertools import takewhile
def pentagon(init=None):
if init is None:
init=1
while not ispentagon(init):
init+=1
n=((1+24*init)**0.5+1)//6
while True:
yield n*(3*n-1)//2
n+=1
def ispentagon(n):
flag=False
if int(((1+24*n)**0.5+1)/6)==((1+24*n)**0.5+1)/6:
flag=True
return flag
flag=False
for p1 in pentagon(3):
if flag==True:
break
for p2 in takewhile(lambda x:x<p1,pentagon(1)):
if ispentagon(p1+p2) and ispentagon(p1-p2):
print(int(p1-p2))
flag=True
break
print('Runing time: {0}s'.format(round(time.clock()-s,3)))

复制代码

5482660
Runing time: 3.316s

najin · 发表于 2017-9-30 10:51:29

用的matlab
结果是：
>> Untitled
   7042750

   1560090

   5482660

时间已过 0.167725 秒。
>>

王小召 · 发表于 2019-6-21 10:41:54

最小值是：442.0
用时：0.7488047999999999秒

import math
import time

def pentagon_num(num):
if int(math.sqrt(24*num + 1)) == math.sqrt(24*num + 1):
      return True

def cal_result():
result = []
#  2000的五角数范围已经达到 1000 * (2999)/2 = 1499500
for i in range(2, 1000):
      for j in range(1, i):
         if pentagon_num(i*(3*i-1)/2 + j*(3*j-1)/2) and pentagon_num(i*(3*i-1)/2 - j*(3*j-1)/2):
            result.append(i*(3*i-1)/2 - j*(3*j-1)/2)
return result

print("最小值是：{}\n用时：{}秒".format(min(cal_result()), time.process_time()))

永恒的蓝色梦想 · 发表于 2019-8-5 13:13:24

本帖最后由永恒的蓝色梦想于 2020-5-8 08:26 编辑

抄了一下3L的求根公式：

isRoot=lambda x:not(1+(1+24*abs(x))**0.5)%6
pentagon=lambda x:(3*x-1)*x//2
for k in range(1,10000):
i=pentagon(k)
for j in range(k,10000):
j=pentagon(j)
if isRoot(i-j)and isRoot(i+j):
print(f'运行结果：{abs(i-j)}\n运行时间：{t()-t1}s')
exit()

复制代码

debuggerzh · 发表于 2020-8-18 19:51:50

5482660

Process returned 0 (0x0) execution time : 1.176 s
Press any key to continue.
纯暴力解法。不妨设Pj>Pk
先枚举D，再枚举Pk，二分查找
D小于P[k+1] - P[k]时枚举下一个D

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 3e3;
int p[M] = {0,1};
void ini(){
for (int i = 2;i < M;i++){
p[i] = p[i-1] + 3*i - 2;
}
}
void print(int n){
for (int i = 1;i < n;i++){
cout << p[i] << endl;
}
}
int main(){
ini();
for (int a = 2;;a++){
for (int k = 1;k+1 < M && p[k+1] - p[k] <= p[a];k++){
if (!binary_search(p, p+M, p[a] + p[k])) continue;
if (!binary_search(p, p+M, p[a] + 2*p[k])) continue;
cout << p[a] << endl;
return 0;
}
}
return 0;
}

复制代码

a1351468657 · 发表于 2021-3-20 17:08:59

#include <stdio.h>
#include <math.h>
int check_Pentagonal(int);
int check_Pentagonal(int num)
{
if (num == 0)
{
return 0;
}
float j;
int i;
j = (sqrt(24 * num + 1) + 1) / 6;
i = (sqrt(24 * num + 1) + 1) / 6;
if ((float)i == j)
{
return 1;
}
else
{
return 0;
}
}
main()
{
int i, j, m, n;
for (i = 2; i < 10000; i++)
{
for (j = i; j >= 1; j--)
{
m = i * (i * 3 - 1) / 2;
n = j * (j * 3 - 1) / 2;
if (check_Pentagonal(m + n))
{
if (check_Pentagonal(m - n))
{
goto Label;
}
}
}
}
Label:printf("Pj = %d, Pk = %d D = %d", m, n, m - n);
}

复制代码

Pj = 1560090, Pk = 7042750 D = 5482660

guosl · 发表于 2022-1-8 00:28:30

本帖最后由 guosl 于 2022-1-8 00:30 编辑

/*
答案：5482660
耗时：2.34444秒（单核）
0.198174秒（八核）
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <omp.h>
using namespace std;
int main(void)
{
//打表
vector<int> v;
int k = 1;
while (true)
{
int p = k * (3 * k - 1) / 2;
if (p < 1000000000)
{
v.push_back(p);
++k;
}
else
break;
}
int nMinD = 0x7fffffff, nK = int(v.size());
volatile int i = 0;
volatile bool bContinue = true;
#pragma omp parallel firstprivate(nK) shared(i,v,bContinue) reduction(min:nMinD)
while (bContinue && i < nK)
{
int nD;
#pragma omp critical(c1)
nD = v[i++];//枚举差
bool bFind = false;
for (int j = 0; j < nK; ++j)
{
auto itr = lower_bound(v.begin(), v.end(), nD + v[j]);
if (itr != v.end() && *itr == nD + v[j])//找到两个五边形数使其差位nD
{
int k = int(itr - v.begin());
int nD1 = v[k] + v[j];
itr = lower_bound(v.begin(), v.end(), nD1);
if (itr != v.end() && *itr == nD1)//找到两个五边形数使其和与差都是五边形数
{
bFind = true;
break;
}
}
}
if (bFind)
{
nMinD = min(nD, nMinD);//记录最后结果
#pragma omp critical(c2)
bContinue = false;
}
}
cout << nMinD << endl;
return 0;
}

复制代码

B1tetheDust · 发表于 2022-10-24 22:21:27

import time as t
import numpy as np
start = t.perf_counter()
def is_integer(a_num):
delta = 0.00001
if abs(a_num - int(a_num)) < delta:
return True
def find_pentagon():
given_range = 3000
for j in range(1000, given_range):
for k in range(j + 2, given_range + 2):
k_add_j = np.sqrt(np.square(k) + np.square(j) - 1 / 3 * (k + j) + 1 / 36) + 1 / 6
k_minus_j = np.sqrt(np.square(k) - np.square(j) - 1 / 3 * (k - j) + 1 / 36) + 1 / 6
if is_integer(k_add_j) and is_integer(k_minus_j):
return [j, k, k_minus_j]
nums = find_pentagon()
print(nums[2] * (3 * nums[2] - 1) / 2)
print("It costs %f s" % (t.perf_counter() - start))

复制代码

5482660.0
It costs 0.448183 s

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

题目44：找出最小的和与差都是五角数的五角数对

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

浏览过的版块