Maths Metagolf Mania!

Question

Mathemania Specs:

Every piece of Mathemania code starts off with the number 2. From the 2, you can do the following operations:

• e: Exponentiation. This command's default is squaring the number.
• f: Factorial. This command's default is using the single factorial on the number (using f on 2 = 2! = 2).
• r: Root. This command's default is square-rooting the number.
• c: Ceiling function.
• l: Floor function.

To generate a number in Mathemania, you must string together these commands, which are performed left-to-right on the number 2.

Examples:

ef = (2^2)! = 4! = 24
rl = floor(sqrt(2)) = floor(1.4...) = 1
er = sqrt(2^2) = sqrt(4) = 2
efrrc = ceil(sqrt(sqrt((2^2)!)))
      = ceil(sqrt(sqrt(24)))
      = ceil(sqrt(4.89...))
      = ceil(2.21...)
      = 3

The e, f and r commands can be altered by extra Mathemania commands (which also start off with 2 as its "base" number) to generate different exponentiations, factorials and roots by placing brackets after the altered function and placing the Mathemania commands inside it.

For example, to cube a number instead of squaring it, you can put the command for 3 after e like so:

e(efrrc) -> cube a number, "efrrc" = 3

NOTE: for our purpose, the factorial command (f) start off with 2 as a single factorial. So if you do f(efrrc), that will get evaluated to a double factorial, not a triple factorial.

For n-factorials (e.g. double factorials = 2-factorial, triple factorial = 3-factorial etc.), the base number is multiplied by the number that is n less than it, and n less than that, and so on until the final number cannot be subtracted by n without becoming 0 or negative.

For example:

7!! = 7 * 5 * 3 * 1 = 105 (repeatedly subtract 2, 1 is the last term as
                           1 - 2 = -1, which is negative)
9!!! = 9 * 6 * 3 = 162 (repeatedly subtract 3, 3 is the last term as
                        3 - 3 = 0, which is 0)

For more information, see here.

You can insert it anywhere, and it will get treated by Mathemania as a single function:

e(efrrc)rc = ceil(sqrt(2^3))
           = ceil(2.82...)
           = 3

You're also allowed to nest these inside one another:

e(e(e)) = e(4th power)
        = (2^4)th power
        = 16th power

For an interpreter of Mathemania code, click here (cheers, @BradGilbertb2gills!)

Task:

Your task is to create a program that, when given a positive integer n as input, generates a Mathemania program that when executed, returns n.

However, the Mathemania programs that you generate must be as small (golfed) as possible, and your final score is determined by the sum of the number of bytes in the generated Mathemania programs of the sample, which are the integers 10,000 to 10,100. The lowest score wins.

Rules and specs:

• Your program must output a valid Mathemania program for any positive integer, but only the numbers between 10,000 and 10,100 will be tested.
• You are not allowed to output Mathemania programs that do not result in an integer. If you do so, your program is disqualified.
• For the commands e, f and r, the Mathemania code inside those functions (e.g. e(efrrc), where the efrrc is the code inside the function) must evaluate to a positive integer above 2. If your program doesn't follow this rule, it is disqualified as well.
• Your program must return a Mathemania program for any one of the 101 test integers in at most 30 minutes on a modern laptop.
• Your program must return the same solution for any integer every time it is run. For example, when a program is given an input 5 and it outputs efrc, it must output that every time the input 5 is given.
• You may not hard-code any solutions for any positive integer.
• In order to fully maximise golfing potential in your output, your program should be able to handle arbitrarily large integers. It is not a requirement, though good luck if your language doesn't support this.

This is metagolf, so lowest score wins!

Answer 1

Python 3.5, Score of ??

As of now I don't have the output for all 101 inputs, but once I run the program for all the test cases I will update with my score.

from math import *

memoized = {}
same = {}

def _(mathmania, n):
    memoized[n] = mathmania
    return mathmania

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    for divisor in range(3, int(sqrt(n)) + 1, 2):
        if n % divisor == 0:
            return False
    return True

def pair_key(pair):
    low, high = pair
    diff = high - low
    if diff == 0:
        return 100
    low_done, high_done, diff_done = low in memoized, high in memoized, diff in memoized
    if high_done and memoized[high] == None or low_done and memoized[low] == None:
        return -1
    return (high_done + diff_done + (diff + 1 == low)) * 33 + low / high

def major_pairs(n):
    for i in range(n, int(sqrt(n)), -1):
        d = n / i
        if i - d < d - 1:
            break
        if d == int(d):
            yield (int(d), i)

def fact_key(pair):
    i, f = pair
    if i in memoized:
        if memoized[i] == None:
            return -1
        return 1
    return i / f

def near_fact(n, level):
    s = 4
    if n in same:
        s = same[n]
    for i in range(s, n ** 2 ** level):
        f = factorial(i)
        if f > (n - 1) ** 2 ** level:
            if f < (n + 1) ** 2 ** level:
                same[n] = i
                yield (i, f)
            else:
                return

def generate_mathmania(n):
    if n in memoized and memoized[n] != None:
        return memoized[n]
    memoized[n] = None
    binx = log(n, 2)
    if binx == int(binx):
        if binx == 2:
            return _("e", n)
        if binx == 1:
            return _("er", n)
        if binx == 0:
            return _("rl", n)
        return _("e(" + generate_mathmania(int(binx)) + ")", n)
    sq = sqrt(n)
    if sq == int(sq):
        return _(generate_mathmania(int(sq)) + "e", n)
    low, high = max(major_pairs(n), key=pair_key)
    if pair_key((low, high)) == -1:
        level = 1
        while True:
            try:
                i, f = max(near_fact(n, level), key=fact_key)
            except:
                level += 1
                continue
            if fact_key((i, f)) == -1:
                return _(generate_mathmania((n - 1) ** 2 + 1) + "rc", n)
            if f == n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level, n)
            if f < n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level + "c", n)
            return _(generate_mathmania(i) + "f" + "r" * level + "l", n)
    if low != 1:
        if low == high:
            return _(generate_mathmania(low) + "e", n)
        if high - low == 1:
            return _(generate_mathmania(high) + "f", n)
        return _(generate_mathmania(high) + "f(" + generate_mathmania(high - low + 1) + ")", n)
    good = None
    for i in range(n ** 2 - 1, (n - 1) ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rc", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rc", n)
    for i in range((n + 1) ** 2 - 1, n ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rl", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rl", n)
    return _(generate_mathmania((n - 1) ** 2 + 1), n)

Additionally, I was unable to verify the outputs of some of the test cases I tried due to sheer number size, and at that point @BradGilbertb2gills's online interpreter times out. Hopefully all the outputs work.