Outputting a base-proof expression

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 0s and 1s 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 1

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. 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 2

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 | score calculator | verification

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 3

ß/BrainFuck, 34.201 points

ß 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.

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 4

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 5

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 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 6

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 7

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))