Problem 757

completed November 16, 2021

Comments

I chose this problem to work on next because it was listed as only 10% difficulty. I figured I could do it in an evening.

I used my normal process. Create a brute force solution, write some tests, then optimize. I also went to OEIS to help me find a pattern.

Runs a little slower than I’d like, but works none the less. Takes about 30 seconds in pypy3.

Code

def solve(n):
    stealths = {}
    top = int((n//2) ** 0.5) + 1
    for a in range(1, top):
        A = a * (a + 1)
        for b in range(1, a + 1):
            N = A * b * (b + 1)
            if N > n:
                break
            stealths[N] = True
    return len(stealths)

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

Tests

import pytest
from problem import solve

_test_solve = (
        (10**1, 1),
        (10**2, 8),
        (10**3, 39),
        (10**4, 174),
        (10**5, 720),
        (10**6, 2851),
)

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