Puzzle: Count from 1 to 10 in base negative 2. | Hacker News Reader

Puzzle: Count from 1 to 10 in base negative 2.

7 pointsColinWright11 comments

Apparently this used to be a Microsoft interview question. With the recent question about calculating "by hand" in hexadecimal, I was wondering if people might like this related question.

Edited for (some) clarity: Count in base -2, starting from 1, taking 9 steps.

View on HN

My first reaction is to simply write all the powers of -2 (1, -2, 4, -8...) and simply brute force each of 1-10 to find a solution for how to write a particular number. I think this is what the OP replied below as "looks right", but I think thats actually simply one form of base 2.

The definition of writing something in base n is that you are expressing a number it using n unique values for each digit. Using these digits, there is a way of utilizing the space maximally to write any positive integer which is the above method of packing the values. Simply using n unique values and having each digit #d represent the power n^d.

For base -2, using -2 unique symbols is clearly nonsense. Assigning each digit a power of -2 and allowing for symbols 0 or 1 for each digit is actually just base 2, exactly like how gray code is base 2. It's interesting that its a form of base 2 that has an implicit sign-bit, but its also somewhat strange of a property since it ends up with twice as many negative numbers as positive numbers for any set number of bits.

Microsoft should clearly hire me.

Do you want an answer or is this a question to provoke thought? I have an answer.

I also have an answer. Do you blog? Perhaps you could write up your answer and point us at it.

Otherwise, I don't have a problem with you giving us your answer, although others might like to think about it first. Of course, the question has had so few upvotes, no one is likely to see it.

Here's my answer:

http://active-thought.com/files/answer.txt

Looks right to me. Hope you found it an interesting exercise!

It was and it inspired me to think about complex bases too.

What base is "10" in? I.e., is the question to count from one to minus two (in which case the answer is the empty list of numbers, with all of its members written in base -2) or to count from one to ten?

The "10" in the question is in base (9+1). The question is to produce a sequence in base -2 starting with 1 and taking 9 steps forwards.

is there a standard way of dealing with negative bases? ie, I thought in base -2 our digits would be {0,-1}, not {0,1}.

edit: also, I had a different idea of what "taking a step" would mean. my solution: http://pastie.org/1987386

This will have more than one valid solution, eg. 110 == -10 == (two).

Yes, and shifting is the same as multiplying by -2. Fun!

Can you do it without negative signs?

Reply on news.ycombinator.com