# OEIS A186736
# Matthew Ready, Oct 5th 2024

def is_prime(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True


def primes_less_than_or_equal_to_n(n):
    return [i for i in range(2, n + 1) if is_prime(i)]


def a186736(n):
    # Precalculate a list of primes less than or equal to n
    primes = primes_less_than_or_equal_to_n(n)

    # Preallocate a list of at least [len(primes)] elements to store the current working subset.
    current_set = [0] * len(primes)

    # Tracks the best currently known subset.
    best_sum = 0
    best_set = []

    # Given a 'current set' in current_set[0:current_set_length] consisting only of relatively coprime numbers with
    # prime factors prime[i+1:], and a 'current sum' representing the sum of the numbers in this set, find the maximum
    # possible sum that can be achieved by either:
    #  - Adding prime[i] ** x (for some x) to the current_set
    #  - Multiplying a value in current_set by prime[i] ** x.
    def recurse(i, current_set_length, current_sum):
        # Allow this closure to mutate [best_sum] and [best_set]
        nonlocal best_sum, best_set

        # If i is less than 0, there are no more primes. Update the best known sum if we've done better.
        if i < 0:
            if current_sum > best_sum:
                best_sum = current_sum
                best_set = current_set[:current_set_length]
            return

        # Tree pruning heuristic: The best we can increase the current score by is at the absolute most is n * (i + 1),
        # since we have only (i+1) primes left to check, and each prime can (at most) add [n] to the score.
        if current_sum + n * (i + 1) < best_sum:
            return

        this_prime = primes[i]

        # For all powers of this prime ("powered") <= n:
        powered = this_prime
        while powered <= n:
            # Try extending the current set with "powered" and recursing to the next smaller prime.
            current_set[current_set_length] = powered
            recurse(i - 1, current_set_length + 1, current_sum + powered)

            # Look over the current set and see if there's a number that we can multiply by "powered" and still keep it
            # less than or equal to n.
            for current_num_idx in range(current_set_length):
                current_num = current_set[current_num_idx]
                if current_num * powered <= n:
                    # If we find one, multiply it out and recurse to the next prime with the updated set.
                    current_set[current_num_idx] = current_num * powered
                    recurse(i - 1, current_set_length, current_sum - current_num + current_num * powered)

                    # Restore the set to the way that it was ready for the next recursion.
                    current_set[current_num_idx] = current_num

            powered *= this_prime

    recurse(len(primes) - 1, 0, 0)

    return best_sum + 1


with open("b186736.txt", "w") as f:
    for i in range(1, 5001):
        f.write(f"{i} {a186736(i)}\n")