Golf a Brain-Flak Integer

Integers are tedious to represent in Brain-Flak. There are 8 operators:

()      Evaluates to 1, but does not push anything on any stack
[]      Evaluates to an indeterminate value for the purposes of this question
{}      Removes the top of the stack and evaluates to it
<>      Switches to or back from the alternate stack and evaluates to zero
(foo)   Pushes the value of the expression foo to the stack and evaluates to it
[foo]   Evaluates to the negation of foo
{foo}   Evaluates the expression foo until the top of the stack is zero
<foo>   Evaluates to zero but executes foo anyway


foo may consist of multiple operators, in which case they are evaluated and summed. For example (()()) pushes 2 to the stack (and evaluates to 2 too).

Obviously, the (()...()) mechanism is not useful in Code Golf as large numbers would take n*2+2 bytes to represent. Your challenge is therefore to write a program or function that will output in as few bytes as possible a Brain-Flak program that will push a given positive integer n to the active stack. This program must not make any assumptions about the existing contents of the stacks, so it must not leave the stacks exchanged or add or remove extra values from the stacks.

Although your program or function must be capable of returning a working Brain-Flak program for all inputs from 1 to 1,000,000 the winner will be the program or function that generates the smallest set of appropriate Brain-Flak programs for all 1061 prime numbers between 1,000 and 10,000. You should note the total size of your outputs for those 1061 inputs as part of your submission. Your program or function may accept the integer and return the (string) Brain-Flak program in any of the usual acceptable I/O formats. Ties will be broken using the size of your program or function.

• Just as a note: the number of valid programs of length 2n is 4^n catalan(n). Aug 13, 2016 at 17:34
• Hmm, I like the challenge, but I think it should be scored on unknown integers. Otherwise, the integers programs are scored upon could be brute forced and other integers just left as (()()()...()). Plus, if you just use prime numbers, that might miss out on some optimizations possible for composites. Aug 13, 2016 at 17:40
• Also, why is [] undefined for this challenge? I find it strange to implement 7 of the 8 operators. Either way, cool challenge, I'm honored someone would write a challenge inspired by my own language! Aug 13, 2016 at 17:43
• @DJMcMayhem I want people to be able to compute their own score. All relevant prime numbers are one more than a composite number, so there should be plenty of potential optimisations. Also, I don't want people to rely on a particular value of [] in their answer.
– Neil
Aug 13, 2016 at 18:00
• @YetiCGN The script's size only counts as a tie-breaker.
– Neil
Aug 20, 2016 at 15:14

Python 2, 5939459244585345841658394 58250

Ok here is my solution.

import re
import math

cache = {0:"<()>"}

def find(x,i,j):
return i*((x**2+x)/2)+(j+1)*((x**2-x)/2)

def solve(x, i, j):
a = (i + j + 1)/2.
b = (i - j - 1)/2.
c = -x
return (-b + math.sqrt(b**2 - 4*a*c))/(2*a)

def size(i,j=0):
return 4*(i+j)+14

def polynomials(n):
upperBound = int(4*math.log(n,2))
i = 0
while size(i) < upperBound:
for j in range(i):
sol = int(solve(n, i-j, j)+.5)
if find(sol, i-j, j) == n:
i += 1

def complement(character):
dict = {"(":")","{":"}","<":">","[":"]",")":"(","}":"{",">":"<","]":"["}
return dict[character]

def findMatch(snippet, index):
increment = 1 if snippet[index] in "({<[" else -1
stack = []
if snippet[index] in "(){}<>[]":
stack.append(snippet[index])
while len(stack) > 0 and index + increment < len(snippet):
index += increment
if snippet[index] in "(){}<>[]":
if complement(snippet[index]) == stack[-1]:
stack = stack[:-1]
else:
stack.append(snippet[index])
return index

def isPrime(n):
return not [0 for x in range(2,int(n**.5)+1) if n%x==0] and n>1

def getPrimeFactors(n):
return [x for x in range(2,n/2) if n%x==0 and isPrime(x)]

def divHardcode(n,m):
assert n%m == 0
assert m != 1
assert n != 1
binary = bin(m)[3:]
return (binary.count("1")+len(binary))*"("+getBF(n/m)+")"*binary.count("1")+binary.replace("1","){}{}").replace("0","){}")

def isTriangular(n):
#Triangles must be between sqrt(2n) and cbrt(2n)
if n < 0: return isTriangular(-n)
for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
if (x**2+x) == 2*n:
return True
return False

def getTriangle(n):
if n < 0: return -getTriangle(-n)
#Triangles must be between sqrt(2n) and cbrt(2n)
for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
if (x**2+x) == 2*n:
return x
#If we don't find one we made a mistake
assert False

