Skip to main content

Euler 0012

The Problem:

FindWhat is the greatest productvalue of 4the adjacentfirst numberstriangle innumber to have over five hundred divisors?

Considerations:

We don't actually need to compute all of the griddivisors (of a number, since the number of divisors can be calculated by knowing the number of prime factors.

12, for example, has prime factors 2(2 of these) and 3. It has a total of 6 divisors, which can be foundcalculated onby taking the PEquantity website)of each prime factor and adding 1, 2 for 2 becomes 3 and 1 for 3 becomes 2...
ThisOk, maybe that's an obtuse way of explaining it... If you want a good explanation of it, you can befind up,it down,here: left, right, or diagonal.https://mathschallenge.net/library/number/number_of_divisors

Considerations:

  • We don't need to check left ever. In the last 3 columns we don't check right, either. 
  • We don't need to check up ever. In the last 3 rows we don't check down.
  • We don't need to check up diagonals. We will check both left and right diagonals, and ignore the relevant diagonals when we are in the first or last 3 columns. We don't need to check diagonals in the last 3 rows.

The Approach:

StartingWe fromare 0,0going beingto use the topmostsame leftmostprime cornerfactors finder that we have before, but instead of the grid, we canare keepgoing iteratingto throughmultiple andby checkinga everyrunning case,divisors remembering the considerations above.count.

The Code:

import numpymath

from#This enumis importa Enummodification classof Direction(Enum)the prime factor finder
def calculate_divisors(number):
    #notupper_limit necessary= number
    current_upper_limit = upper_limit
    sqrt_limit = math.sqrt(upper_limit)
    current_divisors = 1 

    #we are going to thehardcode solution,2 butand helps3 mefor aslooping asake
    humanif visualizeupper_limit where% the2 solution== is0:
        at
    DOWNcurrent_div = "DOWN"1
        RIGHTwhile current_upper_limit % 2 == 0:
            current_upper_limit = "RIGHT"current_upper_limit/2
            LEFT_DIAGcurrent_div += 1
        current_divisors *= current_div
    if upper_limit % 3 == 0:
        current_div = "LEFT_DIAG"1
        RIGHT_DIAGwhile current_upper_limit % 3 == 0:
            current_upper_limit = "RIGHT_DIAG"current_upper_limit/3
            best_indexcurrent_div += 1
        current_divisors *= current_div
    current = [0,0]6

    best_dirwhile current < sqrt_limit:
        #print(prime_factors, current_upper_limit)
        if current_upper_limit % (current - 1) == 0:
            current_div = Direction.DOWN1
            best_productwhile current_upper_limit % (current - 1) == 0:
                current_upper_limit = 0current_upper_limit/(current-1)
                lengthcurrent_div += 1
            current_divisors *= current_div
        if current_upper_limit % (current + 1) == 0:
            current_div = 41
            gridwhile current_upper_limit % (current + 1) == 0:
                current_upper_limit = numpy.genfromtxt("numbers",current_upper_limit/(current+1)
                delimiter="current_div ")+= #using1
            numpycurrent_divisors to*= readcurrent_div
        incurrent the+= file6

    return current_divisors

bailout = 100000 #keep checking up to a gridbailout fornumber

ustriangle = 1
for i in range(len(grid))2,bailout):
    #gotriangle through+= every row in the grid
    for j in range(len(grid[i])): #go through every column in the grid
        #print(i,j)
        #check righti
    if j < len(grid)-(length-1):
            current_prod = 1
            for k in range(length):
                current_prod *= grid[i,j+k]
            if current_prodcalculate_divisors(triangle) >= best_product:500:
        best_index = [i,j]
                best_dir = Direction.RIGHT
                best_product = current_prod

        #check down
        if i < len(grid)-(length-1):
            current_prod = 1
            for k in range(length):
                current_prod *= grid[i+k,j]
            if current_prod >= best_product:
                best_index = [i,j]
                best_dir = Direction.DOWN
                best_product = current_prod

        #check down right
        if i < len(grid)-(length-1) and j < len(grid)-(length-1):
            current_prod = 1
            for k in range(length):
                current_prod *= grid[i+k,j+k]
            if current_prod >= best_product:
                best_index = [i,j]
                best_dir = Direction.RIGHT_DIAG
                best_product = current_prod

        #check down left
        if i < len(grid)-(length-1) and j > (length-1):
            current_prod = 1
            for k in range(length):
                current_prod *= grid[i+k,j-k]
            if current_prod >= best_product:
                best_index = [i,j]
                best_dir = Direction.LEFT_DIAG
                best_product = current_prodbreak
        
print(best_index,i, best_dir, best_product) #prints out the best position, the direction it points, and the producttriangle)
Back to top