Problem 214

Comments

I do not understand why this one is marked as 40% difficulty, because it felt waaaaaay easier to me than even some of the 20% ones. Mayb though it is because I’ve been doing a lot of totient problems recently and I feel like I have a good handle of it.

I started out by grabbing the code snippet I’d saved for Euler’s totient. The only other thing to do after that was create a function that recursively calls this totient function and return how deap the recursion was.

The test passed so I figured I might as well try it with the I was suppose to input for the solution. I wanted to see just how slow it would be and what I was “going to be up against” in a way. And then it just finished. And then I just entered the answer into the form. And that was it.

There’s gotta be things that can be improved in here though I think this is the minimal complexity solution. After submitting I figured I might as well try to make some of these improvements. That’s when I figured out that this is the most efficient solution.

Update

I was wrong, this can get faster. When creating the primes, once you have processsed all the primes less than or equal to the square root of n, you don’t need to do the while loop at all. That change reduces the total time from about 22 seconds to about 18 seconds.

Code

def memoize(fn):
    _cache = {}
    def wrap(n):
        if n in _cache:
            return _cache[n]
        ret = fn(n)
        _cache[n] = ret
        return ret
    return wrap

def solve(n, l):
    sieve = {}
    primes = []
    for p in range(2, n + 1):
        if sieve.get(p):
            continue
        primes.append(p)
        num = p + p
        while num <= n:
            sieve[num] = p
            num += p

    @memoize
    def totient(n):
        if n == 1:
            return 1
        p = sieve.get(n)
        if not p:
            return n - 1
        n //= p
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        return p**e * (p - 1) * totient(n)

    @memoize
    def chain(n):
        if n == 1:
            return 1
        t = totient(n)
        return 1 + chain(t)

    total = 0
    for p in primes:
        if chain(p) == l:
            total += p

    return total

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

Tests

import pytest
from problem import solve

_test_solve = (
        (20, 4, 12),
)

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