Problem 659

p659.py

def compute(limit):
    f = [int(4*(x**2)+1) for x in range(limit+1)] #Initialise the list f 
    max_prime_factor = [0]*(limit+1) #Initialise the list max_prime_factor
    for x in range(1,len(f)): #Go through f
        div = f[x] #Initialise divisor
        if div > 1: #Check if divisor > 1
            curr1 = x % div
            while curr1 <= limit: #while curr = x + k*f[x] < limit we continue
                if f[curr1] % div == 0: #Check if f[x+k*f[x]] is divisible by f[x]
                    max_prime_factor[curr1] = max(max_prime_factor[curr1], div)
                    #Assign max_prime_factor
                    while f[curr1] % div == 0:
                        f[curr1] //= div #Keep dividing f[x+k*f[x]] by f[x]
                curr1 += div #This is a way to keep increasing "k"
            
            #Same as above
            curr2 = -x % div
            while curr2 <= limit:
                if f[curr2] % div == 0:
                    max_prime_factor[curr2] = max(max_prime_factor[curr2], div)
                    while f[curr2] % div == 0:
                        f[curr2] //= div
                curr2 += div
    return sum(max_prime_factor) % 10**18 #Return the sum of max_prime_factor and mod 10^18 at the end