Problem 276

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

[hk]

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

No it hasn't.
Just rambling away.

[TripleM]

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]

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 )

[jaap]

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.

[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

[jaap]

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?

[Oliver1978]

*edited because of profanity*

Thanks a lot, jaap, for pointing this out!

[SNAIL-ERATO]

Do we have to count degenerated triangles like a=1,b=2 and c=3 or not ?

[sjhillier]

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]

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?

[RobertStanforth]

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.

[hamsterofdeath]

i found the corrresponding sequence in oeis, but - how do i read the page? why don't they provide a formula? it's totally cryptic/messy for me

[hamsterofdeath]

i'm 100% stuck on this one. what is the correct keyword i need to google?
there seems to be no pattern i can exploit nor any calculations that are repeated, so caching values won't be useful either.
is it even possible for a standard human to solve this?

[neverforget]

This forum is for clarifying ambiguous or confusing problem statements. It's not the right place to ask for hints, especially for the harder questions. My advice is to tackle easier problems and other problems (outside PE) and really explore different solutions to learn more techniques. This is certainly solvable by a "standard" human, once expose to said techniques.

[yourmaths]

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:

Haha. I did the same, i.e. just as Oliver1978 did, I classified a triangle as a<=b<=c with c > a+b . I developed a method to solve that problem and came here because PE wasn't accepting my clearly correct answer. Luckily I could adapt the method to solve the actual problem.