Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Negative Base

en.wikipedia.org

Post reply on HN
Print view View original

21–30 of 74 posts

Re: Negative Base

#21

Post by macintux »

msoucy wrote: post #15

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

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.

Re: Negative Base

#22

Post by catpolice »

philbarr wrote: post #18
Sharlin wrote: post #10

See also balanced ternary [1]. [1] https://en.wikipedia.org/wiki/Balanced_ternary

Which you can use to solve the puzzle: "You have 12 coins that all look exactly the same. One is counterfeit and is either heavier or lighter than the other 11. With a balance beam scale, isolate the counterfeit coin in three moves." Any uses for Negative-base systems?

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Re: Negative Base

#23

Post by JadeNB »

empath75 wrote: post #16
fwdpropaganda wrote: post #14

Earlier quoted context omitted.

So in your mind people are just coming up with these things for no reason, is that it?

It’s fun and interesting to figure out. There are lots of ways to represent numbers but they don’t change the thing they represent.

> There are lots of ways to represent numbers but they don’t change the thing they represent.

Different representations of the same thing are not useless; one might make an argument (which I can only back up off the top of my head with mathematical examples, but I suspect that there are also many in the physical sciences) that they are at the root of much progress. The canonical example is to try to do positive-integer arithmetic with Arabic versus Roman numerals; they represent exactly the same thing, but I'll bet you can compute 16 ⨉ 17, but not XVI ⨉ XXIII (without converting), in your head.

Re: Negative Base

#24

Post by bhrgunatha »

msoucy wrote: post #15

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

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

Re: Negative Base

#25

Post by vinceguidry »

jerf wrote: post #13
vinceguidry wrote: post #7

Earlier quoted context omitted.

I don't think anyone ever imagined a use for imaginary numbers either, but those turned out to be quite useful for reducing dimensionality. Towards the bottom of the article it states that Donald Knuth proposed imaginary base numerical systems. So this may eventually find a use, likely with higher-dimensional math.

In addition to the other points, imaginary numbers immediately added to the representation of things we could represent. Simply rewriting existing numbers in other ways isn't all that interesting; it doesn't add anything. We already knew there's an infinite number of ways to serialize numbers to symbols. Negative base numbers don't behave differently than positive base numbers, because "negative base numbers" and "po…

> At most there might be one or two concepts that might in some manner if you squint hard enough could be better represented by negative base numbers,

That's what I was thinking.

Re: Negative Base

#26

Post by TrinaryWorksToo »

catpolice wrote: post #22
philbarr wrote: post #18

Earlier quoted context omitted.

Which you can use to solve the puzzle: "You have 12 coins that all look exactly the same. One is counterfeit and is either heavier or lighter than the other 11. With a balance beam scale, isolate the counterfeit coin in three moves." Any uses for Negative-base systems?

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

Re: Negative Base

#27

Post by cecilpl2 »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

I don't want to give too much away but consider that if you start by weighing 6 coins against the other 6, you already know what's going to happen.

Re: Negative Base

#28

Post by wolfgke »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

No, it is a ternary search problem.

EDIT: According to

> https://en.wikipedia.org/w/index.php?title=Balance_puzzle&ol...

if you know that one coin is different from the others, with 3 weighings, you can even detect it among 13 coins (not just 12).

Re: Negative Base

#29

Post by scentoni »

JadeNB wrote: post #23
empath75 wrote: post #16

Earlier quoted context omitted.

It’s fun and interesting to figure out. There are lots of ways to represent numbers but they don’t change the thing they represent.

> There are lots of ways to represent numbers but they don’t change the thing they represent. Different representations of the same thing are not useless; one might make an argument (which I can only back up off the top of my head with mathematical examples, but I suspect that there are also many in the physical sciences) that they are at the root of much progress. The canonical example is to try to do positive-integ…

    XVI ⨉ XXIII
  = XVI ⨉ (XVI + I)
  = (XVI ⨉ XVI) + XVI
  = CCLVI + XVI
  = CCLXXII

Re: Negative Base

#30

Post by phamilton »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

Nope. It's ternary in nature. The subproblem of "You have 3 coins, one of which is lighter than the others. On a balanced scale, figure out which one is lighter in one weighing." is a good place to start. Just enumerate all 3 possible weighings and you should be able to see the correct approach.
Post reply on HN