CODEWITHSUNDEEP
c++
Ranveer
Ranveer

Reputation: 6863

Code for Project Euler No 45 not working

Here is the problem, Project Euler #45

And here's the code I wrote for it:

#include <iostream>
#include <math.h>
using namespace std;

bool ispent (long num){
    long double x = (sqrt(24*num+1) + 1.0)/6.0;
    if (floor(x)==x) return true;
    else return false;
}

bool ishex (long num){
    long double x = (sqrt(8*num+1) + 1.0)/4.0;
    if (floor(x)==x) return true;
    else return false;
}

int main(){
    int i=286;
    while(true){
        long x = (i*(i+1))/2;
        if((ispent(x)) && (ishex(x))){
            cout << x;
            break;
        }
        i++;
    }
}

This gives the output 40755, whereas I require the next number. What could be the possible bug?

Upvotes: 0

Views: 241

Answers (2)

jh314
jh314

Reputation: 27792

The issue is that using square roots to check if a number is pentagonal or hexagonal is imprecise, so the test will fail and you will overflow x.

To fix this, you can use a type with more precision, like replacing long with unsigned long, or even unsigned long long.

Upvotes: 3

Peter
Peter

Reputation: 14937

You are overflowing the 32-bit representation of x. If you know the next x is 1533776805, then an intermediate value of 2x is necessary, which at 3e9 overflows a signed integer. You can just fit this in an unsigned int, but I would use a 64-bit integer instead. #include <stdint.h>, and use int64_t for both i and x. But I agree with the other commenters, there's something suspicious about testing for exact double precision answers

Upvotes: 0

Related Questions