## Programming Challenge

### Background

At 7 pm on 21 October 1999, participants in the 1999 Mathematica Developer conference were challenged to construct a function which can calculate the negabinary representation of any integer (see below).   Entries were due by noon the next day.  Of the 13 solutions which were received, two solutions caught the attention of the judges.  The first, by Mark Reeve, took a particularly original approach to the problem and performed its computations with far greater efficiency than any of the other entries.  The second, by Jarl Sobel, was written with unparalleled elegance while maintaining a respectable degree of efficiency.  These two solutions were deemed the winners of the contest.

The sections below contain the original statement of the challenge, the entries which were received before the deadline, an explanation of the criteria on which they were judged, and an exhibition of the winners.  After the deadline for the contest, a few especially stunning solutions were devised by Wolfram Research employees.  Although they were exempt from the contest, these solutions are included below.

### Challenge

It is well known that every positive integer has a binary representation---that is, every positive integer can be written in base as a sequence of 's and 's.  In Mathematica, gives the binary representation of .  For example, the binary representation of is .

A number is found from its binary representation by adding together the corresponding powers of two.

Knowing this, it is easy to write a function that finds an integer, given its binary representation (in fact, Mathematica's built-in function does this automatically).

It is not well known that every integer has a negabinary representation---that is, every integer can be written in base as a sequence of 's and 's.  A number is found from its negabinary representation by adding together the corresponding powers of negative two.  For example, the negabinary representation of is .

Knowing this, it is easy to write a function that finds an integer, given its negabinary representation.

So, the negabinary representation of is and the negabinary representation of is .

Unfortunately, Mathematica's built-in function cannot automatically find the negabinary representation of an integer.

Write a function that can find the negabinary representation of any integer .  Solutions will be judged based on efficiency and elegance of code.

### Entries

#### F

``````ToNegabinary[i_]:=
Module[{d={},r=i,n=0},
While[r != 0,
PrependTo[d,Mod[r,2]];
r = (r - Mod[r,2]*(-1)^n++)/2
];
d /. {}->{0}
];    ``````

### Judging

Entries to the 1999 Mathematica Developer Conference Programming Challenge were judged as follows.  First, each prospective solution was tested to verify that it gives the correct output for all integer inputs between -500 and 500.

Any entry for which this test failed to output was disqualified.

Next, a large integer was randomly chosen.

The efficiency of each remaining entry was judged by timing its output for this large input.

Many entries produced recursion errors for large inputs, so it was necessary to set to in those cases.

Lastly, the judges carefully looked at each entry and subjectively evaluated its elegance.

### Winners

#### The Most Elegant Entry

Submitted by Jarl Sobel (jsobel@sdav01.seinf.abb.se).

### Other Solutions

Members of the Wolfram Research staff devised a number of notable solutions. To demonstrate that a working solution could be written by a participant with limited mathematical skill, Matthew Szudzik (mszudzik@wolfram.com) found a short algorithm which searches through all possible sequences of 's and 's until it finds the desired negabinary representation.

David Librik found what is perhaps the ultimate solution---it is extremely efficient and elegant.

Many of the programmers at Wolfram Research experimented with solutions written in different computer languages. Perhaps the most unusual language in which a solution was written is PostScript.  Brian Downing (bdowning@wolfram.com) exploited Mathematica's ability to follow commands written in PostScript, and wrote the following solution.  Note that it requires Mathematica's front end.

### References

See Donald E. Knuth's The Art of Computer Programming (volume 2): Seminumerical Algorithms for a discussion of negative base number representations.