def getSimpleBF(n):
if n in cache:return cache[n]
if n < 0:
# There is room for better solutions here
return "["+getSimpleBF(-n)+"]"
elif n == 0:
return ""
elif n < 6:
return "()"*n
#Non-edge cases
solutions = []
factors = getPrimeFactors(n)
if n >= 78 and isTriangular(n):
solutions.append(
min([push(getTriangle(n))+"{({}[()])}{}","<"+push(getTriangle(n)+1)+">{({}[()])}{}"],key=len)
)
polynomialSolutions = polynomials(n)
for polynomial in polynomialSolutions:
solutions.append("<%s>{%s({}[()])%s}{}"%(push(polynomial[0]),"({})"*polynomial[1],"({})"*polynomial[2]))
#Mod 3 tricks
if n % 3 == 2:
solutions.append(("((%s)()){}{}")%getBF(n/3))
elif n % 3 == 1:
solutions.append(("((%s)()()){}{}")%getBF(n/3-1))
#Basic solutions
if isPrime(n):
solutions.append(getSimpleBF(n-1) + "()")
else:
solutions += map(lambda m:divHardcode(n,m),factors)
return min(solutions,key=lambda x:len(unpack(x)))

def getBF(n):
if n in cache: return cache[n]
result = getSimpleBF(n)
index = n - 1
while index > n-(len(result)/2):
score = getSimpleBF(index)+getSimpleBF(n-index)
if len(score) < len(result):result = score
index -= 1
index = n + 1
while index < n+(len(result)/2):
score = getSimpleBF(index)+getSimpleBF(n-index)
if len(score) < len(result):result = score
index += 1
cache[n] = result
return result

def unpack(string):
reMatch = re.match("\(*<",string)
if reMatch:
location =reMatch.span()
return string[location[1]:findMatch(string,location[1]-1)] +string[:location[1]-1] + string[findMatch(string,location[1]-1)+1:]
return string

def push(n):
return unpack("("+getBF(n)+")")

def kolmo(string):
code = push(ord(string[-1]))
stringVector = map(ord,string)
for x,y in zip(stringVector[-1:0:-1],stringVector[-2::-1]):
code = "("+code+getBF(y-x)+")"
code = code.replace("<()>)",")")
return code

def kolmo(stringVector):
code = push(stringVector[-1])
for x,y in zip(stringVector[-1:0:-1],stringVector[-2::-1]):
code = "("+code+getBF(y-x)+")"
code = code.replace("<()>)",")")
return code

if __name__ == "__main__":
import primes
sum = 0
for prime in primes.nums:
print push(prime)
sum += len(push(prime))
print sum


The relevant function is push(n). To call it simply call push on the integer you wish to represent.

Explanation

The main optimization done by the program is multiplication hard-coding. The idea of multiplication hardcoding is pretty simple. You push the a number and then pop and push it to create a new value. For example to multiply by two you can use the following code ((n){}) where n code producing a specific number. This works because both (n) and {} have a value of n.

This simple idea can be made more complex for larger numbers. Take for instance 5 it was discovered a while ago that the best way to multiply by five was (((n)){}){}{}. This code makes two copies of the n multiplies one by 4 and adds the two. Using the same strategy I make every multiplication based on a number's binary representation. I won't get into the details of how this works right now but I do this by chopping off the first one of the binary representation and replacing 0 with ){} and 1 with ){}{}. It then makes sure that n is pushed the appropriate number of times and balances all the parentheses. (If you want to know how this is done you can look at my code). If you want to know why this works just ask me in a comment. I don't think anyone actually reads all the updates to my post so I left the explanation out.

When the algorithm attempts to find a multiplication hardcode it attempts all of a numbers prime factors. It ignores composite factors because at one point composite factors could always be expressed more concisely as its own prime factors it is not known if this is still true.

The other byte saving mechanism is a polynomial solution finder. There are certain forms of polynomials that are easy to represent with decrementing loops. These polynomials include, but are not limited to, polygonal numbers. This optimization finds polynomials that fit the form and creates the code that makes them.

Output

paste-bin

• "whether n is larger or smaller than n+1"?? Aug 13, 2016 at 21:48
• @Sparr whether the interpretation of n is larger or smaller than n+1 Aug 13, 2016 at 22:00
• You should unindent the lines from if n % 3 == 2:  to the end of that function by one level. May 8, 2018 at 17:09

Brain-Flak, 64664

Try it Online!

Here is my annotated code

