// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 4.20 out of 5)
Loading...

Project Euler Solutions

Project Euler 94 Solution

Project Euler 94 Solution

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.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 94 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 94 Solution Python 2.7 source.

Afterthoughts

  • Area of the isosceles triangle calculated as:
     A = \frac{1}{2}\>a^2\sqrt{\frac{b^2}{a^2}-\frac{1}{4}}

  • 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
Project Euler 94 Solution last updated

Discussion

4 Responses to “Project Euler 94 Solution”

  1. Thank you for your response. It was a precision issue as you suspect.

    Posted by Henri | November 8, 2016, 4:59 AM
  2. Good 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 AM
  3. How exactly did you manage to get the formula for the variable side?

    Posted by Aljaž | August 22, 2015, 11:30 AM

Post a comment