Python Solution for project euler's ex 94

Question

Note: This is a revised version of a post I made some days ago that was closed due to incompleteness. I have now done my best to optimise it, and it should now be a minimal reproducible example.

The question:

"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)."

The answer to the problem is 518408346.

My result is much larger than this number. How come? After looking through the comments on the previous post prior to its suspension, I believe that it is due to a floating-point error.

I assume that my code generates numbers that are border-line integers which Python falsely takes for integers. That would explain why my result is much larger than the correct. I have observed that python does this when the number of leading zeros after the decimal point exceed 15 (e.g., 3.0000000000000005 is taken as 3.0000000000000005 whereas 3.(>15x 0) is taken as 3.0. If there was a way to change this setting, my method could work. Do you agree? I have thought that the module, decimal, could prove useful here, but I am not sure how to utilize it for this purpose.

This is my code:

sum_of_p=0


for i in range(2,333333334):

    if i%(5*10**6)==0:
        print(i)
    
    h=(i**2-((i+1)*0.5)**2)**0.5
    if int(h)==h:
        a=0.5*(i+1)*h
        if int(a)==a:
            sum_of_p+=3*i+1
        

    h=(i**2-((i-1)*0.5)**2)**0.5
    if int(h)==h:
        a=0.5*(i-1)*h
        if int(a)==a:
            sum_of_p+=3*i-1



print(sum_of_p)

Answer 1

I assume that using floats is not a good idea for integer values problem. Here is solution that I have found. If your version or python is below 3.8, then you will have to use more slow is_square_ function

import math

def is_square_(apositiveint):
# Taken from: 
# https://stackoverflow.com/questions/2489435/check-if-a-number-is-a-perfect-square
    x = apositiveint // 2
    seen = set([x])
    while x * x != apositiveint:
        x = (x + (apositiveint // x)) // 2
        if x in seen: return False
        seen.add(x)
    return True

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

def check(a, b, c):
    """ return preimeter if area of triangle with sides of lengts a,b,c is integer """
    perimeter = a + b + c
    if perimeter % 2 == 1:
        # preimeter should be even
        return 0
    p = perimeter // 2
    # Use Heron's formula
    H = p*(p-a)*(p-b)*(p-c)
    if is_square(H):
        return perimeter
    return 0


sum_of_p = 0
max_i = 1000000000 // 3
for i in range(2, max_i + 1):

    if i % (10**5) == 0:
        print(i*100 / max_i )
    

    sum_of_p += check(i, i, i+1)
    sum_of_p += check(i, i, i-1)

print(sum_of_p)