Project Euler Forum

The problem states a<=b<=c. Is GCD(a,a) considered to be equal to 1 when a is prime?

Also, I wonder if the answer for a smaller limit could be posted as an algorithm check.

(Link to problem added by moderator: Problem 276 (View Problem))

GCD(x,x)=x always (irrespective of whether x is prime or not)

Is the GCD function a Greatest Common Denominator, or is it some other function that I should know but cannot think of now? Thanks for the help.

-S

It is the greatest common divisor.
See: http://en.wikipedia.org/wiki/Greatest_common_divisor

If I understand the problem right, we don't have to consider the rule a²+b²=c².

So a=1, b=1000, c=1000 for example is a valid triangle?
And a=2, b=1000, c=1000 for example is a invalid triangle?

Thanks for the help!

That rule applies only to right-angle triangles. Problem 276 (View Problem) poses no such restriction.
Yes and yes (for the last two questions).

From the above, it seems that GCD(a,b,c)=1 is not the same as GCD(a,b)=1 AND GCD(b,c)=1

No, it is not. The dotted line below gcd(a,b,c) in the problem description, means a tooltip explanation. Hovering your mouse over it, you'll see: Good luck!

If I understood the problem correctly, each side has to be a prime so gcd(a,b,c)=1 ist true, right?
So isn't this assumption wrong?

jvdmeer wrote:So a=1, b=1000, c=1000 for example is a valid triangle?
And a=2, b=1000, c=1000 for example is a invalid triangle?

MacPr1mE wrote:If I understood the problem correctly, each side has to be a prime so gcd(a,b,c)=1 ist true, right?

No wrong.
Consider gcd(25,49).
25 and 49 have no common factor, so gcd(25,49)=1.
Neither 25 nor 49 is prime.
gcd(a,b,c) should return the gratest common factor of a, b and c.
So gcd(14,21,35)=7, because 14=2*7, 21=3*7 and 35=5*7
But gcd(14,21,36)=1 because 14, 21 and 36 have no common factor.

Just a algorythm-check:

For a max perimeter [le] 100, I get an answer of 6067 triangles with a gcd(a,b,c)=1
For a max perimeter [le] 1000, I get an answer of 5865423 triangles with a gcd(a,b,c)=1

Can someone check this?

jvdmeer wrote:Just a algorythm-check:

For a max perimeter [le] 100, I get an answer of 6067 triangles with a gcd(a,b,c)=1

Can someone check this?

I haven't solved the problem, but my algo gives me 6033 such triangles. Also, for p[le]1000, I get 5803431. I would appreciate some feedback.

Lord_Farin wrote:I haven't solved the problem, but my algo gives me 6033 such triangles. Also, for p[le]1000, I get 5803431. I would appreciate some feedback.

Both values are ok - and both values can easily be brute forced.

AHahahaha ... hah .. errr.

I got 23384 for p <= 100 and 23137742 for p <= 1000.
No wonder I am stuck with this

I am surprised to see, that my solution with the primitive triangles does not fit. I applied the Pythagoras-algorithm and counted the trivial ones. I do not understand from the description where is the misconcept. Reading here I get the idea that non-right-triangles might work as well. Are there samples for the triangles which might fit as well? At least one additional sample on the page would have been beneficial.

martina_qu wrote:I am surprised to see, that my solution with the primitive triangles does not fit. I applied the Pythagoras-algorithm and counted the trivial ones. I do not understand from the description where is the misconcept. Reading here I get the idea that non-right-triangles might work as well. Are there samples for the triangles which might fit as well? At least one additional sample on the page would have been beneficial.

primitive integer sided triangles example #1: a=1, b=1, c=1
primitive integer sided triangles example #2: a=6, b=10, c=15

Sorry, but now I completely off the track. Under triangle I understand a geometric figure with three different corners `which are located anywhere in a (x,y) coordinate-system. And the distance between the so called corners is named length and they are individually named by a,b,c. Additionally the name tri-angle refers to the fact of a geometric figure enclosing 3 angles.

The sample with a=1, b=1, c=1 cannot be constructed unless it is a straight line. But then it fails to have 3 different edges. And therefore cannot be called triangle.
And the sample with 6,10,15 can also not be constructed geometrically as a triangle.

So, what is it, that you call triangle?

Here is a triangle where all three sides are the same length. Let this length be 1. Then you have a triangle with a=b=c=1.

Thx for the picture As it says, one pic says more then 1000 words. May I suggest to update the question in that sense, that you provide at least the information you have posted here? i.e. the two tuples (1,1,1) [+pic?] and (6,5,10) cause the first is so trivial one might skip it as well as there exists no right-corners triangles as well. Perhaps you could also add the triple (6,6,11).

I am aware that these information might not get into the direction of solution but would help to have a clear understanding what might be requested and which thinking-lapsus could be avoided. At least this would have helped me a lot.

Why shoudn't there exist right corner triangles?
Take for instance the triangle (3,4,5).
I think you have to update your notion what a triangle is.
Here's a page to begin with Wikipedia