[Question]
  [
## Background
In some possible futures, the world will convert their numerical systems from decimal (base 10 or `b10`) to some other base (binary `b2`, octal `b8`, hexadecimal `b16`, or even unary `b1`, in which case we're screwed!). Thus, in preparation for this possible world-changing event, you decide to base-proof all of your programs. This can be done by using only singular `0`s and `1`s in conjunction with operators to replace the existing number constants.
However, there's just one problem: You have a ton of programs to change, and manually converting each number to an expression would take weeks! Thus, you decide to write a program (or function) to decide for you what expression should replace each number.
## Input
The input will be a positive integer. Your code **must** be able to handle any integer up to 1000.
(If your code supports decimals and/or negative inputs, see **Scoring** below.)
## Output
Your code must output an expression that evaluates to the input in at least one language. This may be any language; it does not have to be the same one your program or function is written in. Also, this expression does not need to be a full program or function.
For clarity, the output may contain any of these operations:
* increment / decrement
* add / sum
* subtract / negate
* multiply / double (only if it doesn't directly involve the number `2`!)
* divide / modulo
* exponents / logarithms
* square / sqrt (again, only if these don't directly involve the number `2`!)
* bitwise operations (bOR, bAND, bNOT, bXOR, bit-shifts)
* setting / getting variables
* stack manipulation
You may **not** use `eval()` or any similar functions in the output. You may also not use in the output any functions that perform an action(s) other than the ones mentioned above.
Oh, and one more thing: since we want the output to be valid in as many bases as possible, the only number constants it may contain are `0` and `1`. Numbers such as `10` (ten) are disallowed, unless the language interprets it as a `1` and a `0`. Using strings to contain numbers is not allowed either, as is using characters such as CJam's `A`-`K` (which represent `10`-`20`).
## Test-cases
(All outputs are in JavaScript, but may work in other languages.)
**Input 1:**
```
2
```
**Possible output 1:**
```
1+1
```
**Input 2:**
```
13
```
**Possible output 2:**
```
(a=1+1+1)*a+a+1
```
**Input 3:**
```
60
```
**Possible output 3:**
```
(b=(a=1+1+1+1)*a)*a-a
```
**Input 4:**
```
777
```
**Possible output 4:**
```
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1
```
**Input 5:**
```
1000
```
**Possible output 5:**
```
Math.pow((a=1+1+1)*a+1,a)
```
---
## Scoring
The goal of this challenge is to shorten your code's output as much as possible. Your score will be calculated in this way:
* **Base score:** The average byte-count of all outputs for integers 1 to 1000.
* **Decimal score:** If your code supports at least 3 decimal places, this is the average byte-count of all outputs of the sequence of numbers starting at `0.001` and ending at `1000`, increasing by `1.001` each time. `0.001, 1.002, 2.003...998.999, 1000.000` Then take 50% off of this score.
* **Negative score:** If your code supports negative numbers and zero, this is the average byte-count of the outputs of all integers from `-1000` to `0`. Then take 10% off of this score.
(The easiest way to calculate these would likely be a loop with your program/function inside.)
**Your final score is the average of whichever of the above formulas apply.**
If the output is non-deterministic (i.e. somewhat random; multiple runs with the same input produces multiple unique outputs), then the score for each input is determined by the largest output over ten runs on my CPU.
Also, as you don't know how precious computer data will be in the future, **the byte-count of your generator code must be less than 512 bytes.**
~~**Lowest score in two weeks (on Sep 30) will be declared the winner.**~~ Congratulations to your winner, **@ThomasKwa**!
---
## Leaderboard
```
var QUESTION_ID=58084,OVERRIDE_USER=42545;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[3],language:a[1]+'/'+a[2],lang2:a[2],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size.toFixed(3)).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.lang2,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){var E=e.lang.toLowerCase(),S=s.lang.toLowerCase();return E>S?1:E<S?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size.toFixed(3)).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,])\/([^\n,]*[^\s,]),.*?([\.\d]+)(?=[^\n\.\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\.\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```
```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```
```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Languages</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Output Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```
To make sure your answer shows up correctly, please start it with this header:
```
# Language name/Other language name, X points
```
Where `X` is the score of your answer. Example:
```
# CJam/Pyth, 25.38 points
```
If you have any questions or suggestions, please let me know. Good luck!
  
[Answer]
# Python/Zilog Z80 machine code, ~~11.653~~ 11.488
```
import math,numpy as np
def R(n):
    if n==0:return []
    if n<0:return -R(-n)
    e=int(math.log(n,2))
    if n >= 5/3 * 2**e:
        return np.append(2**(e+1),-R(2**(e+1)-n))
    return np.append(2**e,R(n-2**e))
def strR(n):
    b = R(n)
    s = ""
    if n==0:return s
    e=max(abs(b))
    while e:
        if e in b:s+="#"
        elif -e in b:s+="+"
        s+=")"
        e//=2
    return s[:-1]
```
Bonuses: Negative numbers.
Assumes that the `hl` register pair initially holds 0, and returns the result in `hl`.
Only these three instructions are used:
```
ASCII   Hex    Instruction
--------------------------
#       23     inc hl
)       29     add hl,hl
+       2B     dec hl
```
We use a small modification of the [minimum-weight balanced binary representation BBR2](https://cs.uwaterloo.ca/~shallit/Papers/bbr.pdf). Since BBR2 minimizes the weight (number of nonzero digits), but we want to minimize the weight plus the number of bit shifts, we change a constant in the algorithm from `3/2` to `5/3`.
To compute the score and verify, use this code:
```
def verify(n):
v = 0
for c in strR(n):
    if c=="#":v += 1
    elif c=="+":v -= 1
    else: v *= 2
return v==n
print(0.5*(sum([len(strR(n)) for n in range(1,1001)])/1000 + \
           sum([len(strR(n)) for n in range(-1000,1)])/1001 * 0.9))
print(all([verify(n) for n in range(-1000,1001)]))
```
Example output:
```
strR(486)
         '#)))))+)+))+)'
```
Or in assembly:
```
inc hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl \ dec hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl
```
More example programs:
```
-256  +))))))))
-255  +))))))))#
-254  +)))))))#)
-253  +)))))))#)#
-252  +))))))#))
-251  +))))))#))#
-250  +))))))#)#)
-249  +)))))#)))+
-248  +)))))#)))
-247  +)))))#)))#
-246  +)))))#))#)
-245  +)))))#))#)#
-244  +)))))#)#))
-243  +)))))#)#))#
-242  +))))#)))+)
-241  +))))#))))+
  -5  +))+
  -4  +))
  -3  +)+
  -2  +)
  -1  +
   0  
   1  #
   2  #)
   3  #)#
   4  #))
   5  #))#
```
Possible optimizations: OP rules that the `inc h` and `dec h` instructions, which directly change the upper byte of `hl`, are illegal, but `sla h` and the undocumented `sl1 h` (left bit shifts by 1 on `h` that shift in a `0` and `1` respectively) are permitted. `sla h` and `sl1 h` are two bytes each, but they can sometimes shorten the output.
[Answer]
# CJam/CJam, ~~143.263~~ ~~42.713~~ ~~28.899~~ ~~23.901~~ ~~21.903~~ 20.468
```
ri
[
    ['X\2b1>e`{~{"1)*)"*}{_({(')*1\"m<"}{"1)*"*}?}?}/]s
    "X1)*"/"1)"*
    "1)1)*"/"1)))"*
    "X1)m<"/"1)))"*
    _"1)"/("1):Y"+\'Y*+
]
{,}$0=
```
No bonuses apply.
Try it online: [sample run](http://cjam.aditsu.net/#code=ri%0A%5B%0A%20%20%20%20%5B'X%5C2b1%3Ee%60%7B~%7B%221)*)%22*%7D%7B_(%7B(')*1%5C%22m%3C%22%7D%7B%221)*%22*%7D%3F%7D%3F%7D%2F%5Ds%0A%20%20%20%20%22X1)*%22%2F%221)%22*%0A%20%20%20%20%221)1)*%22%2F%221)))%22*%0A%20%20%20%20%22X1)m%3C%22%2F%221)))%22*%0A%20%20%20%20_%221)%22%2F(%221)%3AY%22%2B%5C'Y*%2B%0A%5D%0A%7B%2C%7D%240%3D&input=60) | [score calculator](http://cjam.aditsu.net/#code=1000%2C%3A)%5B%7B%5B%0A%20%20%20%20%5B'X%5C2b1%3Ee%60%7B~%7B%221)*)%22*%7D%7B_(%7B(')*1%5C%22m%3C%22%7D%7B%221)*%22*%7D%3F%7D%3F%7D%2F%5Ds%0A%20%20%20%20%22X1)*%22%2F%221)%22*%0A%20%20%20%20%221)1)*%22%2F%221)))%22*%0A%20%20%20%20%22X1)m%3C%22%2F%221)))%22*%0A%20%20%20%20_%221)%22%2F(%221)%3AY%22%2B%5C'Y*%2B%0A%5D%7B%2C%7D%240%3D%2C%7D%2F%5D%3A%2Be-3) | [verification](http://cjam.aditsu.net/#code=1000%2C%3A)_%5B%7B%5B%0A%20%20%20%20%5B'X%5C2b1%3Ee%60%7B~%7B%221)*)%22*%7D%7B_(%7B(')*1%5C%22m%3C%22%7D%7B%221)*%22*%7D%3F%7D%3F%7D%2F%5Ds%0A%20%20%20%20%22X1)*%22%2F%221)%22*%0A%20%20%20%20%221)1)*%22%2F%221)))%22*%0A%20%20%20%20%22X1)m%3C%22%2F%221)))%22*%0A%20%20%20%20_%221)%22%2F(%221)%3AY%22%2B%5C'Y*%2B%0A%5D%7B%2C%7D%240%3D~%7D%2F%5D%3D)
### Example runs
```
   1 X
   2 1)
   3 1))
   4 1)))
   5 1))))
   6 1))1)*
   7 1))1)*)
   8 X1))m<
   9 1)))1)*)
  10 1))))1)*
  11 1))))1)*)
  12 1))1)m<
  13 1))1)*1)*)
  14 1))1)*)1)*
  15 1))1)*)1)*)
  16 X1)))m<
  17 X1))m<1)*)
  18 1)))1)*)1)*
  19 1)))1)*)1)*)
  20 1))))1)m<
