Problem 44 | Project Euler |

[sx349]

https://pe-cn.github.io/44/

Problem 44 Pentagon numbers Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... It can be seen that P4 +

[shangkelingxiang]

p=[i*(3*i-1)//2 for i in range(1,5000)]
k=[0]*105000000
for i in p:
    k[i]=1
o=190000000
for i in p:
    for j in p:
        if k[abs(i-j)]==1 and k[i+j]==1:
            o=min(o,abs(i-j))
print(o)

[p-gp]

#include <stdio.h>
#define M 10000000

int arr[M]={0};
float rSqrt (float x);
_Bool isPentagon(long long int num);
int main(){

    long long int t=100000000, x,y;
    for(int i=1;i<M;++i){
        arr[i]=3*i+1;
        for(int j=i-1; j>0; --j){
            arr[j]=arr[i]+arr[j];
        }

        if(arr[i]>t){
            printf("\n\n%lld-%lld=%lld\n", x, y, t);
            break;
        }
        for(int k=i; k>0; --k){
            if(arr[k]>=t){
                break;
            }
            if(isPentagon(arr[k])&&isPentagon((3*k*k-k)/2+(3*(i+1)*(i+1)-(i+1))/2)){
                t=arr[k];
                y=k;
                x=i+1;
                printf("%d  ",t);
                break;
            }
        }
    }

    return 0;
}

_Bool isPentagon(long long int num){
    long long int x=(long long int)rSqrt((float)(num*24+1));
    if(x*x==num*24+1&&((1+x)%6==0)){
        return 1;
    }
    return 0;
}

float rSqrt(float x){

    float xhalf =0.5f*x;

    int i=*(int*)&x;
    i=0x5f3759df-(i>>1);
    x=*(float*)&i;
    x=x*(1.5f-xhalf*x*x); 
    x=x*(1.5f-xhalf*x*x);  
    x=x*(1.5f-xhalf*x*x);

    return (1/x);
}