Brainflak Multiplication Metagolf

Question

This question is the first of several Brain-flak Birthday challenges designed to celebrate Brain-Flak's first Birthday! You can find more information about Brain-Flak's Birthday here

Last summer we had the Brain-flak Integer Metagolf, and the answers it generated have been very useful to the Brain-Flak community since. The main thing that makes the Integer Metagolf so efficient is a technique called Multiplication hardcoding.

In Brain-Flak runtime multiplication is extremely expensive. The shortest known multiplication snippet is:

({}<>)({<({}[()])><>({})<>}{}<><{}>)

Discovered by Megatom

However there is a very simple way to create compile time multiplication. For example the following code will multiply by 5:

 (({})({})({})({}){})

Try it online!

This works because consecutive expressions are added together. Each ({}) does nothing to the stack ({} pops and (..) pushes it right back) and evaluates to whatever is on top of the stack. All these expressions together sum up to five times whatever was on the top of the stack.

For any n the following string expression will make a snippet that will multiply the top of the stack by n:

"("+"({})"*(n-1)+"{})"

This works by making n expressions that all evaluate to the top of the stack. The first n-1 don't actually change anything and the last one removes the top of the stack before the push.

For composite numbers you can chain multiple smaller expressions together to save bytes. For example you can multiply by 25 by multiplying by 5 twice:

(({})({})({})({}){})(({})({})({})({}){})

This is pretty simple, and for some numbers it works pretty well however there are better ways to do this. For example one method I came up with uses the binary representation of the number. (Here is a python implementation) This new method is much more effective than the simple string expression shown earlier, but its not the end, there are all sorts of interesting ways to hardcode multiplication and probably a ton that no one has yet discovered.

So I think it is time to see how good we can get.

Brief Overview of Brain-Flak

Here is a description of everything you will need to know about Brain-Flak for this challenge.

Brain-Flak has "nilads" and "monads". Nilads are parentheses that have nothing inside of them. Each nilad does a thing and returns a value. For this challenge the two nilads we are concerned with are {} and <>. {} pops the top of the active stack and returns its value. <> switches the active stack and the in active stack, so that the active stack becomes inactive and the inactive stack becomes active, it returns zero.

Monads are parentheses with stuff inside them. They take a single argument, the sum of everything inside them, sometimes perform an action, and then return a value. The three of these we are concerned with are (...), <...> and [...]. The most important monad for this challenge (...) takes the value of the inside and pushes it to the active stack. It then returns the argument. <...> and [...] are both "inert" monads, that is they do not perform any action but rather modify the value they are passed. <...> always returns zero regardless of the argument passed. Meanwhile [...] always returns the argument times -1.

---

Sample programs with explanation

If you have never programmed in Brain-Flak it might be a good idea to look at some example programs using the operations described

({}{})

This adds the top two numbers on the stack. Each {} pops a value off of the stack and (...) pushes their sum back.

({}[{}])

Similarly this subtracts the second item on the stack from the first. Like before each {} pops a value but the [..] around the second one causes it to be added. Once again the (...) pushes the sum.

({}<{}>)

This removes the second value on the stack keeping the top value intact. It works just like the last two except the second value is silenced by the <...> so the push only pushes the first value back.

(({}))

This makes a second copy of the value on the top of the stack. It does this by popping the top of the stack with {} getting its value, the first (..) then pushes it back evaluating to its value. The second (...) takes the value returned by the first and pushes that to the stack as well. creating a second copy.

Task

Given an integer n create a stack-clean Brain-Flak snippet that multiplies the top of the current stack by n.

You are permitted to use the following Brain-Flak operations

(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{}    -> Pop nilad, Pops the TOS and returns its value
<>    -> Switch nilad, Switches the active and inactive stack

The other operations are banned for the purpose of the challenge.

Scoring

Your score will be the cumulative lengths of all the programs from n=2 to n=10000. Be sure to include a link to the output of your program for verification.

Answer 1

Ruby, 669856

$answers = Hash.new{|hash,n|
  valid = []
  2.upto(n**0.5){|i|
    valid.push("("+hash[n/i]+")"+"({})"*(i-2)+"{}") if n%i == 0
  }
  valid.push("({})"+hash[n-1])
  (hash[n] = valid.min_by{|s| s.length})
}
$answers[1] = "{}"

def full_answer n
  "("+$answers[n]+")"
end

This is a quick baseline answer. First 1000 min-programs found here. (I tried posting all of them, but that overloaded the max pastebin size.) I may add a code explanation later.

Examples:

360:    ((((((({})(({}){}){})({}){})({}){}){}){}){})
4608:   (((((((((((({})({}){})({}){}){}){}){}){}){}){}){}){}){})
9991:   (({})((({})(((((((({})((({})({}){}){}){}){}){}){}){}){}){}){})({}){}){})