```
```
 981 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*Y*)
 982 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*
 983 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*)
 984 1):Y)Y*)Y*)Y*Y*)Y*)Y)m<
 985 1):Y)Y*)Y*)Y*Y*)Y*)Ym<Y*)
 986 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*
 987 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*)
 988 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Ym<
 989 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*Y*)
 990 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*
 991 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*)
 992 1):Y)Y*)Y*)Y*)Y)))m<
 993 1):Y)Y*)Y*)Y*)Y))m<Y*)
 994 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*
 995 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*)
 996 1):Y)Y*)Y*)Y*)Ym<Y*)Ym<
 997 1):Y)Y*)Y*)Y*)Ym<Y*)Y*Y*)
 998 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*
 999 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*)
1000 1):Y)Y*)Y*)Y*)Y*Y*)Y)m<
```
[Answer]
# [ß](https://github.com/minxomat/-S-)/BrainFuck, 34.201 points
### [ß](https://github.com/minxomat/-S-) source (194B):
```
E='++[------>+<]>++'°\c[1]<0°{E&='.'µA=ß"-ß°°c[1]),'')µE&='+++'°/B=1°(A[0]°\A[B]='.'°{µE&='--.++'°]E&=ß~A'+',A[B])&'.'&ß~A'-',A[B])°}°)°'ß"&E,'+-')+ß"&E,'-+')>0µE=ß"'ß"'E,'-+',''),'+-','')°!€E)
```
If someone is interested, I'll add an explanation. The BF output is pretty optimized already, but I guess I could use the remaining 318B of ß code to implement 
* a loop-nesting-optimization,
* more 8bit overflow shortcuts,
* ~~operator collision removal~~.
### Samples:
Running in windows:
```
$ sharps encode.ss 42
++[------>+<]>+++++++++.--.--
$ sharps encode.ss -42
++[------>+<]>++.+++++++.--.--
$ sharps encode.ss 1.427
++[------>+<]>++++++.---.++++++.--.+++++.-------
$ sharps encode.ss -946.427
++[------>+<]>++.++++++++++++.-----.++.--------.++++++.--.+++++.-------
```
Running in linux:
```
$ WINEDEBUG=-all wine sharps source.ss -4.72
++[------>+<]>++.+++++++.------.+++++++++.-----.--
```
Validate in the [online BF interpreter](http://brainfuck.tk).
### Scores:
1. Base average `= 37.495`.
2. Decimal average `= 60.959 * 0.5 = ~30.48`.
3. Negative avg. `= 38.4765234765235 * 0.9 = ~34.629`
4. Avg of the above, final score `= (37.495 + 30.48 + 34.629)/3 = 34.201`.
[Answer]
# Ruby/Ruby, 29.77885
31.873\*0.9 (negative) 30.872 (positive).
Basic strategy is symmetrical base 3 representation ("balanced ternary"), ie when the digits are `-1,0,1` instead of `0,1,2`
```
#function
f=->n{m=n  
  a='0' 
  7.times{|i|
    r=m%3;r-=r/2*3
    m=(m-r)/3
    #produce expression: replace 0 with (0*x+-1)
    #only add 0*x if there are higher base 3 digits to follow.
    #only add (..+-1) if the current base 3 digit is nonzero. 
    a.sub!('0',['','(','('][r]+(m.abs>0?'0*x':'')+['','+1)','-1)'][r])
  }
  #tidy up expression
  a.sub!('(-1)*','-')          #remove internal (-1)*
  a.sub!('(+1)*','')           #remove internal (+1)*
  a[-1]==')' && a=a[1..-2]     #remove unnecessary global brackets
  a.sub!('x','(x=1+1+1)')      #find the first x and define it as 1+1+1=3
  #special cases for small numbers 
  n.abs<8 && a=n==0?'0':['','1'+'+1'*(n-1).abs,'-1'*n.abs][n<=>0] 
  a 
}
#call like this
(1..1000).each{|p|
b=f.call(p)
puts b
```
Here's the output from 0 to 40 before cleanup
```
(+1)
((+1)*x-1)
(+1)*x
((+1)*x+1)
(((+1)*x-1)*x-1)
((+1)*x-1)*x
(((+1)*x-1)*x+1)
((+1)*x*x-1)
(+1)*x*x
((+1)*x*x+1)
(((+1)*x+1)*x-1)
((+1)*x+1)*x
(((+1)*x+1)*x+1)
((((+1)*x-1)*x-1)*x-1)
(((+1)*x-1)*x-1)*x
((((+1)*x-1)*x-1)*x+1)
(((+1)*x-1)*x*x-1)
((+1)*x-1)*x*x
(((+1)*x-1)*x*x+1)
((((+1)*x-1)*x+1)*x-1)
(((+1)*x-1)*x+1)*x
((((+1)*x-1)*x+1)*x+1)
(((+1)*x*x-1)*x-1)
((+1)*x*x-1)*x
(((+1)*x*x-1)*x+1)
((+1)*x*x*x-1)
(+1)*x*x*x
((+1)*x*x*x+1)
(((+1)*x*x+1)*x-1)
((+1)*x*x+1)*x
(((+1)*x*x+1)*x+1)
((((+1)*x+1)*x-1)*x-1)
(((+1)*x+1)*x-1)*x
((((+1)*x+1)*x-1)*x+1)
(((+1)*x+1)*x*x-1)
((+1)*x+1)*x*x
(((+1)*x+1)*x*x+1)
((((+1)*x+1)*x+1)*x-1)
(((+1)*x+1)*x+1)*x
((((+1)*x+1)*x+1)*x+1)
```
And after cleanup
```
0
1
1+1
1+1+1
1+1+1+1
1+1+1+1+1
1+1+1+1+1+1
1+1+1+1+1+1+1
(x=1+1+1)*x-1
(x=1+1+1)*x
(x=1+1+1)*x+1
((x=1+1+1)+1)*x-1
((x=1+1+1)+1)*x
((x=1+1+1)+1)*x+1
(((x=1+1+1)-1)*x-1)*x-1
(((x=1+1+1)-1)*x-1)*x
(((x=1+1+1)-1)*x-1)*x+1
((x=1+1+1)-1)*x*x-1
((x=1+1+1)-1)*x*x
((x=1+1+1)-1)*x*x+1
(((x=1+1+1)-1)*x+1)*x-1
(((x=1+1+1)-1)*x+1)*x
(((x=1+1+1)-1)*x+1)*x+1
((x=1+1+1)*x-1)*x-1
((x=1+1+1)*x-1)*x
((x=1+1+1)*x-1)*x+1
(x=1+1+1)*x*x-1
(x=1+1+1)*x*x
(x=1+1+1)*x*x+1
((x=1+1+1)*x+1)*x-1
((x=1+1+1)*x+1)*x
((x=1+1+1)*x+1)*x+1
(((x=1+1+1)+1)*x-1)*x-1
(((x=1+1+1)+1)*x-1)*x
(((x=1+1+1)+1)*x-1)*x+1
((x=1+1+1)+1)*x*x-1
((x=1+1+1)+1)*x*x
((x=1+1+1)+1)*x*x+1
(((x=1+1+1)+1)*x+1)*x-1
(((x=1+1+1)+1)*x+1)*x
(((x=1+1+1)+1)*x+1)*x+1
```
[Answer]
## Ceylon/Ceylon, ~~49.86~~ 40.95 points
The third version uses Ceylon 1.2 for the generator and 509 bytes of code:
`import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}`
It gets down to 35.22 points, but I won't put this in the title line because Celyon 1.2 only was published at october 29. I don't think I would be able to implement this algorithm in Ceylon 1.1 in this size.). More details down there, here I'll describe the second version. (The first version can be seen in the history – it supported only positive numbers, but did fit into 256 bytes.)
### Second version
Now the second version, which supports negative integers (and 0), and generally creates a bit shorter output by using in addition `-`.
(This version actually uses the permitted length, the first one tried to stay under 256 bytes instead of 512.)
```
String proof(Integer n) {
    if (n == 0) { return "0"; }
    if (n < 0) { return "-" + p(-n, "-"); }
    return p(n, "+");
}
String p(Integer n, String sign) {
    if (n < 9) {
        return sign.join([1].repeat(n));
    }
    value anti = (sign == "+") then "-" else "+";
    value root = ((n^0.5) + 0.5).integer;
    return "(" + p(root, "+") + ")^(1+1)" +
       ( (root^2 < n) then sign + p(n - root^2, sign) else
         ((n < root^2) then anti + p(root^2 - n, anti) else ""));
}
```
Code has length 487, so there is still some space for more optimizations later. (There are also lots of reserves in form of whitespace and long variable names.)
The scoring:
```
Total positive: 42652
Average positive:42.652
Total negative: 43653
Average negative: 43.60939060939061
With bonus:39.24845154845155
Overall score: 40.95022577422577
```
Some sample outputs:
```
   27:  21: (1+1+1+1+1)^(1+1)+1+1
   28:  23: (1+1+1+1+1)^(1+1)+1+1+1
   29:  25: (1+1+1+1+1)^(1+1)+1+1+1+1
   30:  27: (1+1+1+1+1)^(1+1)+1+1+1+1+1
   31:  29: (1+1+1+1+1+1)^(1+1)-1-1-1-1-1
   32:  27: (1+1+1+1+1+1)^(1+1)-1-1-1-1
   33:  25: (1+1+1+1+1+1)^(1+1)-1-1-1
   34:  23: (1+1+1+1+1+1)^(1+1)-1-1
  -27:  22: -(1+1+1+1+1)^(1+1)-1-1
  -28:  24: -(1+1+1+1+1)^(1+1)-1-1-1
  -29:  26: -(1+1+1+1+1)^(1+1)-1-1-1-1
  -30:  28: -(1+1+1+1+1)^(1+1)-1-1-1-1-1
  -31:  30: -(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  -32:  28: -(1+1+1+1+1+1)^(1+1)+1+1+1+1
  -33:  26: -(1+1+1+1+1+1)^(1+1)+1+1+1
  -34:  24: -(1+1+1+1+1+1)^(1+1)+1+1
  993:  65: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  994:  63: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1-1
  995:  61: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1
  996:  59: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1
  997:  57: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1
  998:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1
  999:  53: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)
 1000:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)+1
 -993:  66: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1+1)^(1+1)-1-1-1-1-1
 -994:  64: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1+1
 -995:  62: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1
 -996:  60: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1
 -997:  58: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1
 -998:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1
 -999:  54: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)
