0
$\begingroup$

Recently I have been thinking about writing numbers using the digits $1,-1(=\bar{1}),0$, and combining them similarly as one would for binary representations. For example, $$(1\bar{1}0)_2 = 1\cdot 2^2+(-1)\cdot 2 + 0 =2.$$ I noticed that though this representation is in general not unique for every integer, we may dictate that the digits $1$ and $-1$ alternate in occurrence, like this: $$10\bar{1}001\bar{1}$$ then I was able to show that such representation is unique for each integer as long as we fix the last digit to be either $1$ or $\bar{1}$. Let's call each representation a $1$-rep ( or $\bar{1}$-rep) if it ends in $1$( or $\bar{1}$). I tried to write out the alternative binary representation for small $n$'s, and I seem to see some connections with the regular paper-folding sequence: the occasions where the representation with a smaller number of nonzero digits corresponds to a $\bar{1}$-rep follow the familiar sequence described in https://en.wikipedia.org/wiki/Regular_paperfolding_sequence.

My calculations for the representations

\begin{array}{c|c c c } n & Type-1 & Type-\bar{1} & Shorter Representation \\ \hline 1 & 1 & 1\bar{1} & 1 \\ 2 & 10 & 1\bar{1}0 & 1 \\ 3 & 1\bar{1}1 & 10\bar{1} & -1 \\ 4 & 100 & 1\bar{1}00 & 1 \\ 5 & 1\bar{1}01 & 1\bar{1}1\bar{1} & 1 \\ 6 & 1\bar{1}10 & 10\bar{1}0 & -1 \\ 7 & 10\bar{1}1 & 100\bar{1} & -1 \\ 8 & 1000 & 1\bar{1}000 & 1 \\ \end{array} In the "Shorter representation" column, we use 1 for Type-1 and -1 for Type-I.

How do I prove this?

$\endgroup$
3
  • 3
    $\begingroup$ See balanced ternary system. $\endgroup$ Commented Sep 2 at 16:07
  • 1
    $\begingroup$ @Jean, but balanced ternary involves powers of three, while OP still wants to use powers of two. $\endgroup$ Commented Sep 3 at 1:57
  • 1
    $\begingroup$ @Gerry Myerson My bad. You are perfectly right. $\endgroup$ Commented Sep 3 at 6:21

1 Answer 1

Reset to default
1
$\begingroup$

Write out a binary representation $B$ for a positive integer $n$ using the normal binary system. After adding a leading zero, you can divide this representation in a unique way into a sequence of blocks which are interspersed with strings of zeroes, where each block consists of a 0 followed by a string of 1s. Then you can get your $\bar{1}$-representation of $n$ by changing each block $01^k$ to $10^{k-1}\bar 1$, and you can get your 1-representation in the same way, except that when dividing $B$ into blocks, you don't place the rightmost 1 in a block, but simply place it into the 1-representation unaltered.

Given this, you can see that a 1-representation will always use one more nonzero digit than a $\bar 1$-representation, since it has an extra 1 at the right, unless the rightmost block is $01$, in which case it becomes $1 \bar 1$ in the $\bar 1$-representation and $01$ in the 1-representation. Therefore the numbers whose 1-representation is shorter are those whose binary expansions end with $01$, $010$, $0100$, $\dots$ and the numbers whose $\bar 1$-representation is shorter are those in the complementary set, which is those whose binary expansions end with 11, 110, 1100, $\dots$. This gives the paper-folding sequence.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.