Yet another pattern finding problem. I followed my same technique of getting a brute force solution, even if it’s slow. Then I create tests and attempt to speed it up from there. My initial implementation allowed me to get the answers to streaks(n). I printed these out the first 1,000,000 values and quickly saw that there was some type of pattern. Plugging the sequence into OEIS, I found https://oeis.org/A055874 which was exactly what I was looking for. It confirmed to me that I was going to need to find numbers that are divisible by a range of numbers starting with one. Once doing that I was able to count the number of values of streak(n) less than the needed value.
def multipliers(n):
mults = {1: 1}
num = adder = 2
for n in range(2, n + 2):
while True:
if num % n != 0:
num += adder
else:
mults[n] = adder = num
break
return mults
def solve(n):
total = 0
mults = multipliers(n)
this = mults[1]
maxim = 1
for k in range(1, n + 1):
that = mults[k+1]
maxim *= 4
total += maxim // this - maxim // that
if k < 3:
total -= 1
this = that
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(1, 1),
(2, 6),
(3, 11),
(4, 28),
(5, 28),
(6, 87),
(7, 107),
(8, 159),
(9, 159),
(10, 538),
(11, 538),
(12, 1097),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)