Number of ways to write integers in balanced binary

Question

Imagine a method of writing integers which is similar to balanced ternary, except as you write more digits, their value increases by a factor of 2, not 3. For the remainder of the post, I will call this system "balanced binary". For example: (with T representing -1)

1T11 $= 1*2^0 + 1*2^1 - 1*2^2 + 1*2^3 = 7$

10T $= -1*2^0 + 0*2^1 + 1*2^2 = 3$

Obviously, there is more than one way to represent each integer in this system, as an n-digit number can range from $-2^{n+1}+1$ to $2^{n+1}-1$, which contains roughly $2^{n+2}$ numbers, and the n-digit balanced binary string has n ternary digits, which can represent $3^{n}$ numbers, clearly more as n grows.

If given a string in balanced binary, you can apply 2 transformations to the string which do not change its value. These are:

1T <=> 01

T1 <=> 0T

For example:

1T11 $= 7$

10T1 $= 1*2^0 - 1*2^1 +0*2^2 + 1*2^3 = 7$

These represent the fact that $2-1=0+1$, and $1-2=0-1$, respectively.

By applying these transformations to eliminate all T's, all positive numbers written in balanced binary can be converted to their standard binary representations. For negative numbers, the same can be done by eliminating all 1's, then swapping every T with a 1 and adding a negative sign.

What I would like to know is: how can I compute a function which, given an integer and a string length, outputs the number of ways the integer can be written in a balanced binary string of the given length, and, optionally, a list of the representations.

Answer 1

Let $n$ be the given length of the balanced binary representation.
Let $x$ be an integer, such that $0\le x \le 2^n-1$.
Let $b(0),b(1),\dots,b(n-1)$ be the binary digits $x$, so each $b(i)\in \{0,1\}$, and $$x=2^{n-1}b({n-1}) + \dots + 2^0b(0).$$

Defintion: A noncrossing 0-1 matching for $x$ is a list of integers $[m_1,\dots,m_{2k}]$ of even length, such that

• $n - 1 \ge m_1> m_2> \dots > m_{2k} \ge 0$.
• For all $i\in \{1,\dots,k\}$, $b(m_{2i-1})=0$ and $b(m_{2i})=1$.

In words, we find all ways to select a set of disjoint contiguous subsequences of the list $[b(n-1),\dots,b(0)]$, where each subsequence begins with a zero and ends with a one.

Each noncrossing 0-1 matching determines a representation of $x$ of length $n$ in balanced binary, as follows. For $i\in \{1,\dots,k\}$, and each interval of digits of the form $$ [b(m_{2i-1}),b(m_{2i-1}-1),\dots,b(m_{2i})], \qquad b(m_{2i-1})=0,\quad b(m_{2i})=1, $$ we will modify the digits in this interval as follows. We make replacements of the form 01 -> 1T and T1 -> 0T until the only remaining 1 in this block of digits occurs on the left. What remains will be a block starting with $1$, where the rest is made of 0 and T, such that the last digit is T.

For example, with $n=5$ and $x=00101_2=5$, here are the noncrossing 0-1 matchings, and the resulting balanced binary representations.

Noncrossing 0-1 matching	Balanced binary rep of 5
$\text{empty list}$	00101
$[1, 0]$	0011T
$[3, 2]$	01T01
$[3,2,1,0]$	01T1T
$[3,0]$	010TT
$[4,2]$	1TT01
$[4,2,1,0]$	1TT1T
$[4,0]$	1T0TT

Claim: Every balanced binary representation for $x$ of length $n$ is generated in a unique way by some non-crossing 0-1 matching for $x$.

Proof of claim: Given a balanced binary representation $B$ of $x$, where the length of $B$ is $n$, we find the corresponding noncrossing 0-1 matching as follows.

1. Find the rightmost instance of T; its location is the smallest entry in the non-crossing matching.
2. Find the rightmost instance of 1 which is to the left of the T in the previous step; its location is the second smallest entry in the noncrossing matching.
3. Continue capturing intervals like this, where the rightmost digit is a T, the leftmost digit is a 1, and all digits between are 0 or T, until all Ts have been captured in some interval.

This proves that every string is generated. Proof of uniqueness is not too bad, and left to the reader. $\square$

Using the claim, you can imagine a simple backtracking program which enumerates all non-crossing 0-1 matchings of $x$.

Answer 2

I wrote out the sequences for the numbers 1-15 in excel, like so:

I noticed that the end half of the sequences of length 3 was the same as the sequences of length 2. For example, the number of equivalent sequences of length 2 goes 1,2,1,1, and the number of equivalent sequences of length 3 goes 1,3,2,3,1,2,1,1. 1,2,1,1 appears on the end of both. This inspired me to write this sequence in reverse, and plug it into the OEIS, and I found that it matched (perfectly, if you include sequences of length 0) OEIS A002487, which is generated like so:

f(0) = 0

f(1) = 1

f(2n) = f(n)

f(2n+1) = f(n) + f(n+1)

With this insight (and blind trust the sequence remains accurate), a solution presents itself.

If $g(x, l)$ is the function I want, and $f(x)$ is defined above, outputting the number of ways to write the number $x$ as a sequence of length $l$:

$g(x, l) = f(2^l-x)$

This is obviously a little unsatisfying, with no real reasoning, but computes the answer.