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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
kvom
Posts: 13
Joined: Tue Oct 02, 2007 11:06 pm
Location: Georgia, USA

Problem 276

Post by kvom »

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

Re: Problem 276

Post by harryh »

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

Post by SynK »

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

Re: Problem 276

Post by hk »

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

Re: Problem 276

Post by jvdmeer »

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

Post by harryh »

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

Post by kvom »

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

Post by harryh »

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

Post by MacPr1mE »

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

Re: Problem 276

Post by hk »

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

Re: Problem 276

Post by jvdmeer »

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.
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Problem 276

Post by Lord_Farin »

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

Re: Problem 276

Post by ThomasH »

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

Re: Problem 276

Post by Jochen_P »

AHahahaha ... hah .. errr.

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

Re: Problem 276

Post by martina_qu »

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. :?
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 276

Post by mpiotte »

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

Re: Problem 276

Post by martina_qu »

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

Post by TripleM »

Image

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

Post by martina_qu »

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

Re: Problem 276

Post by hk »

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
Image
Post Reply