Project Euler - Page 3

Batalov · 2016-06-14, 19:50

Quote:

Originally Posted by henryzz

...However, there needs to be a solution for [3,1,1,1,1] based upon the value for S(5).

You are retracing my steps :-)

Try to solve this particular sub-problem on the table using matchsticks (or Q-tips; 4 "1/3"s and one "1")... and you will see what is going on!

Only if completely stuck, watch this spoiler --> the circle's center _[I]can[/I]_ be outside of the polygon, but the (maximal) polygon is still cyclic!

henryzz · 2016-06-16, 09:06

There are two sizes of angles the angles between sides of length 1 and the two angles between sides of length 1 and 3. All of the vertices are the opposite side of the longest line to the centre of the circle.
Not sure where to go from here. Need to check whether the only problem cases are the ones with a load of 1s and a longer side. If so it should be possible to work it out as a special case(calculate the distance between the endpoints of the curve generated from the sides of length 1 with certain angles and solve for the larger size).

henryzz · 2016-06-16, 15:26

I implemented the special case(one long side and a load of 1s). This wasn't enough. Now stuck with [6,2,1,1,1,1,1,1,1]. There has got to be something I am missing with my standard optimization. My standard optimization presumably assumes that the polygon is facing the other way around.

WMHalsdorf · 2016-06-16, 21:36

Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?

Batalov · 2016-06-16, 23:35

The reordering of sides doesn't matter - ...by a very simple argument

science_man_88 · 2016-06-17, 00:57

Quote:

Originally Posted by science_man_88

as someone who tried to knit a regular pentagon my first thought turns to tan functions of the outer angles or at least saying okay the other side is 3 the rest of them total 4 what average angle can I have. If half go in and got connected together of the 1 segments it's like a 2,2,3 triangle but we want 5 true sides for [2,1,1,1] the first shape I can think of is a rhombus /__\ the outer segments being tilted to be roughly cos(theta)=1/2

you would think I would know a rhombus and a trapezoid aren't the same doh.

henryzz · 2016-06-17, 20:57

I found a paper which includes the method I have been using for solving the majority of cases. http://www.sciencedirect.com/science...22314X07001126
Unfortunately the formula is reliant on the centre of the circle being inside the polygon.

I have not a clue how to go about cases such as [6,2,1,1,1,1,1,1,1] other than increasingly complex optimization problems.
For one large side and a load of 1s I just needed to vary one angle until the length of the long side was correct. For more than one large side there are two angles to vary. This is possible but this solution is not necessarily unique which means it may not be maximal(if it converges given it is not unique). This means I am trying to maximize the area at the same time as solving for side length.
http://mathoverflow.net/questions/35...iate-bisection should hopefully give me the means to do this.
Am I barking up the wrong tree here? Will I have to go beyond 2d optimization for future cases n<=50? I am hoping that there are few enough cases that speed won't be an issue.

Batalov · 2016-09-04, 17:05

Project Euler re-opened after the summer break with two related (moderate) problems: 567 and 568.

Edit (September 10): pe 569 is also easy (brute force, run-time 40 minutes); but may be a bit harder to get run-time under 1 minute...

Blackadder · 2021-01-18, 14:27

I discovered Project Euler only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.

petrw1 · 2021-01-18, 14:31

Quote:

Originally Posted by Blackadder

I discovered Project Euler only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.

They are pretty cool problems.
I did a couple hundred a dozen years ago.

LaurV · 2021-01-19, 04:05

We also did few, at the time. As we remember, for some of them, you don't need a computer, you can just do them with a pencil on paper if you think a bit. On the other hand, some were difficult and we gave up, due to limited time, knowledge, and "guts"...

2016-09-04, 17:05	#30
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×2,333 Posts	Project Euler re-opened after the summer break with two related (moderate) problems: 567 and 568. Edit (September 10): pe 569 is also easy (brute force, run-time 40 minutes); but may be a bit harder to get run-time under 1 minute... Last fiddled with by Batalov on 2016-09-10 at 21:32

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Project Euler 486	lavalamp	Puzzles	8	2015-02-04 14:28
Project Euler #372	lavalamp	Puzzles	165	2012-05-24 16:40
Euler (6,2,5) details.	Death	Math	10	2011-08-03 13:49
Project Euler	Mini-Geek	Lounge	2	2009-10-23 17:19
Bernoulli and Euler numbers (Sam Wagstaff project)	fivemack	Factoring	4	2008-02-24 00:39

2016-06-16, 09:06	#24
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5,821 Posts	There are two sizes of angles the angles between sides of length 1 and the two angles between sides of length 1 and 3. All of the vertices are the opposite side of the longest line to the centre of the circle. Not sure where to go from here. Need to check whether the only problem cases are the ones with a load of 1s and a longer side. If so it should be possible to work it out as a special case(calculate the distance between the endpoints of the curve generated from the sides of length 1 with certain angles and solve for the larger size).

2016-06-16, 15:26	#25
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5,821 Posts	I implemented the special case(one long side and a load of 1s). This wasn't enough. Now stuck with [6,2,1,1,1,1,1,1,1]. There has got to be something I am missing with my standard optimization. My standard optimization presumably assumes that the polygon is facing the other way around.

2016-06-16, 21:36	#26
WMHalsdorf Feb 2005 Bristol, CT 3³×19 Posts	Wouldn't [2,1,2,1,1] for 5 sides produce the largest area since it is closest to a regular pentagon?

2016-06-16, 23:35	#27
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×2,333 Posts	The reordering of sides doesn't matter - ...by a very simple argument

2016-06-17, 20:57	#29
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5821₁₀ Posts	I found a paper which includes the method I have been using for solving the majority of cases. http://www.sciencedirect.com/science...22314X07001126 Unfortunately the formula is reliant on the centre of the circle being inside the polygon. I have not a clue how to go about cases such as [6,2,1,1,1,1,1,1,1] other than increasingly complex optimization problems. For one large side and a load of 1s I just needed to vary one angle until the length of the long side was correct. For more than one large side there are two angles to vary. This is possible but this solution is not necessarily unique which means it may not be maximal(if it converges given it is not unique). This means I am trying to maximize the area at the same time as solving for side length. http://mathoverflow.net/questions/35...iate-bisection should hopefully give me the means to do this. Am I barking up the wrong tree here? Will I have to go beyond 2d optimization for future cases n<=50? I am hoping that there are few enough cases that speed won't be an issue.

2021-01-18, 14:27	#31
Blackadder "Angelino Desmet" Mar 2018 Belgium 2·23 Posts	I discovered Project Euler only recently and decided to take up programming again because of it. Have done the three first problems. This is cool.

2021-01-19, 04:05	#33
LaurV Romulan Interpreter Jun 2011 Thailand 5²×7×53 Posts	We also did few, at the time. As we remember, for some of them, you don't need a computer, you can just do them with a pencil on paper if you think a bit. On the other hand, some were difficult and we gave up, due to limited time, knowledge, and "guts"...