After completing problem 679, this one felt like a breeze. I did my normal process of implementing a brute force algorithm, writing some tests, and then iterating from there. I started by printing out the values for F(n) and quickly saw that there was a pattern to them. I figured out the pattern, noting that they are the values from https://oeis.org/A119387, and then write it in code. Because the algorithm took several steps, I wrote out the comments first and was sure to give the variables clear names.
Gets the solution in under a second. In fact, can even calculate the value for 10**100 in less than a second! The only thing keeping this puppy from going any larger is python’s recursion limit.
import math
def solve_by_power(k):
# the n will be (2**e - 1)
last = 0
total = 0
for e in range(1, k+1):
this = int((e-1)*2**(e-2)) + last
total += this
last = this
return total
_solve = {0: 0, 1: 0}
def solve(n):
if n in _solve:
return _solve[n]
# total to nearest power of 2
nearest_power_of_2 = int(math.log(n, 2))
total = solve_by_power(nearest_power_of_2)
# figure out how many numbers are left total
total_num_left = n - 2**nearest_power_of_2 + 1
# figure out how many numbers are left from previous
num_from_prev = total_num_left // 2
further_power_of_2 = 2 ** (nearest_power_of_2 - 1) - 1
total += solve(further_power_of_2 + num_from_prev) - solve(further_power_of_2)
# get the alternator number
total += nearest_power_of_2 * (total_num_left - num_from_prev)
_solve[n] = total
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(10**1, 14),
(10**2, 389),
(10**3, 7002),
(10**4, 103649),
(10**5, 1368968),
(10**6, 16951471),
(10**7, 203222840),
(10**8, 2365782338),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)