Re:Negative Base
by msoucy on Thursday June 28, 2018 @09:33AM
(#17416689)
When I was part of an organization in college, part of the onboarding process was that each applicant had to have a conversation and (possibly) do a "quest" for each member. My standing quest was that I would write the first 12 or so numbers in negabinary on my whiteboard, and have them determine the next few numbers and explain what they meant. I had people sitting outside my room for hours trying to figure it out. A few did do it, and normally had some expletives for me afterward.
[ Parent
| on HN ]
Re:Negative Base
by bhrgunatha on Thursday June 28, 2018 @10:28AM
(#17417126)
Looking at the table is bad enough, but I imagine most people looking would think "Aaah binary" and convert to decimal: 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28...
That's cruel :)
I probably got a little too much sadistic pleasure out of it, yes...
However, I was always willing to answer nontrivial questions, and even convert numbers to/from negabinary to help them. (The program used the Schroeppel2 implementation, to prevent them from getting too much of a clue if they somehow managed to find its source code)
Re:Negative Base
by soVeryTired on Thursday June 28, 2018 @11:17AM
(#17417556)
Looking at the sequence of negabinary representations, I could imagine (with the benefit of hindsight) that it wouldn't be too hard to guess the next numbers in the sequence. You'd just need to make a few observations: the rightmost digit always flips from 1 to 0. The second digit from the right reads one twice, then zero twice, etc. When you increase the length of the sequence, add two leading ones.
I'm not sure those would be enough, but just inspecting the digit-wise patterns would get you pretty far. Correctly interpreting the sequence is far harder!
Yup, the actual challenge was to interpret the sequence, not just produce the next number. I recall a few people starting on that track though.
Reading those as normal binary, apparently there's significant overlap between the negabinary sequence and the sequence of n XOR 10:
https://oeis.org/search?q=1%2C+6%2C+7%2C+4%2C+5%2C+26%2C+27&...
It seems to me like the n-th number repeats 2^n times, with 1 being in the middle of each sequence.
From this, you could get the 13th number quite easily.
Interpreting it would be a lot more difficult though.
Interestingly, normal binary has the same pattern, but with different offsets for the start of the sequence.
I bet they were frustrated. I was thinking of the various puzzles online trying to understand a sequence of numbers when I read about this, and realizing there's no way I'd ever have come up with the answer on my own.