## Problem 276

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
kvom
Posts: 13
Joined: Tue Oct 02, 2007 11:06 pm
Location: Georgia, USA

### Problem 276

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.

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

### Re: Problem 276

GCD(x,x)=x always (irrespective of whether x is prime or not)
SynK
Posts: 1
Joined: Wed May 20, 2009 6:19 am

### Re: Problem 276

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
hk
Posts: 10993
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 276

It is the greatest common divisor.
See: http://en.wikipedia.org/wiki/Greatest_common_divisor jvdmeer
Posts: 2
Joined: Mon Jan 25, 2010 10:43 pm
Location: Zoeterneer, Netherlands

### Re: Problem 276

If I understand the problem right, we don't have to consider the rule a2+b2=c2.

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!
harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

### Re: Problem 276

That rule applies only to right-angle triangles. Problem 276 (View Problem) poses no such restriction.
Yes and yes (for the last two questions).
kvom
Posts: 13
Joined: Tue Oct 02, 2007 11:06 pm
Location: Georgia, USA

### Re: Problem 276

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
harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

### Re: Problem 276

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: p276.gif (3.64 KiB) Viewed 7349 times
Good luck!
MacPr1mE
Posts: 10
Joined: Tue Dec 29, 2009 1:45 pm
Location: Germany

### Re: Problem 276

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?
hk
Posts: 10993
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 276

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. jvdmeer
Posts: 2
Joined: Mon Jan 25, 2010 10:43 pm
Location: Zoeterneer, Netherlands

### Re: Problem 276

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?
Last edited by jvdmeer on Thu Feb 04, 2010 1:59 pm, edited 1 time in total.
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

### Re: Problem 276

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. ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 8:41 am
Location: Berlin, Germany

### Re: Problem 276

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.
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

### Re: Problem 276

AHahahaha ... hah .. errr.

I got 23384 for p <= 100 and 23137742 for p <= 1000.
No wonder I am stuck with this  martina_qu
Posts: 5
Joined: Wed Feb 05, 2014 7:59 pm

### Re: Problem 276

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. mpiotte
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm

### Re: Problem 276

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 martina_qu
Posts: 5
Joined: Wed Feb 05, 2014 7:59 pm

### Re: Problem 276

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?
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

### Re: Problem 276 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.
martina_qu
Posts: 5
Joined: Wed Feb 05, 2014 7:59 pm

### Re: Problem 276

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.
hk 