Back to index.

The problem: https://projecteuler.net/problem=46

I guess the trick here is to figure out the right way to do the looping. The idea is that if you pick a positive integer $a$ (this plays the role of our composite odd number), then as we increase $q$ (this is the basis for our square) from 1 and on, $a - 2q^2$ dictates the value for the prime we're looking for and quickly becomes negative (for $a$ fixed and $q$ increasing).

We'll maintain a running store of primes found so far. That will help us do the looping.

So, the most interesting thing here is the looping pattern in which we keep increasing the amount of primes we know and we also use that as a source of odd composite numbers.

As an interesting optimization, for another day, we don't really need to keep a list of all the primes we've seen so far. We, in a sense, only have to keep two consecutive primes and update them as the looping happens.

primes_so_far = []
looked_for_primes_up_to = 1

def is_prime(n):
    if n <= 1:
        return False
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def update_primes(look_at):
    global looked_for_primes_up_to
    if look_at <= looked_for_primes_up_to:
        return
    for n in range(looked_for_primes_up_to, look_at+1):
        if is_prime(n):
            primes_so_far.append(n)
    looked_for_primes_up_to = look_at

def all_composite_odds():
    update_primes(looked_for_primes_up_to*2 + 100)
    i = 9
    j = 0
    while True:
        while j < len(primes_so_far) and primes_so_far[j] < i:
            j += 1
        if j == len(primes_so_far) or primes_so_far[j] > i:
            yield i
        i += 2
        if looked_for_primes_up_to < i:
            update_primes(looked_for_primes_up_to*2)

def integer_sqrt(n):
    if n < 0:
        return -1
    if n == 1 or n == 0:
        return n
    lo = 1
    hi = n
    while lo <= hi:
        mid = (hi+lo)//2
        square = mid*mid
        if square == n:
            return mid
        elif square > n:
            hi = mid-1
        else:
            lo = mid+1
    return -1
            
def solve_it():
    for a in all_composite_odds():
        found = True
        for p in primes_so_far:
            d = a - p
            if d <= 0:
                continue
            q = integer_sqrt(d//2)
            if q > 0:
                found = False
        if found:
            return a

print(solve_it())

5777