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

欧拉计划

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 的值是多少?

迷雾少年

看不懂。。

jerryxjr1220

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

利用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))

飘飞的白杨

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楼老大代码

愤怒的大头菇

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

能算出来，但是速度很慢

渡风

%% 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

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

用的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()))

永恒的蓝色梦想

抄了一下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

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

#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

/*
答案：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

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