(6 votes, average: 4.33 out of 5)
Loading...
Project Euler 94: Find the sum of the perimeters for a set of almost equilateral triangles
Project Euler 94 Problem Description
Project Euler 94: It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.
We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.
Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).
Analysis
A good magic trick seems to defy both logic and physics until the secret is revealed. Then your response is something like: “What? That’s it! You just stacked the deck? I can’t believe I fell for that!” But until that point you were truly impressed.
Such are the secrets of these infernal math problems. I usually have few clues knowing where to begin and after some research and study I hack together a few short lines of code and wonder: “How is it I didn’t see that two hours ago?”
Anyway, here’s the solution to this problem of isoscele triangles trying to masquerade as “almost equilaterals.” Resources include Wikipedia’s article Almost-equilateral Heronian triangles, the series Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) : Areas of 'close-to-equilateral' integer triangles, and the table below in the comments section which yields some evidence of a sequence and the recurrence equation wrapped in a Diophantine equation that guarantee integer results.
Adding ±1 to the perimeter guarantees an even area and perimeter as the problem requires.
solves all test cases
on HackerRank
Project Euler 94 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 94 Solution Python 2.7 source.Afterthoughts
- Area of the isosceles triangle calculated as:
- Table of sides, perimeters, p, and areas for p < 109
| Side 1 (a) | Side 2 (a) | Side 3 (b=a±1) | Perimeter | Area |
|---|---|---|---|---|
| 5 | 5 | 6 | 16 | 12 |
| 17 | 17 | 16 | 50 | 120 |
| 65 | 65 | 66 | 196 | 1848 |
| 241 | 241 | 240 | 722 | 25080 |
| 901 | 901 | 902 | 2704 | 351780 |
| 3361 | 3361 | 3360 | 10082 | 4890480 |
| 12545 | 12545 | 12546 | 37636 | 68149872 |
| 46817 | 46817 | 46816 | 140450 | 949077360 |
| 174725 | 174725 | 174726 | 524176 | 13219419708 |
| 652081 | 652081 | 652080 | 1956242 | 184120982760 |
| 2433601 | 2433601 | 2433602 | 7300804 | 2564481115560 |
| 9082321 | 9082321 | 9082320 | 27246962 | 35718589344360 |
| 33895685 | 33895685 | 33895686 | 101687056 | 497495864091732 |
| 126500417 | 126500417 | 126500416 | 379501250 | 6929223155685600 |
Why the parties 100640664 and 100640665 can not be a solution to this problem? The area is 4385787908123430
Posted by Sergey | June 20, 2019, 10:07 PMNo, the area is 4,385,787,908,123,429.7927697417 and not integral. The area must evaluate to an integer.
check out https://keisan.casio.com/exec/system/1223267646 and specify 22 digits of accuracy.
Posted by Mike Molony | June 21, 2019, 12:19 AMThank you for your response. It was a precision issue as you suspect.
Posted by Henri | November 8, 2016, 4:59 AMGood morning,
Could you please tell why the following two cases are not valid cases to add the the list given above:
a=two sides of equal length; b = a+/-1, h = height, A = area and P = perimeter
(i) a = 92604733, b = 92604734, h = 80198051, A = 3713359590086717, P = 277814200
(ii) a = 97145893, b = 97145892, h = 84130811, A = 4086481363925679, P = 291437678
Thank you
Henri
Posted by Henri | October 7, 2016, 3:48 AMYou may have a precision problem as these sides do not yield an integer area.
Check your division and let me know what you find.
Posted by Mike Molony | November 3, 2016, 11:36 PMHow exactly did you manage to get the formula for the variable side?
Posted by Aljaž | August 22, 2015, 11:30 AM