-1000:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)-1
    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  15: 1+1+1+1+1+1+1+1
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1
    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  16: -1-1-1-1-1-1-1-1
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1
```
As you can see, the negative ones are always one byte (the leading `-`) longer than the corresponding positive ones.
The base idea is the same as the previous program: find a square near our target number, and represent its root and the remainder recursively.
But now we allow our square being also some larger than the target number, which then makes the remainder negative.
(The `+0.5` can be changed to a different constant to tweak the algorithm, but it seems that I already did hit the optimum here – both 0.4 and 0.6 give worse results.) 
To make negative values negative (and otherwise have the same structure as the positive ones, we pass the operator `sign` to our recursive function `p` – that is either `"+"` or `"-"`. We can use that for the joiner in the trivial cases (i.e. n < 9) as well as for the remainder if it's positive, and use the opposite sign for the remainder if it is negative.
The `proof` function handles the initial sign (with a special case for 0), the `p` function does the actual work, with recursion.
### Third version, for Ceylon 1.2
```
import ceylon.language { S=String, I=Integer,e=expand }
// output a base-proof Ceylon expression for an integer
// (i.e. using only 0 and 1 as digits).
//
// Question: http://codegolf.stackexchange.com/q/58084/2338
// My Answer:  http://codegolf.stackexchange.com/a/58122/2338
//
// The goal is to produce an expression as short as possible, with
// the code staying under 512 bytes in length.
//
// This approach is to represent a positive integer as a square
// of a positive integer plus some remainder (where the remainder
// can be negative), and for negative integers replace the + on the
// outer level by -.
S q(I n) =>
        n == 0 then "0"
        else (n < 0 then "-" + p(-n, "-")
            else p(n, "+"));
