题目44：找出最小的和与差都是五角数的五角数对
Pentagon numbersPentagonal 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 andis minimised; what is the value of D?
题目：
五角数通过如下公式定义：。前十个五角数是：
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
可以看出. 但是它们的差 70 − 22 = 48 却不是五角数。
找出最小的五角数对， 使得它们的和与差都是五角数，并且取到最小。这时 D 的值是多少?
看不懂。。 本帖最后由 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()
利用set（）元组去搜索，更快速 0.3 sec出结果
from time import time
start = time()
def generatePentagonals(n):
pentagonals =
x=1
while pentagonals < 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-p in pSet) and (p+p in pSet):
return p - p
return "Pair not in range"
print (findPair(generatePentagonals(10000000)))
print("Time: {0} secs".format(time()-start)) 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()) 没有好办法，学习4楼老大代码 本帖最后由 永恒的蓝色梦想 于 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: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 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 用的matlab
结果是：
>> Untitled
7042750
1560090
5482660
时间已过 0.167725 秒。
>> 最小值是：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()))
本帖最后由 永恒的蓝色梦想 于 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() 5482660
Process returned 0 (0x0) execution time : 1.176 s
Press any key to continue.
纯暴力解法。不妨设Pj>Pk
先枚举D，再枚举Pk，二分查找
D小于P - P时枚举下一个D
#include<iostream>
#include<algorithm>
using namespace std;
const int M = 3e3;
int p = {0,1};
void ini(){
for (int i = 2;i < M;i++){
p = p + 3*i - 2;
}
}
void print(int n){
for (int i = 1;i < n;i++){
cout << p << endl;
}
}
int main(){
ini();
for (int a = 2;;a++){
for (int k = 1;k+1 < M && p - p <= p;k++){
if (!binary_search(p, p+M, p + p))continue;
if (!binary_search(p, p+M, p + 2*p))continue;
cout << p << endl;
return 0;
}
}
return 0;
}
#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: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;//枚举差
bool bFind = false;
for (int j = 0; j < nK; ++j)
{
auto itr = lower_bound(v.begin(), v.end(), nD + v);
if (itr != v.end() && *itr == nD + v)//找到两个五边形数使其差位nD
{
int k = int(itr - v.begin());
int nD1 = v + v;
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;
} 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
nums = find_pentagon()
print(nums * (3 * nums - 1) / 2)
print("It costs %f s" % (t.perf_counter() - start))
5482660.0
It costs 0.448183 s
{:10_256:}
页:
[1]