Problem 146

completed January 23, 2021

Comments

Hmmm, I didn’t like this one as much. Probably because I never got to a solution that completed in a reasonable amount of time. This one took a few hours to run unfortunately. I believe I did what I could do to speed things up, with checking for the modulos of different numbers and whatnot. Looking at the forums after completing the problem, I see that others focused on the efficiency of their primality tests, some centering around prime probability tests like Miller-Rabin. This test is suppose to be quick and will tell you if the number is probably prime. Meaning that if it is probably prime, the next step would be to check if it actually is prime or not.

Code

def isprimefactory(top):
    sieve = [True] * (top + 1)
    primes = []
    for p, isprime in enumerate(sieve):
        if not isprime or p < 2:
            continue
        primes.append(p)
        num = p + p
        while num <= top:
            sieve[num] = False
            num += p

    def _isprime(n):
        top = n**0.5
        for p in primes:
            if p > top:
                return True
            if n % p == 0:
                return False
        return True

    return _isprime

primes = (27, 13, 9, 7, 3, 1)
composites = (5, 11, 15, 17, 19, 21, 23, 25)
mod11s = (1, 3, 5)

def solve(n):
    isprime = isprimefactory(n + 6)
    total = 0
    for k in range(10, n, 10):  # assumption: k is div by 10
        if k > 10 and k % 7 != 4:
            continue
        k2 = k**2
        if k2 % 210 != 100:
            continue
        if k2 % 11 not in mod11s:
            continue
        for p in primes:
            if not isprime(k2 + p):
                break
        else:
            for c in composites:
                if isprime(k2 + c):
                    break
            else:
                total += k
    return total

if __name__ == '__main__':
    import sys
    n = eval(sys.argv[1])
    print(solve(n))

Tests

import pytest
from problem import solve

_test_solve = (
        (11, 10),
        (10**6, 1242490),
        #(10**7, 11914460),
)

@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
    assert expect == solve(n)