// cache for values of p
variable Map<[I, S],S> c = map { };
// Transforms a positive number into a base-proof term, using
// the given sign for the summation on the outer level.
S p(I n, S s) {
    S v =
    // look into the cache
            c[[n, s]] else (
        // hard-code small numbers
        n < 8 then s.join([1].repeat(n)))
            else
    // do the complicated stuff
    (let (a = "+-".replace(s,""))
            e(e {
                    for (x in 2..8) // try these exponents
                        let (l = (n ^ (1.0 / x)).integer) // \[ sqrt[exp]{n} \] in LaTeX
                            { for (r in l:2) // lowerRoot, lowerRoot + 1
                                    if (r > 1)
                                        let (w = r ^ x)
                                            { if (w-n < n) // avoid recursion to larger or same number
                                                    // format the string as  r^x + (n-w)
                                                    "(" + p(r, "+") + ")^(" + p(x, "+") + ")" +
                                                            (w < n then s + p(n - w, s)
                                                                else (n < w then a + p(w - n, a)
                                                                    else ""))
                                            } } })
            // and now find the shortest formatted string
                .reduce<S>((x, y) => x.size < y.size then x else y))
    // this should never happen, but we can't tell the compiler
    // that at least some of the iterables are non-empty due to the if clause.
            else "";
    // this builds a new cache in each step – quite wasteful,
    // as this also happens when the value was found in the cache,
    // but we don't have more characters remaining.
    //// c = map { [n, s] -> v, *c };
    ///better way:
     c = [n,s] in c then c else map{[n,s]->v, *c}; 
    return v;
}
```
The golfed version (i.e. comments and whitespace removed) is posted at the top, at exactly 509 bytes of code.
This uses the same base principle as the second version, but instead of just squares, it also tries to use higher powers of numbers (trying exponents from 2 to 8), and uses the shortest result. It also caches the results, as otherwise this would be unacceptably slow for larger numbers with many recursive calls.
Scoring:
```
Total positive: 36622
Average positive: 36.622
Total negative: 37623
Average negative: 37.58541458541458
With bonus:33.826873126873124
Overall score: 35.22443656343656
```
The big indented construct in the middle are three nested iterable comprehensions, the inner two inside a let expression. These are then unnested using the expand function twice, and the `reduce` function finds the shortest of those strings.
I've filed a [feature request](https://github.com/ceylon/ceylon-spec/issues/1458#issuecomment-152881872) to be able to do this in a single comprehension.
Inside the comprehension, we are building a string from the root `r`, the exponent `x` and the remainder (`n-w` or `w-n`).
The `let` expression and the `map` function are new in Ceylon 1.2. `map` could have been replaced by `HashMap` (which would have needed more characters for the import, although it would probably be even faster, as I wouldn't build the map new for each new entry). The `let` expressions like `let (w = r ^ x)` could have been replaced by using an `if` clause like `if(exists w = true then r ^ x)` (and then I wouldn't have needed the two `expand` calls either), but this would still be a bit longer, not fitting inside the 511 allowed bytes.
Here the sample outputs corresponding to those selected above, all of them except the really small numbers are shorter:
```
   27:  15: (1+1+1)^(1+1+1)
   28:  17: (1+1+1)^(1+1+1)+1
   29:  19: (1+1+1)^(1+1+1)+1+1
   30:  21: (1+1)^(1+1+1+1+1)-1-1
   31:  19: (1+1)^(1+1+1+1+1)-1
   32:  17: (1+1)^(1+1+1+1+1)
   33:  19: (1+1)^(1+1+1+1+1)+1
   34:  21: (1+1)^(1+1+1+1+1)+1+1
  -27:  16: -(1+1+1)^(1+1+1)
  -28:  18: -(1+1+1)^(1+1+1)-1
  -29:  20: -(1+1+1)^(1+1+1)-1-1
  -30:  22: -(1+1)^(1+1+1+1+1)+1+1
  -31:  20: -(1+1)^(1+1+1+1+1)+1
  -32:  18: -(1+1)^(1+1+1+1+1)
  -33:  20: -(1+1)^(1+1+1+1+1)-1
  -34:  22: -(1+1)^(1+1+1+1+1)-1-1
  993:  39: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1-1
  994:  37: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1
  995:  35: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1
  996:  33: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1
  997:  31: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1
  998:  29: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1
  999:  27: ((1+1+1)^(1+1)+1)^(1+1+1)-1
 1000:  25: ((1+1+1)^(1+1)+1)^(1+1+1)
 -993:  40: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1+1
 -994:  38: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1
 -995:  36: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1
 -996:  34: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1
 -997:  32: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1
 -998:  30: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1
 -999:  28: -((1+1+1)^(1+1)+1)^(1+1+1)+1
