Results 1 to 1 of 1
  1. Default Project Euler 408.


    I am stuck on this.

    Problem link

    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 xullong y) {
        return (
    == 0) ? gcd(y,(x%y));
    }

    template<typename T>
    std::vector<std::pair<T,T>> generateTriples(ullong limit) {
        
    std::vector<std::pair<T,T>> triples;
        
    ullong ab;
        for(
    ullong n 1limit; ++n) {
            if(
    n*+ (n+1)*(n+1) > limit)
                break;
            for(
    ullong m n+1limit+= 2) {
                if(
    n*m*limit)
                    break;
                if(
    gcd(n,m) > 1)
                    continue;
                
    m*n*n;
                
    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(
    autotriples)
            
    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.

    Thank you for your help.

    Update 1:
    I changed the Pythagorean Triple to:
    PHP Code:
    template<typename T>
    std::vector<std::pair<T,T>> generateTriples(ullong limitullong c) {
        
    std::vector<std::pair<T,T>> triples;
        
    ullong ab;
        for(
    ullong i 1c; ++i) {
            for(
    ullong j 1i; ++j) {
                
    i*j*j;
                
    2*i*j;
                if(
    a*<= limit && 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.
    Last edited by Locked; 2012-12-31 at 03:06 AM.

  2.  

Bookmarks

Posting Permissions

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