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

Re: Problem 276

Post by martina_qu »

Hm? Does your response has anything to do with my last post?

I have written: one might skip ... as there exists no right-corners triangles as well

And thx for the advice to update my notion what ... I guess, that's due to the fact I made a suggestion to update the problem on the web-site that you suggest as well to update my knowledge. Right? Well, anyway, I don't like that sort of discussion when one makes a suggestion the opposite makes a different one. :? But I suggest, lets stop that kind of talk and get back to what was written and asked for before starting a flame. :shock:
User avatar
hk
Administrator
Posts: 10993
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 276

Post by hk »

martina_qu wrote:Hm? Does your response has anything to do with my last post?

No it hasn't. 8-)
Just rambling away.
Image
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 276

Post by TripleM »

martina_qu wrote: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.
That's what this forum is for :) Not intending to cause any offence in the slightest, but I don't think there'll ever be another occasion where somebody doesn't believe you can form a triangle with three sides of length 1 - having to define what a triangle is in a problem statement would set a bad precedent for the other hundreds of more complicated problems.
martina_qu
Posts: 5
Joined: Wed Feb 05, 2014 7:59 pm

Re: Problem 276

Post by martina_qu »

I agree with what you say, yeah, the sample with 1 is nice - almost tooooo trivial to even think about.

I want to add, that coming directly from Problem 75 I have had the idea all triangles constructed more or less by the Euclids construction. Since the main idea there is to have as well primitive triples I think it might be worth to mention that those primitive triples do not match the primitive triples from 276 - simply cause there exists more triangles. And a simple sample like 6,10,15 or 6,6,11 wont hurt, but would make clear that theses 'primitive' triplets don't match any other... Just a sample like in 75 would be appreciated.

My 2 cents... (since I have seen above that others fall in the same trap of right-triangles ;) )
User avatar
jaap
Posts: 553
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 276

Post by jaap »

martina_qu wrote:I want to add, that coming directly from Problem 75 I have had the idea all triangles constructed more or less by the Euclids construction. Since the main idea there is to have as well primitive triples I think it might be worth to mention that those primitive triples do not match the primitive triples from 276 - simply cause there exists more triangles. And a simple sample like 6,10,15 or 6,6,11 wont hurt, but would make clear that theses 'primitive' triplets don't match any other... Just a sample like in 75 would be appreciated.

My 2 cents... (since I have seen above that others fall in the same trap of right-triangles ;) )
Being primitive or not has very little to do with it. P75 is about right-angled triangles, whereas P276 is not. The definition of primitive is the same in both cases. In fact, the statement of P75 actually doesn't mention primitive, and the concept might not even be needed in its solution at all.

Your mistake was to add extra conditions to the problem that were not stated. I think it is a bit much to clutter up the simple and clear problem statement with examples just to counteract all kinds of unwarranted assumptions people might make.
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 276

Post by Oliver1978 »

I'm having a little problem with this and how I've got to make up the description.

Let's take -10- for the maximum perimeter. In case I treat gcd(a,b,c) like proposed in the description I get these -26- results:

Code: Select all

gcd(a,b,c) = gcd(a, gcd(b,c))
  3 = 1 - 1 - 1
  4 = 1 - 1 - 2
  5 = 1 - 1 - 3
  6 = 1 - 1 - 4
  7 = 1 - 1 - 5
  8 = 1 - 1 - 6
  9 = 1 - 1 - 7
 10 = 1 - 1 - 8
  5 = 1 - 2 - 2
  6 = 1 - 2 - 3
  7 = 1 - 2 - 4
  8 = 1 - 2 - 5
  9 = 1 - 2 - 6
 10 = 1 - 2 - 7
  7 = 1 - 3 - 3
  8 = 1 - 3 - 4
  9 = 1 - 3 - 5
 10 = 1 - 3 - 6
  9 = 1 - 4 - 4
 10 = 1 - 4 - 5
  7 = 2 - 2 - 3
  9 = 2 - 2 - 5
  8 = 2 - 3 - 3
  9 = 2 - 3 - 4
 10 = 2 - 3 - 5
 10 = 3 - 3 - 4
When I change the gcd calculation to "standard" I get -16- results:

Code: Select all

gcd(a,b,c) = gcd(a,b) and gcd(b,c)
  3 = 1 - 1 - 1
  4 = 1 - 1 - 2
  5 = 1 - 1 - 3
  6 = 1 - 1 - 4
  7 = 1 - 1 - 5
  8 = 1 - 1 - 6
  9 = 1 - 1 - 7
 10 = 1 - 1 - 8
  6 = 1 - 2 - 3
  8 = 1 - 2 - 5
 10 = 1 - 2 - 7
  8 = 1 - 3 - 4
  9 = 1 - 3 - 5
 10 = 1 - 4 - 5
  9 = 2 - 3 - 4
 10 = 2 - 3 - 5
Neither way I get 6,033 for p <= 100 :(
49.157.5694.1125
User avatar
jaap
Posts: 553
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 276

Post by jaap »

leghorn wrote:I'm having a little problem with this and how I've got to make up the description.

Let's take -10- for the maximum perimeter. In case I treat gcd(a,b,c) like proposed in the description I get these -26- results:

Code: Select all

gcd(a,b,c) = gcd(a, gcd(b,c))
  3 = 1 - 1 - 1
  4 = 1 - 1 - 2
  5 = 1 - 1 - 3
What would a triangle with sides 1, 1, and 3 look like?
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 276

Post by Oliver1978 »

*edited because of profanity*

Thanks a lot, jaap, for pointing this out!
49.157.5694.1125
SNAIL-ERATO
Posts: 3
Joined: Sat Nov 01, 2014 10:35 pm

Asking for clarification on Problem 276

Post by SNAIL-ERATO »

Do we have to count degenerated triangles like a=1,b=2 and c=3 or not ?
User avatar
sjhillier
Administrator
Posts: 558
Joined: Sun Aug 17, 2014 4:59 pm
Location: Birmingham, UK
Contact:

Re: Asking for clarification on Problem 276

Post by sjhillier »

SNAIL-ERATO wrote: Mon Apr 03, 2017 4:44 pm Do we have to count degenerated triangles like a=1,b=2 and c=3 or not ?
No, a degenerate triangle isn't really a triangle, so don't count them. Explicitly, only count triplets with a+b>c.

Please do try to find first if a forum already exists for your problem before starting a new topic. A simple search on 276 (in this case) should get you there.
SteveB
Posts: 4
Joined: Sun Jun 15, 2014 11:04 pm

Re: Problem 276

Post by SteveB »

So I have been thinking about this problem wayyyy too long.

I think I have done some pretty good stepwise refinement on my algorithm but ran out of things to refine, and still have an estimated 275 day run time to solution (Mathematica is pithy but sometimes very slow).

Am I allowed to ask - can this problem be solved in O(n^2) time or is it sometime better?
User avatar
RobertStanforth
Administrator
Posts: 1403
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 276

Post by RobertStanforth »

SteveB wrote: Fri Oct 20, 2017 6:48 am Am I allowed to ask - can this problem be solved in O(n^2) time or is it sometime better?
Each Project Euler problem can be solved within a minute, on a reasonably powered home computer. That should provide you with an indication of whether a faster algorithm exists.
Post Reply