Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the triangles with integer sides a, b and c with a ≤ b ≤ c. An integer sided triangle (a,b,c) is called primitive if gcd(a,b,c)=1. How many primitive integer sided triangles exist with a perimeter not exceeding 10 000 000?

I am trying to solve this on euler project. I am wondering what is the best way to go to find the valid triples for constructing a triangle. Of course you can do nested for loops but that is not efficient. Any pointers would help.

Thanks

share|improve this question
add comment

3 Answers 3

This is problem 276. I haven't solved it, but the first thing to realize is you don't have to loop over c-from a and b you should be able to find the number of solutions. Of course, you don't have time to loop over both a and b, but you may be able to loop over a. I would start by doing a brute force run up to 100 or 250-you should have time for that. Keep track of the number of solutions for each a. Then try to find a formula for the number of triangles that include a. This will probably be based on the factors of a.

Hope this helps. I did a lot of them, but have gotten less energetic now.

share|improve this answer
add comment

HINT $\rm\ gcd(a,b,c) = gcd(10^7-b-c,b,c) = gcd(10^7,b,c)\:, $ so a triple will be primitive unless $\rm\:b,c\:$ are both divisible by $2$ or $5$. The longest leg $\rm\:c\:$ must be less than half the perimeter $\rm\:P\:$ and at least $\rm\:P/3\:.\: $ Therefore, for each $\rm\:c\:$ in this range, count the values of $\rm\ b = c,\: c-1,\ldots, \lceil (P-c)/2\rceil\ $ such that $\rm\:b,c\:$ have neither $2$ nor $5$ as a common divisor. It depends only on $\rm\:b,c\:$ modulo $\ldots$

share|improve this answer
2  
The perimeter need not be $=10^7$, it just has to be $\leq 10^7$ –  Ross Millikan Jan 5 '11 at 21:35
    
Indeed, but once should able to use similar sieve-like ideas to avoid gcd computations. But there is probably a better way. –  Bill Dubuque Jan 5 '11 at 22:06
    
Does it mean that the solution wont work for p <= 10^7? –  Jinesh Parekh Jan 6 '11 at 6:07
add comment

There is a formula which gives you all the Pythagorean triples. That should cut down your search space a bit.

share|improve this answer
2  
The triangles need not be right-angled. –  Chris Eagle Jan 5 '11 at 16:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.