CODEWITHSUNDEEP
pythonalgorithmmath
RedBanana
RedBanana

Reputation: 25

What makes this code so slow? (for project Euler q45)

I just solved and found the answer for problem 45 on project euler, however the solution took twenty minutes to compute. Other similar solutions take less than a second to find the solution.

The problem

My code:

import time

def is_triangular(n):

    triangle_index = (((8 * n + 1) ** 0.5) + 1) / 2
    if triangle_index % 1 == 0:
        return True
    return False

def is_pentagonal(n):

    pentagonal_index = (((24 * n  + 1) ** 0.5) + 1) / 6
    if pentagonal_index % 1 == 0:
        return True
    return False

def is_hexagonal(n):
    hexagonal_index = (((8 * n + 1) ** 0.5) + 1) / 4
    if hexagonal_index % 1 == 0:
        return True
   return False


number = 40756
while True:
    if is_triangular(number) and is_pentagonal(number) and is_hexagonal(number):
        print(number)
        break

    number += 1

Upvotes: 0

Views: 144

Answers (2)

dteod
dteod

Reputation: 331

Because you are looking to every natural number after 40755. Limit the case to a subset of real numbers: if you know already that a number is not hexagonal you can discard it already, for example.

Since the hexagonals are in the less dense subset, start by looking to numbers in that set. Then, check if they're pentagonals, and eventually check if those are triangular too.

main function example:

hex = 144
while True:
    number = hex*(2*hex-1)
    if is_hexagonal(number):
        if is_pentagonal(number):
            if is_triangular(number):
                print("Found: {}".format(number))
                break
    hex += 1

There are other modifications that can be done in the Python code, but I focused on the algorithm only.

Upvotes: 1

Flaming_Dorito
Flaming_Dorito

Reputation: 485

Instead of going through every number and checking if its triangular, pentagonal and hexagonal. Generate Hexagonal numbers and for each hexagonal number check if its triangular or pentagonal.

You can generate hexagonal numbers by using the formula for hexagonal numbers and increasing n by 1.

Upvotes: 5

Related Questions