-1000:  26: -((1+1+1)^(1+1)+1)^(1+1+1)
    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  13: (1+1)^(1+1+1)
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1
    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  14: -(1+1)^(1+1+1)
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1
```
For example, now we have 1000 = (3^2 + 1)^3, instead of 1000 = (6^2-4)^2-5^2+1.
[Answer]
# Ruby/dc, ~~20.296~~ ~~18.414~~ 16.968
Dynamic programming! Defines a list of functions that, given a dc instruction, return a new expression and the numeric value of that expression. Then, starting with `1` prefined, it builds a list of all reachable values up to and including the wanted value.
### edit:
Added a function for *n-1* and made it run the algorithm through multiple passes. It seems to need 7 passes to stabilize. Had to shorten some variable names to stay within 512 bytes.
### edit 2:
Added functions for *n(n-1)*, *n(n+1)* and *n^3* while I was at it. Shortened the code some more, landing at exactly 512 bytes.
```
N = gets.to_i
fns = [
  ->(n,s){[n-1,   s+'1-']},
  ->(n,s){[n+1,   s+'1+']},
  ->(n,s){[n*2,   s+'d+']},
  ->(n,s){[n*3,   s+'dd++']},
  ->(n,s){[n*~-n, s+'d1-*']},
  ->(n,s){[n*n,   s+'d*']},
  ->(n,s){[n*-~n, s+'d1+*']},
  ->(n,s){[n*n*n, s+'dd**']},
]
lst = []*(N+1)
lst[0..2] = %w[0 1 1d+]
loop do
  prev = lst.dup
  (1..N).each do |n|
    fns.each do |f|
      m,s = f[n, lst[n]]
      lst[m] = s if m <= N && (lst[m].nil? || lst[m].size > s.size)
    end
  end
  break if lst == prev