({}<
((((()()()()()){}){}){}()) #41
>)
{
(({})[()()()()()()])
([({}<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){(<{}({}<>)>)}{}({}<>)
{((< #IF
{}
{({}[()]< #FOR
((((()()()()()){}){}){}()) #41
(({})[()])                 #40
>)}{}
>))}{}
(({}))
#MOD2
{(<
({}<(())>)({<({}[()]<>)><>(()[{}])<><({}<>)>}{}<({}<>)><>)<>({}<>)
{((<{}({}< #IF
{}
(((()()()()())({})({})({}){})({})({})({}){})  #125
(({})[()()])                                  #123
((((()()()()()){}){}){}())                    #41
<>
((((()()()()()){}){}){})                      #40
<>
>)

>))}{}{}
>)}{}
#MOD2 (number 2)
(({}))
({}(())){({}[()]<>)<>(()[{}])<>({}<>)}{}
(({})<([{}]{})>)
{
({}[()]<<>
((((()()()()()){}){}){}) #40
(({})())                 #41
<>>)
}{}
}{}
<>{({}<>)<>}<>((((()()()()()){}){}){})


Explanation

This only implements two rules as of now:

• If n is divisible by two return (n/2){}

• If n is not divisible by two return n-1()

It also hardcodes all the numbers smaller than 6.

• Seems like a check for divisibility by three should reduce score by quite a bit Nov 4, 2016 at 9:29
• @ASCII-only I actually implemented it and it increased the byte count. I am working on a way of implement a smarter version of divisibility by three. Nov 5, 2016 at 4:50
• Ok, using Brain-Flak to make a program that generates Brain-Frak numbers. Nice. Apr 12, 2017 at 14:54

Perl, 5922259156 58460 characters

• n() (11322660 characters)
• (n){}() (64664 characters)
• ((n)){}{} (63610 characters)
• ((n)()){}{} (63484 characters) - this is a novel calculation
• (n){({}[()])}{} (60748 characters)
• n[m] (62800 characters)
• (n){m({}[l])}{} (58460 characters) - this is a novel calculation

The formula for that last calculation is n(n/l+1)/2+mn/l. I've tried some other calculations but they are no longer helpful for the given output. The program actually generates all the values up to 9999 but then lists the given prime numbers and their total length.

@primes = (<list of the 4-digit prime numbers here>);
@numbers = ();
for ($i = 1;$i < 10000; $i++) {$numbers[$i] = "()" x$i; # default calculation
}
for ($i = 2;$i < 10000; $i++) { for ($j = 1; $j < 8;$j++) {
&try($i, "$numbers[$i+$j]\[$numbers[$j]]");
}
&try($i + 1, "$numbers[$i]()"); &try($i * 2, "($numbers[$i]){}");
&try($i * 3, "(($numbers[$i])){}{}"); &try($i * 3 + 2, "(($numbers[$i])()){}{}");
for ($l = 1;$l * $l <$i; $l++) { unless ($i % $l) { for ($j = 0; ($k = (($i + $j +$j) * $i /$l + $i) / 2) < 10000;$j++) {
&try($k, "($numbers[$i]){$numbers[$j]({}[$numbers[$l]])}{}"); } } } }$len = 0;
foreach (@primes) {
print "($numbers[$_])\n";
$len += 2 + length$numbers[$_]; } print "$len\n";
sub try {
($n,$s) = @_;
$numbers[$n] = $s if (length($numbers[$n]) > length$s);
}

• Could you provide a link to the output? Aug 22, 2016 at 1:37
• @DJMcMayhem Oops, I'd accidentally corrupted my list of primes, invalidating my character count.
– Neil
Aug 22, 2016 at 9:02
• @Linus ((X)()){}{} pushes X, then adds 1, pushes the result, then pops the X+1 and X. Total 3X+2. I think I tried the other formula on Try It Online but I can double-check if you like.
– Neil
Aug 24, 2016 at 16:20
• @Neil My mistake... These look good but what exactly corrupts your primes then? Aug 24, 2016 at 16:49
• @Neil I get 58158 when I add &try($i *$i, "$numbers[$i]{({})({}[()])}{}");, which goes down to 58032 when I also add &try((3 * $i *$i - $i) / 2, "$numbers[$i]{({})({}[()])({})}{}"); (square/pentagonal numbers) - it's from here Nov 3, 2016 at 13:20 Lua 5.3, 57522 I actually started working on this back when the question was posted, but forgot about it until the Brain-Flak anniversary. -- 64 gives all results through 10000 (should run in about 1 second) -- 78 gives all results through 100000 (should run in about 20 seconds) -- 90 gives all results through 1000000 (should run in about 200 seconds) -- Note: Timings may not be accurate, as the are not updated every time new cases are added. local k_max_len = 64 local k_limit = 10000 local pre = os.clock() local function compute_multiplier_helper(prefix, suffix, m) if m == 2 then prefix[#prefix + 1] = "(" suffix[#suffix + 1] = "){}" elseif m % 2 == 0 then prefix[#prefix + 1] = "(" compute_multiplier_helper(prefix, suffix, m // 2) suffix[#suffix + 1] = "){}" else suffix[#suffix + 1] = ")" compute_multiplier_helper(prefix, suffix, m - 1) prefix[#prefix + 1] = "(" suffix[#suffix + 1] = "{}" end end local function compute_multiplier(m) local prefix = {} local suffix = {} compute_multiplier_helper(prefix, suffix, m) return table.concat(prefix), table.concat(suffix) end local multipliers = {} for m = 2, k_limit do -- Including all factors, not just primes. -- This did improve a few numbers, although none in the ppcg test set. local prefix, suffix = compute_multiplier(m) local mult = {prefix = prefix, suffix = suffix, m = m, cost = #prefix + #suffix} table.insert(multipliers, mult) end table.sort(multipliers, function(a, b) return a.cost < b.cost end) local poly_multipliers = {} poly_multipliers[1] = {m = 1, s = "({})", l = 4} for m = 2, k_limit do local prefix, suffix = compute_multiplier(m) local s = prefix .. "({})" .. suffix assert(#s <= 4 * m) poly_multipliers[m] = {m = m, s = s, l = #s} end poly_multipliers[k_limit + 1] = {m = 0, s = "", l = 0} table.sort(poly_multipliers, function(a, b) return a.l < b.l end) local pcache = {} local plen_cache = {} local function register_push(prefix, suffix, value, pvalue) if value > 1500000 or value < -1500000 then return end local old_res = pcache[value] if old_res == nil then local res = {prefix = prefix, suffix = suffix, value = value, pvalue = pvalue} pcache[value] = res local length = #prefix + #suffix local lcache = plen_cache[length] if lcache == nil then lcache = {} plen_cache[length] = lcache end lcache[#lcache + 1] = res end end local function get_pushes(length) return ipairs(plen_cache[length] or {}) end register_push("", "()", 1, 0) register_push("", "<()>", 0, 0) local function triangle(n) return (n * (n + 1)) // 2 end local function process(length) -- basic for _, res in get_pushes(length - 2) do register_push(res.prefix, res.suffix .. "()", res.value + 1, res.pvalue) register_push(res.prefix, "[" .. res.suffix .. "]", -res.value, res.pvalue) end -- multiplication by constant (precomputed) for _, mult in ipairs(multipliers) do local cost = mult.cost if length - cost >= 4 then local m, prefix, suffix = mult.m, mult.prefix, mult.suffix for _, pus in get_pushes(length - cost) do local name = prefix .. pus.suffix .. suffix register_push(pus.prefix, name, pus.value * m, pus.pvalue) end else break end end -- residue 2 mod3 trick (Neil) -- ((n)()){}{} -- (n) -- push n -- ( ()) -- push n + 1 -- {}{} -- (n + 1) + (n + 1) + n if length - 10 >= 2 then for _, res in get_pushes(length - 10) do local name = "((" .. res.suffix .. ")()){}{}" register_push(res.prefix, name, 3 * res.value + 2, res.pvalue) end end -- residue 1 mod3 trick (Wheat Wizard) -- ((n)()()){}{} -- (n) -- push n -- ( ()()) -- push n + 2 -- {}{} -- (n + 2) + (n + 2) + n -- not useful, but fast... if length - 12 >= 2 then for _, res in get_pushes(length - 12) do local name = "((" .. res.suffix .. ")()()){}{}" register_push(res.prefix, name, 3 * res.value + 4, res.pvalue) end end -- residue 2 mod5 trick (tehtmi) -- (((n)){}()){}{} -- (n) -- push n -- ( ) -- push n -- ( {}()) -- push 2n + 1 -- {}{} -- (2n + 1) + (2n + 1) + n -- [[ if length - 14 >= 2 then for _, res in get_pushes(length - 14) do local name = "(((" .. res.suffix .. ")){}()){}{}" register_push(res.prefix, name, 5 * res.value + 2, res.pvalue) end end -- ]] -- residue 4 mod5 trick (tehtmi) -- (((n)()){}){}{} -- (n) -- push n -- ( ()) -- push n + 1 -- ( {}) -- push 2n + 2 -- {}{} -- (2n + 2) + (2n + 2) + n -- [[ if length - 14 >= 2 then for _, res in get_pushes(length - 14) do local name = "(((" .. res.suffix .. ")()){}){}{}" register_push(res.prefix, name, 5 * res.value + 4, res.pvalue) end end -- ]] -- residue 6 mod7 trick (tehtmi) -- ((((n)())){}{}){}{} -- (n) -- push n -- ( ()) -- push n + 1 -- ( ) -- push n + 1 -- ( {}{}) -- push 3n + 3 -- {}{} -- (3n + 3) + (3n + 3) + n -- [[ if length - 18 >= 2 then for _, res in get_pushes(length - 18) do local name = "((((" .. res.suffix .. ")())){}{}){}{}" register_push(res.prefix, name, 7 * res.value + 6, res.pvalue) end end --]] -- residue 4 mod7 trick (tehtmi) -- ((((n))()){}{}){}{} -- (n) -- push n -- ( ) -- push n -- ( ()) -- push n + 1 -- ( {}{}) -- push 3n + 2 -- {}{} -- (3n + 2) + (3n + 2) + n -- [[ if length - 18 >= 2 then for _, res in get_pushes(length - 18) do local name = "((((" .. res.suffix .. "))()){}{}){}{}" register_push(res.prefix, name, 7 * res.value + 4, res.pvalue) end end --]] -- residue 2 mod7 trick (tehtmi) -- ((((n))){}{}()){}{} -- (n) -- push n -- ( ) -- push n -- ( ) -- push n -- ( {}{}()) -- push 3n + 1 -- {}{} -- (3n + 1) + (3n + 1) + n -- [[ if length - 18 >= 2 then for _, res in get_pushes(length - 18) do local name = "((((" .. res.suffix .. "))){}{}()){}{}" register_push(res.prefix, name, 7 * res.value + 2, res.pvalue) end end --]] -- triangle numbers (?) --(n){({}[()])}{} --(n) -- push n -- { } -- sum and repeat -- ( ) -- push -- {}[()] -- top - 1 -- {} -- pop 0 if length - 14 >= 2 then for _, res in get_pushes(length - 14) do if res.value > 0 then local code = "{({}[()])}{}" register_push(res.prefix .. "(" .. res.suffix .. ")", code, triangle(res.value - 1), res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. code, triangle(res.value), res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, triangle(res.value) + res.pvalue, 0) end end end -- negative triangle numbers (tehtmi) --(n){({}())}{} --(n) -- push n -- { } -- sum and repeat -- ( ) -- push -- {}() -- top + 1 -- {} -- pop 0 if length - 12 >= 2 then for _, res in get_pushes(length - 12) do if res.value < 0 then local code = "{({}())}{}" register_push(res.prefix .. "(" .. res.suffix .. ")", code, -triangle(-res.value - 1), res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. code, -triangle(-res.value), res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, -triangle(-res.value) + res.pvalue, 0) end end end -- cubic (tehtmi) -- (n){(({}[()])){({}[()])}{}}{} -- (n^3-3*n^2+8*n-6)/6 -- (-6 + n*(8 + n*(-3 + n)))/6 --[[ superceded by negative cubic because it is the same cost of -ncubic(-n) if length - 28 >= 2 then for _, res in get_pushes(length - 28) do if res.value > 0 then local code = "{(({}[()])){({}[()])}{}}{}" local v = res.value + 1 v = (-6 + v*(8 + v*(-3 + v)))//6 register_push(res.prefix .. "(" .. res.suffix .. ")", code, v - res.value, res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. code, v, res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, v + res.pvalue, 0) end end end --]] -- negative cubic (tehtmi) -- (n){(({}())){({}())}{}}{} -- (n^3-3*n^2+8*n-6)/6 -- (-6 + n*(8 + n*(-3 + n)))/6 -- [[ if length - 24 >= 2 then for _, res in get_pushes(length - 24) do if res.value < 0 then local code = "{(({}())){({}())}{}}{}" local v = -res.value + 1 v = (-6 + v*(8 + v*(-3 + v)))//6 v = -v register_push(res.prefix .. "(" .. res.suffix .. ")", code, v - res.value, res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. code, v, res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, v + res.pvalue, 0) end end end --]] -- polynomial (Wheat Wizard, modified by tehtmi) -- <(n)>{A({}[()])B}{} where A, B are ({})({})({})... repeated a, b times -- <(n)> -- push n (without adding) -- { } -- repeat until top is zero -- A -- top * a -- ({}[()]) -- top = top - 1; += top - 1 -- B -- (top - 1) * b -- {} -- pop 0 -- triangular numbers are with a = b = 0 -- from B and base: -- (n - 1) * (B + 1) * (n - 2) * (B + 1) * ... -- (B + 1) * (1 + ... + n - 1) -- (B + 1) * n * (n - 1) / 2 -- from A: -- n * A + (n - 1) * A + ... -- A * (1 + ... n) -- A * (n + 1) * n / 2 -- total: (B + 1) * n * (n - 1) / 2 + A * (n + 1) * n / 2 -- [(A + B + 1) * n^2 + (A - B - 1) * n] / 2 -- S := 4 * (A + B) -- [[ if length - 18 >= 2 then for S = 4, length - 14, 4 do for _, res in get_pushes(length - 14 - S) do if res.value > 0 then for _, A in ipairs(poly_multipliers) do if A.l > S then break end for _, B in ipairs(poly_multipliers) do if A.l + B.l < S then -- continue elseif A.l + B.l > S then break else local a = A.m local b = B.m local logic = "{" .. A.s .. "({}[()])" .. B.s .. "}{}" local v = res.value v = ((a + b + 1) * v * v + (a - b - 1) * v) // 2 register_push(res.prefix .. "(" .. res.suffix .. ")", logic, v, res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. logic, v + res.value, res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. logic, v + res.value + res.pvalue, 0) end end end end end end end --]] -- negative polynomial (tehtmi) -- <(n)>{A({}())B}{} -- [[ if length - 16 >= 2 then for S = 4, length - 12, 4 do for _, res in get_pushes(length - 12 - S) do if res.value < 0 then for _, A in ipairs(poly_multipliers) do if A.l > S then break end for _, B in ipairs(poly_multipliers) do if A.l + B.l < S then -- continue elseif A.l + B.l > S then break else local a = A.m local b = B.m local logic = "{" .. A.s .. "({}())" .. B.s .. "}{}" local v = -res.value v = ((a + b + 1) * v * v + (a - b - 1) * v) // -2 register_push(res.prefix .. "(" .. res.suffix .. ")", logic, v, res.pvalue + res.value) register_push(res.prefix, "(" .. res.suffix .. ")" .. logic, v + res.value, res.pvalue) register_push("", res.prefix .. "(" .. res.suffix .. ")" .. logic, v + res.value + res.pvalue, 0) end end end end end end end --]] -- addition -- [[ if length >= 4 then for part1 = 4, length // 2, 2 do for _, res1 in get_pushes(part1) do for _, res2 in get_pushes(length - part1) do register_push(res2.prefix .. res1.prefix, res1.suffix .. res2.suffix, res1.value + res2.value, res1.pvalue + res2.pvalue) end end end end --]] -- pseudo-exponentiation (tehtmi) -- (n)<>(m){({}[()])<>(({}){})<>}{}<>{} -- (n)<>(m) -- push n and m on opposite stacks -- { } -- sum and repeat -- ({}[()]) -- top(m) - 1 -- <>(({}){})<> -- n = 2*n; += n -- {} -- pop 0 -- <> -- swap to result -- {} -- pop and add n -- [[ if length - 34 >= 4 then local subl = length - 34 for part1 = 2, subl - 2, 2 do for _, res2 in get_pushes(part1) do local b = res2.value if b > 0 and b < 55 then -- overflow could be a problem, so bound... for _, res1 in get_pushes(subl - part1) do -- 2n + 4n + 8n + ... + (2^m)*n + 2^m * n -- n( 2 + 4 + 8 + .. 2^m + 2^m) -- n( 3 * 2^m - 2 ) local a = res1.value local body = "(" .. res1.suffix .. ")<>" .. res2.prefix .. "(" .. res2.suffix .. "){({}[()])<>(({}){})<>}{}<>{}" local v = a * (3 * (1 << b) - 2) + b * (b - 1) // 2 + a + b + res2.pvalue register_push(res1.prefix, body, v, res1.pvalue) register_push("", res1.prefix .. body, v + res1.pvalue, 0) end end end end end --]] end --print(os.clock(), "seconds (startup)") local start = os.clock() for i = 2, k_max_len - 2, 2 do --print(i) process(i) end plen_cache = nil local final = {} for i = 1, k_limit do if pcache[i] ~= nil then final[i] = pcache[i].prefix .. "(" .. pcache[i].suffix .. ")" end end pcache = nil -- hard coded to 10000 for ppcg test local sieve = {} for i = 1, 10000 do sieve[i] = true end for i = 2, 10000 do for j = i * i, 10000, i do sieve[j] = false end end --print(os.clock() - start, "seconds (calculation)") --local bf = require("execute2") local count = 0 local sum = 0 local sum2 = 0 local maxlen = 0 local pcount = 0 for i = 1, k_limit do local res = final[i] final[i] = nil --print(i, #res, res) --local ev = res and bf.eval1(bf.compile(res)) or -1; assert( res == nil or ev == i, string.format("Failed %d %s %d", i, res or "", ev)) if sieve[i] and i > 1000 then sum = #res + sum pcount = pcount + 1 end if res then sum2 = #res + sum2 maxlen = math.max(maxlen, #res) count = count + 1 end end print("sum", sum) --print("coverage", count / k_limit, "missing", k_limit - count) --print("sum2", sum2) --print("maxlen", maxlen) assert(pcount == 1061)  Similar idea to the other answers where known-useful functions are used to build up larger numbers from good representations of simpler numbers. One difference is that instead of solving subproblems in terms of smaller numbers, I'm solving subproblems in terms of numbers with shorter representations. I think this makes it more elegant to take advantage of negative numbers as well as handling the case where smaller numbers are represented in terms of larger numbers. Also, trying to find all numbers that can be represented in a certain size rather trying to represent a particular number as shortly as possible actually simplifies certain calculations. Instead of working a formula in reverse to see whether it can be applied to a number, the formula can be worked forwards and applied to every number. Another difference is that known solutions are stored in two pieces -- an (optional) "prefix" and a "suffix" (more like an infix). The valuation of the prefix is expected to be ignored when calculating the given number -- the prefix just contains code that sets up the suffix to run (generally by pushing one or more things to the stack). So, given a prefix and a suffix, the corresponding number can be pushed onto the stack with prefix(suffix). This split basically solves the same problem as the unpack function in Wheat Wizard's answer. Instead of wrapping code with <...> only to undo this later, such code is simply added to the prefix. In a few cases, the prefix actually does get evaluated (mainly for the pseudo-exponentiation operation), so its valuation is also stored. However, this doesn't really cause a big problem, as the generator isn't trying to construct specific numbers. It seem to theoretically imply that there could be two pieces of code of the same length and generating the same number that wouldn't be redundant in the cache due to having different prefix valuations. I didn't bother accounting for this though, as it doesn't seem to matter much (at least in this domain). I imagine it would be easy to whittle down the byte count just by adding more cases, but I've had enough for the moment. I've run to 1000000, but only done sanity checking up to 100000. Pastebin of output on given primes. • What do k_limit and k_max_len do? I'm not sure I understand the header. Jun 30, 2017 at 14:51 • Rather than trying to calculate particular numbers, I'm calculating all useful (ie giving not-too-large numbers shorter than any other found program) programs up to a certain length -- k_max_len. It could as easily check that it has found all the numbers you asked for after processing each length, but it was useful for me to be able bound the max length during testing so the program would run faster. (Processing larger lengths can be very slow.) k_limit is basically the input parameter -- it will output programs for numbers up to this -- assuming k_max_len was large enough to find them. Jul 1, 2017 at 22:39 Python, 59136 58676 characters Brainflak number golfing function: m=11111 R=range(0,m) R[1]="()" R[2]="()()" l=2 def a(v,r): if v>0 and v<m: if isinstance(R[v],int) or len(r)<len(R[v]): R[v]=r if v<R[0]: R[0]=v def s(v,k): S=0 while v>0: S+=v v-=k return S p=lambda r:"("+r+")" w=lambda r:"{({}["+r+"])}{}" def q(r,v): for i in range(1,v): r="("+r+")" for i in range(1,v): r+="{}" return r def e(r,v,k): for i in range(0,k): r=q(r,v) return r while l<m: R[0]=l+1 a(l*2,q(R[l],2)) a(l*3,q(R[l],3)) a(l*5,q(R[l],5)) a(l*7,q(R[l],7)) for i in range(1,l): a(l+i,R[l]+R[i]) a(l-i,R[l]+"["+R[i]+"]") if l%i==0: t=s(l-i,i) a(s(l,i),p(R[l])+w(R[i])) a(l+2*t,p(R[l])+q(w(R[i]),2)) a(l+4*t,p(R[l])+e(w(R[i]),2,2)) a(l+8*t,p(R[l])+e(w(R[i]),2,3)) a(l+16*t,p(R[l])+e(w(R[i]),2,4)) a(l+32*t,p(R[l])+e(w(R[i]),2,5)) a(l+64*t,p(R[l])+e(w(R[i]),2,6)) a(l+128*t,p(R[l])+e(w(R[i]),2,7)) a(l+3*t,p(R[l])+q(w(R[i]),3)) a(l+9*t,p(R[l])+e(w(R[i]),3,2)) a(l+27*t,p(R[l])+e(w(R[i]),3,3)) a(l+5*t,p(R[l])+q(w(R[i]),5)) a(l+6*t,p(R[l])+q(q(w(R[i]),3),2)) a(l+10*t,p(R[l])+q(q(w(R[i]),5),2)) a(l+15*t,p(R[l])+q(q(w(R[i]),5),3)) a(l+12*t,p(R[l])+q(q(q(w(R[i]),3),2),2)) a(l+18*t,p(R[l])+q(q(q(w(R[i]),3),3),2)) a(l+20*t,p(R[l])+q(q(q(w(R[i]),5),2),2)) a(l+24*t,p(R[l])+q(q(q(q(w(R[i]),3),2),2),2)) a(l+36*t,p(R[l])+q(q(q(q(w(R[i]),3),3),2),2)) a(l+40*t,p(R[l])+q(q(q(q(w(R[i]),5),2),2),2)) l=R[0] f=lambda v:p(R[v])  Prime number iteration: def isPrime(v): i=2 while i*i<=v: if v%i==0: return False i+=1 return True for i in range(1000,10000): if isPrime(i): print f(i)  Output: Pastebin Explanation: We pre-populate a list R of Brain-flak representation evaluating to individual integers over a larger than necessary range [1,m-1] to define our function f. The representations are formed by taking the lowest unused representation (indexed by l) and forming many new representations from it, keeping only the shortest. The lowest unused representation assumes that all number 1 to l have been assigned a representation, and that these representations have already been used to produce new numbers. If a value less than l gets a shorter representation we must go back and reproduce numbers beginning form that point. The function f produces a program saving the number to the stack by adding parenthesis. I didn't know any Brainflak when I began this, and greatly appreciate Eamon Olive's answer for pointing out the formula for triangle numbers. Mostly I've generalized the summation and been relentless about checking sums and differences. Adding lots of multiples of sums has had a great effect. For those who care, here is the scratch code I used to see which formulas were worth it. Representation Formulas: 1. Multiplication by small primes: (X){} ((X)){}{} ((((X)))){}{}{}{} ((((((X)))))){}{}{}{}{}{} 2. Addition X+Y: XY 3. Subtraction X-Y: X[Y] 4. Summation to and including X of increment Y: (X){({}[Y])}{} 5. Multiples of summations to X of increment Y, plus X: (X)({({}[Y])}{}){} (X)(({({}[Y])}{})){}{} (X)(({({}[Y])}{}){}){} etc... • I thought 5* wasn't helpful, but I now see it saves 10 characters on my answer. I thought I'd tried those summations, but I'll double-check! – Neil Aug 24, 2016 at 7:38 • Summations of increments plus multiples saves me another 46 bytes, and even then I have to rinse and repeat three times to catch them all. – Neil Aug 24, 2016 at 13:19 • Turns out that if I use subtraction then I don't use 5* again. – Neil Aug 25, 2016 at 19:19 ruby, 60246 bytes $brain_flak = Hash.new{|h, k|
a = []
a.push "()"*k
if k > 1
if k > 10
# Triangle Numbers:
n = (Math.sqrt(1+8*k).to_i-1)/2
if (n*n+n)/2 == k
a.push "("+h[n]+"){({}[()])}{}"
a.push  h[n+n]+")({({}[()])}{}"
end
end
(k**0.51).to_i.downto(2){|i|
# multiplication:
if k%i==0
a.push "("*(i-1) + h[k/i] + ")"*(i-1)+"{}"*(i-1)

end
}
(k/2).downto(1){|i|
a.push h[k-i] + h[i]
}
end

h[k] = a.min_by{|x|x.length}
}
$brain_flak[0] = "<><>" def get_code_for (i) "(#{$brain_flak[i]})"
end


I use a hash. I finds the best golf for a given number and uses the smaller ones to find the larger ones.

Recursive hashes are so much fun!

Python, 64014 characters

I didn't know anything about brainflak before this challenge and only fiddled around with it a bit on tryitonline, so there could be obvious shortcuts I missed. This is a quite boring solution, just splits the input into x=x/2+x%2 or x=x/3+x%3, whichever is shorter.

k=lambda x:"(("+o(x/3)+")){}{}"+(x%3)*"()"if x>3else"()"*x
m=lambda x:"("+o(x/2)+"){}"+(x%2)*"()"if x>6else"()"*x
o=lambda x:min(k(x),m(x),key=len)
b=lambda x:"("+o(x)+")"


Call it like so: b(42)

Lua, 64664 bytes

Program prints the total length of the programs and the program for the 203rd prime (theres a line you can change to change which one is printed, or uncomment a line to print all the programs)

Right now the only optimization is x = 2*n + 1

Hopefully I will have time to add some more optimizations to lower the score.

local primeS = [[<INSERT PRIMES HERE>]]

local primes = {}

for num in primeS:gmatch("%d+") do
table.insert(primes, num+0)
end

local progs = {}
progs[0] = ""
progs[1] = "()"
progs[2] = "()()"

local function half(n)
if progs[n] then return progs[n] end
local p = ""
local div = math.floor(n/2)
local rem = n%2 == 1 and "()" or ""
return "("..progs[div].."){}"..rem
end

for i = 3, 10000 do

local bin = half(i)

progs[i] = progs[i-1] .. "()"

if #bin < #progs[i] then
progs[i] = bin
end

if i % 1000 == 0 then
print(i)
end

end

local n = 203 -- This is the program it outputs
print(n..", ("..progs[203]..")")

local len = 0
for i,v in ipairs(primes) do
len = len + #progs[v] + 2
--print(v.." ("..progs[v]..")\n")
end
print("Total len: "..len)


Husk, 64664, 35 bytes

?*"()"¹+*"()"%2¹+"){}":'(₀½-%2¹¹<6
`

Try it online!

Husk is a golfing language so making a high scoring solution is a little hard, simply because long Husk code quickly becomes unwieldy. I just gave this a shot to practice my Husk.

This implements the same algorithm as my Brain-Flak solution from earlier.