For this one I just used a sieve to find the divisors of all numbers less than n. The solution will be just like the normal equation for binomeal coefficients but replace multiplication with addition and division with subtraction. Runs in about 2.7 seconds.
def solve(n, k):
sieve = [0] * (n + 1)
for p, iscom in enumerate(sieve):
if iscom or p < 2:
continue
num = p
while num <= n:
m = num // p
e = 1
while m % p == 0:
m //= p
e += 1
sieve[num] += p * e
num += p
total = 0
for l in range(n - k + 1, n + 1):
total += sieve[l]
for l in range(1, k + 1):
total -= sieve[l]
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
k = eval(sys.argv[2])
print(solve(n, k))
import pytest
from problem import solve
_test_solve = (
(10, 0, 0),
(10, 1, 7),
(10, 2, 11),
(10, 3, 14),
(10, 4, 17),
(10, 5, 17),
(10, 6, 17),
(10, 7, 14),
(10, 8, 11),
(10, 9, 7),
(10, 10, 0),
(100, 0, 0),
(100, 1, 14),
(100, 2, 29),
(100, 3, 42),
(100, 4, 135),
(100, 5, 143),
(100, 6, 162),
(100, 7, 204),
(100, 8, 232),
(100, 9, 253),
(100, 10, 266),
(100, 11, 268),
(100, 12, 350),
(100, 13, 354),
(100, 14, 377),
(100, 15, 414),
)
@pytest.mark.parametrize('n,k,expect', _test_solve)
def test_solve(n, k, expect):
assert expect == solve(n, k)