1. ## Project Euler 408.

I am stuck on this.

Let us consider the fact that if there are no inadmissible points, then the function to determine the number of total paths is defined as nCr(2n,n). This is especially true because when you consider P(5), there are 0 inadmissible paths and the function nCr(10,5) == 252, which is the answer to the problem. However, consider the other givens, P(16) has 2 inadmissible nodes, both (16,9) and (9,16). However, finding out nCr(32,16) leads us with 601080390, yet the answer is 596994440 for a difference of 4085950 for just two inadmissible nodes. P(1000) has about 26 nodes and the results are even larger. The arbitrary digit would take up quite an amount of space here.

I figured there had to be a different way of doing it so I thought about it and if we set x = a^2, and y = b^2, then x+y is the same as a^2 + b^2 = c^2, so in order for a point to be inadmissible, it has to be a Pythagorean triple, which might improve the runtime of the code by a ton compared to finding the square root of the number to figure out if it's a perfect square. However as of that point, I'm lost. I have a couple of ideas to throw around and linger but I'm unsure of how to calculate N amount of Pythagorean triples that threshold to that limit. I tried applying Euclid's formula in C++ here:

PHP Code:
``` #include <iostream>#include <vector>#include <utility>#include <cmath>using ullong = unsigned long long;constexpr ullong gcd(ullong x, ullong y) {    return (y == 0) ? x : gcd(y,(x%y));}template<typename T>std::vector<std::pair<T,T>> generateTriples(ullong limit) {    std::vector<std::pair<T,T>> triples;    ullong a, b;    for(ullong n = 1; n < limit; ++n) {        if(n*n + (n+1)*(n+1) > limit)            break;        for(ullong m = n+1; m < limit; m += 2) {            if(n*n + m*m > limit)                break;            if(gcd(n,m) > 1)                continue;            a = m*m - n*n;            b = 2*m*n;            triples.push_back(std::make_pair(a*a,b*b));        }    }    return triples;}int main() {    std::vector<std::pair<unsigned,unsigned>> triples = generateTriples<unsigned>(100);    for(auto& i : triples)        std::cout << "a: " << i.first << " b: " << i.second << '\n';}  ```
Output

However, I'm still kind of unsure where else to go about with this. What do? :(

My questions:
Is there a better way to solve it?
How do I generate Pythagorean Triples with an arbitrary limit of N?

I will post updates I guess.

Update 1:
I changed the Pythagorean Triple to:
PHP Code:
``` template<typename T>std::vector<std::pair<T,T>> generateTriples(ullong limit, ullong c) {    std::vector<std::pair<T,T>> triples;    ullong a, b;    for(ullong i = 1; i < c; ++i) {        for(ullong j = 1; j < i; ++j) {            a = i*i - j*j;            b = 2*i*j;            if(a*a <= limit && b*b <= limit) {                triples.push_back(std::make_pair(a*a,b*b));                triples.push_back(std::make_pair(b*b,a*a));            }        }    }    return triples;}  ```
It works for both P(5) and P(16) but fails for P(1000) % 1000000007.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•