end
puts lst[N]
```
### Generated numbers:
Output consists entirely of five different characters: `1` pushes the value 1 on the stack; `d` duplicates the top of the stack; `+`, `-`, and `*` pops the two top values and pushes their sum, difference, and product, respectively. Each generated expression adds only one value to the stack after execution. 
```
   1: 1
   2: 1d+
   3: 1dd++
   4: 1d+d+
   5: 1d+d+1+
   6: 1d+dd++
   7: 1d+dd++1+
   8: 1d+dd**
   9: 1dd++d*
  10: 1d+d+1+d+
  11: 1d+d+1+d+1+
  12: 1dd++d1+*
  13: 1dd++d1+*1+
  14: 1d+dd++1+d+
  15: 1d+d+d*1-
  16: 1d+d+d*
  17: 1d+d+d*1+
  18: 1dd++d*d+
  19: 1dd++d*d+1+
  20: 1d+d+d1+*
  21: 1d+d+d1+*1+
  22: 1d+d+1+d+1+d+
  23: 1d+dd**dd++1-
  24: 1d+dd**dd++
  25: 1d+d+1+d*
```
...
```
 989: 1d+d+d*d+d1-*1-1-1-
 990: 1d+d+d*d+d1-*1-1-
 991: 1d+d+d*d+d1-*1-
 992: 1d+d+d*d+d1-*
 993: 1d+d+d*d+d1-*1+
 994: 1d+d+d*d+d1-*1+1+
 995: 1d+d+d*d+d1-*1+1+1+
 996: 1d+d+1+dd**d+1-d+d+
 997: 1d+d+1+d+dd**1-1-1-
 998: 1d+d+1+d+dd**1-1-
 999: 1d+d+1+d+dd**1-
1000: 1d+d+1+d+dd**
```
[Answer]
# Python 2.6, ~~78.069~~ - 66.265 points
Submitting my answer for what it's worth (not a lot in this case ... but clearly demonstrating that for this challenge it's not enough to simply think of composing the output as a sum of bit-shifted values; when taken into account that no digits outside of 0 or 1 may appear in the output). I might come back later with a different way of generating output.
The code itself is not too long (176 characters):
```
def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print"".join(f(int(input())))
```
It generates correct but verbose output:
```
17
1+(1<<1+1+1+1)
800
(1<<1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1+1)
```
Snippet that calculates the score:
```
def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print sum(len("".join(f(i)))for i in range(1000))
```
]