Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship

Abstract

The binary number system is the basic number representation in computing. We can encode natural numbers with finite 0-1 sequences. The representation of natural numbers is based on this system. However, this poses problems and is technically not perfect. Several attempts have been made to handle integers (signed numbers). We mention only two: the balanced triple number system and the number system with base $-2$. Our paper introduces new possibilities. We also shed light on the graph theoretical background of the new number systems.

1. Introduction

Positional number systems are fundamental in mathematics (see [1]). The development and spread of the number system with base 10 is a major achievement of ancient/medieval mathematics. The advent of computers gave special importance to the number system with base 2. These number systems encode natural numbers as a finite sequence of digits. The positions in a sequence of digits are local values weighted by the digits. The sum of these weighted values is a number, coded by the representation.

In the number system with base 2, the digits are $0/1$ (they are called bits), and the values of the positions are …, 16, 8, 4, 2, 1. This basic theorem of the binary system can be formulated as follows.

Theorem 1.

Every natural number can be written uniquely as the sum of distinct powers of two, where the order of the members of the sum does not matter.

First note that the empty sum is also considered; its value is 0. The value of a sum with one term is the value of the only term. Second, we eliminate the freedom in the order of the terms by listing them following increasing order, that is, writing down the number n

$$n=2^{\alpha }+2^{\beta }+\dots +2^{\omega },\mathrm{where}\alpha >\beta >\dots >\omega .$$

The digits 0 do not contribute to the value; hence, we do not include them in the sum.

The ternary number system can be introduced in a similar way. In the number system with base 3, the digits are 0, 1, and 2, and the local values are …, 81, 27, 9, 3, 1.

The decimal number system can be discussed similarly. All number systems are suitable for the unique encoding of natural numbers. If we want to consider integers, the usual method is to introduce signed numbers. Following a $+/-$ sign, we encode the absolute value of a number. The mathematical beauty is somewhat compromised: $+0$ and $-0$ are two codes for the same number.

It helps if you use negative digits. Then, the positive/negative numbers can be handled homogeneously. This option was first published by J. Colson [2]. Later, independently, A. Cauchy [3] also discovered this possibility. A survey on the subject was published in Kvant [4].

If we have digits $\{-1,0,1\}$ (or more generally, a subset of the integers that is closed under taking opposite), then the sign change will be the sign changes of the digits. This advantage was also noticed by Shannon [5].

When designing multiple computer architectures, this advantage was considered [6,7,8,9,10,11,12,13]. The digits $-1$, 0, and 1 can be called trits. Their technical realization is possible. Two early architectures build on this [12,13,14]. Many have looked in more depth at the ternary computers [15,16]. Currently, binary architecture—thanks to its explosive development—is the single dominant technology.

We highlight two possibilities where integers are represented by a finite sequence of $-1/0/1$ digits.

The first is the balanced ternary system. In this number system, the digits $-1$, 0, 1 are powers of 3 of the local values [17]. The advantage of this number system is that all integers can be represented and the representation is unique. Donald Knuth’s well-known statement, in his excellent book [18], describes this system as ”Perhaps the prettiest number system of all is the balanced ternary notation,…”

The second is the negabinary. Here, the number system is based on $-2$. The local values are the powers of $-2$, and the digits 0 and 1. We can expand ${(-2)}^{\alpha }$ and consider it as $2^{\alpha }$ with a possible sign.

For further systems, see [19,20,21,22].

In this note, we propose several new numeral systems based on our main theorem, Theorem 2. We present six options to produce a scheme for a unique representation of integers. In spite of their simplicity, I was able to find only one of them in the literature [20].

We call the new number system the alternating binary number system. The idea is that the local values are the same as in the binary system: …, 16, 8, 4, 2, 1 (the powers of two). The digits are $-1/0/1$. Our main addition assumption is that the non-zero digits must alternate. The representation of a given integer using the above rules will be ambiguous. But this ambiguity is limited: all non-zero integers will have exactly two representations. The basic theorem of our paper is the following statement.

Theorem 2.

Every non-zero integer n has exactly two representations as

$$n=s_{\alpha }{2}^{\alpha }+s_{\beta }{2}^{\beta }+\dots +s_{\psi }{2}^{\psi }+s_{\omega }{2}^{\omega },$$

where $\alpha >\beta >\dots >\psi >\omega$, $s_i\in \{-1,1\}$, for $i=\alpha ,\dots ,\omega$; furthermore, any two consecutive signs differ.

Alternation means the $s_{\alpha }=s_{\gamma }=\dots$ and $s_{\beta }=\dots =-s_{\alpha }$.

In exactly one of the two forms, ψ is undefined or $\psi >\omega +1$ (this is called type I). The other has at least two terms and $\psi =\omega +1$ (this is called type II).

The theorem implies a new numeral system, a new coding of integers with a finite sequence of digits. The sum of the theorem contains the non-zero digits of an alternating binary representation. As usual, we write $\overline{1}$ instead of the $-1$ digit. The $\overline{1}$ and 1 digits are at the corresponding location of the code. The powers of two, which are not present at the sum, correspond to 0 digits. For example,

$$2023=2048-32+8-1=2^{11}-2^5+2^3-2^0=100000\overline{1}0100{\overline{1}}_{\mathrm{alt-bin}}.$$

The digit associated with $s_{\alpha }{2}^{\alpha }$ is the first digit of the code, which is referred to as the most significant digit. A single 0 digit is the code of the empty sum: $0=0_{\mathrm{alt-bin}}$. Given a representation/code, a sequence of digits, the number n, can be decoded.

Although uniqueness is not true, the two representations are strongly related. One representation ends with $s·(2^{\omega +1}-2^{\omega })$. The other ends with $s·2^{\omega }$. Otherwise, the two representations are the same.

In the next section, we give a proof of this. We briefly mention several conventions which lead to a unique representation.

Finally, we provide the graph theoretical explanation of our main theorem. This is a crucial part of our paper. It can be seen that there are numerous ways to design number systems. After describing the number system, it is no longer difficult to understand the existence and uniqueness of the representation. In some cases, the existence and uniqueness can be automated [23,24]. We present the path we took to introduce our number system.

In this paper, $\mathbb{N}$ denotes the natural of natural numbers $\{0,1,2,\dots \}$, $\mathbb{Z}$ denotes the set of integers, and ${\mathbb{N}}_{+}$ denotes the set of positive integers.

2. The Proof of Theorem 2

The proof will be a simple series of simple claims and their proof.

1. Suppose that

$$s_{\alpha }{2}^{\alpha }-s_{\alpha }{2}^{\beta }+s_{\alpha }{2}^{\gamma }\mp \dots$$

is a non-empty alternative binary representation of the number n. Then, n is not 0 and its sign is equal to the sign of $s_{\alpha }$.

Indeed,

$$n=s_{\alpha }(2^{\alpha }-2^{\beta })+s_{\alpha }(2^{\gamma }-2^{\delta })+\dots ,$$

where the “brackets” are positive. (Brackets contain two terms, with the possible exception of the last one which might have only one term.)

2. 0 has a single representation, the empty sum.

3. It is enough to prove the theorem for positive integers, assuming that the most significant digit is $+1$.

4. Let n be a positive integer and take an alternative binary representation of it with $\ell (>0)$ terms. Consider the representation first $k(<\ell )$ of the representation and denote their sum by $S_k$. If k is even, then $S_k<n$. If k is odd, then $S_k>n$.

Indeed,

$$n=(2^{\alpha }-2^{\beta })+(2^{\gamma }-2^{\delta })+\dots =2^{\alpha }-(2^{\beta }-2^{\gamma })-\dots ,$$

where the “brackets” have positive values.

5. Each positive integer n has an alternating binary representation.

Let us write down n in the binary number system, i.e., as the sum of different powers of two (with strictly decreasing order of exponents). Substitute $2^{k+1}-2^k$ for each power of two: $2^k$. We obtain a new representation of our initial number as the sum of signed powers of two; furthermore, the signs alternate. The exponents will be decreasing but not strictly decreasing. There can be only two powers of the same exponent, they must follow each other, and they must have different signs. Thus, they cancel. By performing the cancellations, we obtain a representation of our starting number in the alternating binary number system.

6. Let n be a power of two, i.e., $n=2^k$ for a suitable natural number k. Then, n has exactly two alternating binary binary representations: $2^k$ and $2^{k+1}-2^k$.

We know (4.) that $2^{\alpha -1}\le 2^{\alpha }-2^{\beta }\le n\le 2^{\alpha }$.

7. If n is between two consecutive powers of two (for a suitable natural number k we have $2^k<n<2^{k+1}$), then the first term of each representation of n is necessarily $2^{k+1}$.

Again, we know (4.) that $2^{\alpha -1}\le 2^{\alpha }-2^{\beta }\le n<2^{\alpha }$.

8. If $2^k<n<2^{k+1}$ ($k\in \mathbb{N}$), then every representation of n is $2^{k+1}-\rho$ where $\rho$ is the representation of the number $2^{k+1}-n(>0)$

9. If $2^k<n<2^{k+1}$ ($k\in \mathbb{N}$), then $2^{k+1}-n$ is strictly smaller than n.

Then, the proof is completed by a simple induction.

In the case of a non-zero number in one of the two options for the representation, the last is non-zero, and the preceding digit is $0d$, or $d\overline{d}$, where $d\in \{-1,1\}$. There are several simple ways to make the representation unique.

Theorem 3.

The alternating binary representation will be unique if any of the following additional conditions are satisfied:

 (a) 

The last non-zero digit must be 1.

 (b) 

The last non-zero digit must be $-1$.

 (c) 

The last non-zero digit must be immediately preceded by a 0 digit (or we have only one non-zero digit).

 (d) 

The last non-zero digit must be immediately preceded by a non-zero digit.

 (e) 

The number of non-zero digits is odd.

 (f) 

The number of non-zero digits is even.

The proofs are straightforward.

If we choose any of the rules above, we obtain a numeral system. For example, we can fix (c) as the basic rule of binary alternating coding of integers. We will denote the $-1$ digit as $\overline{1}$ and we use subscript $2-Alt$ when representing n using place-value notation. We list a few integers with small absolute value and their representation.

$$-11=\overline{1}1\overline{1}{01}_{2-Alt},-10=\overline{1}10\overline{1}{0}_{2-Alt},-9=\overline{1}100{\overline{1}}_{2-Alt},-8=\overline{1}{000}_{2-Alt},-7=\overline{1}{001}_{2-Alt},$$

$$-6=\overline{1}{010}_{2-Alt},-5=\overline{1}{0101}_{2-Alt},-4=\overline{1}{00}_{2-Alt},-3=\overline{1}{01}_{2-Alt},-2=\overline{1}{0}_{2-Alt},$$

$$-1={\overline{1}}_{2-Alt},0=0,1=1_{2-Alt},2={10}_{2-Alt},3=10{\overline{1}}_{2-Alt},4={100}_{2-Alt},5=10\overline{1}{01}_{2-Alt},$$

$$6=10\overline{1}{0}_{2-Alt},7=100{\overline{1}}_{2-Alt},8={1000}_{2-Alt},9=1\overline{1}{001}_{2-Alt},10=1\overline{1}{010}_{2-Alt}.$$

3. Connection to Graph Theory

Let $G=(V,E,I)$ be a triple. The elements of V are called vertices; V is the vertex set of G. The elements of E are called edges; E is the edge set G. I is an incidence relation between V and E ($I\subset V\times E$). If $v\in V$ and $e\in E$ are incident, then we say that the vertex v is an endpoint of the edge e. We call G a graph if every edge has two endpoints.

These two endpoints may coincide, in which case e is called a loop. If an edge e has two endpoints u and v, then we say that u and v are connected by e or u and v are adjacent. If two edges have the same two endpoints, then we say that they are parallel edges. If there are no parallel edges in a graph, we only need to describe when two vertices are connected to define the graph. Moreover, if a graph contains no loops, then we call it a simple graph.

If V and E are finite sets, then G is a (finite) graph. If V or E are infinite, then G is an infinite graph.

Definition 1.

Let $\mathcal{G}$ be the infinite graph without parallel edges whose vertices are the natural numbers and two vertices are connected if and only if their sum is a power of two.

Notice that, because $2^k+2^k=2^{k+1}$ for every vertex that is a power of two, a loop is present in our graph. These are the only loops in $\mathcal{G}$. Let ${\mathcal{G}}_0$ be the simple graph that is obtained by removing the loops that are incident to the powers of two.

It is easy to see that ${\mathcal{G}}_0$ is a graph of infinitely many vertices, each of which has infinite neighbors. Let v be a vertex of ${\mathcal{G}}_0$. If k is the natural number satisfying $2^{k-1}<v<2^k$, then the neighbors of v are $2^k-v$, $2^{k+1}-v$, and $2^K-v$, where K is an arbitrary natural number $k+1<K$. If $v=2^k$, then the neighbors of v are 0 and $2^K-v$ for every $k+1<K$ natural numbers.

Lemma 1.

For positive $v\in \mathbb{N}$, the vertex v has exactly one neighbor that is smaller than v.

Let ${\mathcal{G}}_0\left(n\right)$ be the finite graph is obtained from ${\mathcal{G}}_0$ such that $V_n=\{1,2,\dots ,n\}$ with n elements and the edges ${\mathcal{G}}_0\left(n\right)$ are the edges of $\mathcal{G}$ connecting two nodes from $V_n$ (see Figure 1).

Theorem 4.

The graph ${\mathcal{G}}_0\left(n\right)$ is a tree.

Proof. 

We can think about ${\mathcal{G}}_0\left(n\right)$ as a result of the following sequence of graph extensions:

$${\mathcal{G}}_0\left(1\right)\to {\mathcal{G}}_0\left(2\right)\to {\mathcal{G}}_0\left(3\right)\to \dots \to {\mathcal{G}}_0(n-1)\to {\mathcal{G}}_0\left(n\right).$$

The initial graph ${\mathcal{G}}_0\left(1\right)$ is a graph with one node (1) and no edge, i.e., ${\mathcal{G}}_0\left(1\right)$ is the smallest tree. Each expansion step is a “branching” (we extend our actual graph with a new vertex and a new edge that connects the new node to an old one). This operation preserves connectivity and cycle-freeness. That is, the operation forms a tree from a tree. □

Corollary 1.

${\mathcal{G}}_0$ is a tree.

Thus, there is exactly one path from any vertex, let us call it n, to the vertex 0. We assume that $n\ne 0$.

For each edge, label it with the sum of its two endpoints. Thus, we obtain an edge-labeled graph (the labels are powers of two). As the path from n to 0 is traversed, the labels of its edges strictly decrease. The walks with strictly decreasing labels from n to 0 are exactly the paths from n to 0 (that happen to be unique).

This is not true in $\mathcal{G}$. There is a second walk from n to 0 with strictly decreasing edge labels, a walk where the penultimate step is a loop.

The above graph theoretic remark and the alternating binary number system are closely related. The next theorem formalizes this.

Theorem 5.

Let n be a positive integer. Let ${\mathcal{W}}_n$ be the set of $n\to 0$ walks in $\mathcal{G}$ with strictly decreasing edge labels. Let ${\mathcal{R}}_n$ be the set of alternating binary representations of n.

Then, there is a bijection between ${\mathcal{W}}_n$ and ${\mathcal{R}}_n$.

Remember that $\mathcal{G}$ is almost the same as the ${\mathcal{G}}_0$ graph (a tree), except there are additional loops at the neighbors of 0. Hence, ${\mathcal{W}}_n$ consists of two walks: the unique $n\to 0$ path P in ${\mathcal{G}}_0$, and a walk that is the same as P, except that just before reaching 0 we go along a loop. The bijection, presented below, proves that ${\mathcal{R}}_n$ also has two elements, which is the statement of Theorem 2. We can consider Corollary 1 as the graph theoretical analog of Theorem 2.

Proof. 

Let $n=2^{\alpha }-2^{\beta }+2^{\gamma }-2^{\delta }\pm \dots$ be an arbitrary alternating binary representation of n (an element of ${\mathcal{R}}_n$). We introduce the following numbers: $n_0=n=2^{\alpha }-2^{\beta }+2^{\gamma }-2^{\delta }\pm \dots$, $n_1=2^{\beta }-2^{\gamma }+2^{\delta }\mp \dots$, $n_2=2^{\gamma }-2^{\delta }\pm \dots$, $n_3=2^{\delta }\mp \dots$, …, 0. These numbers: $n_0=n$, $n_1$, $n_2$, …, $n_{\ell -1}$, $n_{\ell }=0$ are vertices in $\mathcal{G}$, and they form a sequence of vertices of walk from n to 0. The labels of the edges are $2^{\alpha }>2^{\beta }>2^{\gamma }\dots$.

Conversely, let us take a walk from n to 0 in $\mathcal{G}$ (an element of ${\mathcal{W}}_n$). Let $n=n_0,n_1,\dots ,n_{\ell }=0$ be the sequence of its nodes. $(n+n_1)-(n_1+n_2)+(n_2+n_3)-\dots +s·(n_{\ell -1}+n_{\ell })$ is an element of ${\mathcal{R}}_n$, where s is a sign depending on the parity of ℓ.

The two mappings are inverses of each other; hence, they prove the theorem. □

We recall that after obtaining the two walks in $\mathcal{G}$ we can agree on a condition that makes the route unique. These conditions can be based on the ending of the walk or on parity of the length. At the end of the previous section, we fixed condition (c) in Theorem 3 and gave examples for the concrete representation of small numbers. It is easy to check that condition (c) corresponds to the agreement that the representation is based on the path in the tree ${\mathcal{G}}_0$.

4. Graphs Related to Fibonacci Numbers and the Related Numeral System

In this chapter, we apply the previously introduced graph theory technique. The positional values of the binary system are the powers of two. Now, we start with the Zeckendorff numeral system [25,26,27,28]. Its positional values are the Fibonacci numbers.

Denote by ${\left(F_i\right)}_{i=0}^{\infty }$ the Fibonacci sequence ([29] A000045) defined as $F_n=F_{n-1}+F_{n-2}$ ($n\ge 2$) with $F_0=0$ and $F_1=1$. We refer to $F_2<F_3<F_4<\cdots$ as the Fibonacci numbers. So, when we mention Fibonacci numbers, we mean elements of the Fibonacci sequence with indices at least 2.

In analogy to the previously introduced $\mathcal{G}$ graph, we define a new graph.

Definition 2.

Our graph $\mathcal{F}$ has a vertex set consisting of natural numbers. We connect vertices u and v if $u+v$ is a Fibonacci number.

Specifically, 0 is adjacent to exactly the Fibonacci numbers.

In the graph $\mathcal{F}$, there will be loops. First, note that every third Fibonacci number is even. For the sake of completeness, we acknowledge this commonly known fact.

Lemma 2.

$F_n$ (for $n\ge 2$) is even if and only if n is divisible by 3.

Proof. 

$F_2=1,F_3=2,F_4=3$. We prove by induction that for every positive integer k, $F_{3k}$ is even, and $F_{3k-1}$ and $F_{3k+1}$ are odd. For the base case $k=1$, this is known.

We assume that for $k=\ell$ the claim is true: $F_{3\ell }$ is even, and $F_{3\ell -1}$ and $F_{3\ell +1}$ are odd. We need to prove that $F_{3\ell +3}$ is even, and $F_{3\ell +2}$ and $F_{3\ell +4}$ are odd. This is straightforward from $F_{3\ell +2}=F_{3\ell +1}+F_{3\ell }$, $F_{3\ell +3}=F_{3\ell +2}+F_{3\ell +1}$, and $F_{3\ell +4}=F_{3\ell +3}+F_{3\ell +2}$. □

If $u=v=F_{3k}/2$, then $u+v=F_{3k}$. Thus, $uv$ forms an edge in $\mathcal{F}$, creating a loop.

The graph $\mathcal{F}$ is not a tree, not only because of the loop edges but also because it contains many 4-cycles.

Lemma 3.

If $u,v,u^{\prime },v^{\prime }$ are non-negative integers such that $u+v=F_k$, $u+u^{\prime }=F_{k+2}$, and $v+v^{\prime }=F_{k+2}$, then $u^{\prime }+v^{\prime }=F_{k+3}$. Specifically, $u,v,u^{\prime },v^{\prime }$ form the vertices of a 4-cycle.

Proof. 

We only need to check that $u^{\prime }+v^{\prime }$ will be a Fibonacci number with the right index.

$$\begin{array}{cc}\hfill u^{\prime }+v^{\prime }& =u+u^{\prime }=(F_{k+2}-u)+(F_{k+2}-v)=F_{k+2}+F_{k+2}-(u+v)\hfill \\ \hfill & =F_{k+2}+(F_{k+1}+F_k)-F_k=F_{k+2}+F_{k+1}=F_{k+3}.\hfill \end{array}$$

Thus, the statement is obvious. □

Definition 3.

Let $u(\le F_k)$ be a positive integer. Define $v=F_k-u$, $u^{\prime }=F_{k+2}-u$, $v^{\prime }=F_{k+2}-v)$. The cycle $C_k\left(u\right)$ in the graph F is formed by the edges $uv$, $u{u}^{\prime }$, $v{v}^{\prime }$, and $u^{\prime }{v}^{\prime }$.

Note that the cycles $C_k\left(u\right)$ and $C_k(F_k-u)$ are the same; only the roles of u and v are exchanged.

Lemma 4.

The points of the $C_k\left(0\right)=C_k\left(F_k\right)$ cycle ($u=0$, $v=F_k$, $v^{\prime }=F_{k+1}$, $u^{\prime }=F_{k+2}$) are connected by only one additional edge beside the edges of the cycle: $u{v}^{\prime }$. If u is a positive integer that is not a Fibonacci number, then among the points of $C_k\left(u\right)$, only the edges of the cycle are present.

Proof. 

The points of the $C_k\left(0\right)$ cycle are: $u=0$, $v=F_k$, $v^{\prime }=F_{k+1}$, $u^{\prime }=F_{k+2}$. $u{v}^{\prime }$ is obviously an edge since $u+v^{\prime }$ is a Fibonacci number. $u^{\prime }$ and v may be connected. Because $F_{k+2}<u^{\prime }+v=F_k+F_{k+2}<F_{k+1}+F_{k+2}=F_{k+3}$, their sum lies between two consecutive Fibonacci numbers, meaning it cannot be a Fibonacci number.

Let a be a positive integer: $F_{\ell }<a<F_{\ell +1}\le F_k$. The points of the $C_k\left(a\right)$ cycle are: $u=a$, $v=F_k-a$, $v^{\prime }=F_{k+1}+a$, $u^{\prime }=F_{k+2}-a$. Assume that $u{v}^{\prime }$ is an edge of $\mathcal{F}$. Then, $u+v^{\prime }$ is a Fibonacci number

$$u+v^{\prime }=(F_k-v)+(F_{k+2}-v)=F_k+F_{k+2}-2v<F_k+F_{k+2}<F_{k+3};$$

furthermore,

$$u+v^{\prime }=F_k+F_{k+2}-2v>F_k+F_{k+2}-2F_k>F_{k+2}-F_k=F_{k+1}.$$

Therefore, $u+v^{\prime }$ can only take one value as a Fibonacci number: $F_{k+2}$. This value cannot be the label on this edge because it corresponds to the label of the uu’ edge (and the vv’ edge too). Hence, $u{v}^{\prime }$ cannot be an edge. By the symmetry of u and v, we obtain that $u^{\prime }v$ is not an edge either. □

It will be shown that these cycles, along with the loop edges, are the essential cycles in F. Therefore, it is not difficult to sparsify the F graph to obtain a tree. This is in spite of the fact that some of the 4-cycles share a common edge; hence, they form longer cycles in $\mathcal{G}$.

Definition 4.

Let ${\mathcal{F}}_0$ be the graph obtained from $\mathcal{F}$ by removing the edges connecting 0 to Fibonacci numbers with odd indices, the loop edges, and the $u^{\prime }{v}^{\prime }$ edges of the 4-cycles $C_k\left(a\right)$.

Theorem 6.

${\mathcal{F}}_0$ is a tree.

The theorem points out a spanning tree of $\mathcal{F}$: ${\mathcal{F}}_0$.

Proof. 

Let ${\mathcal{F}}_0\left(n\right)$ be the spanning subgraph of $F_0$ formed by the vertices $0,1,2,\dots ,n$ and the edges between them. It is sufficient to show that for any n, this graph is cycle-free and connected.

For small values of n, it is easy to verify the statement. See ${\mathcal{F}}_0\left(25\right)$ on Figure 2.

By induction, we prove that ${\mathcal{F}}_0\left(F_k\right)$ is a tree. Assume that we know this for ${\mathcal{F}}_0\left(F_{\ell }\right)$. We add the vertices $F_{\ell }+1,F_{\ell }+2,\dots ,F_{\ell +1}-1,F_{\ell +1}$ to it and check that our graph remains a tree. We do this by proving that by adding any of these numbers it will be connected to exactly one earlier (smaller) node.

In the case of $F_{\ell +1}$, this is true. In $\mathcal{F}$, there are two earlier neighbors of it: 0, and $F_{\ell }$. If $\ell +1$ is even, then 0 is connected to $F_{\ell +1}$, but $F_{\ell }{F}_{\ell +1}$ is the deleted edge of $C_{\ell -2}\left(0\right)$ in ${\mathcal{F}}_0$. If $\ell +1$ is odd, then $0F_{\ell +1}$ is a deleted edge, but $F_{\ell }{F}_{\ell +1}$ is a remaining edge of $C_{\ell }\left(0\right)$ in ${\mathcal{F}}_0$.

The same logic works in the case of $F_{\ell }+i$, where $0<i<F_{\ell -1}$. In $\mathcal{F}$, there are two earlier neighbors of it: $F_{\ell +1}-(F_{\ell }+i)=F_{\ell -1}-i$, and $F_{\ell +2}-(F_{\ell }+i)=F_{\ell +1}-i$. The two connecting edges are in two 4-cycles. In one of them, the edge is deleted; in the other, it is not deleted. $F_{\ell }+i$ has exactly one earlier neighbor in ${\mathcal{F}}_0$. □

As previously, we can label the edges. The label of an edge will be the sum of the numbers corresponding to its endpoints. The labels are Fibonacci numbers.

Lemma 5.

Consider ${\mathcal{G}}_0$ as a graph with labeled edges. In this case, the edge labeling possesses the following two properties:

 (a) 

The edges incident to 0 have labels that are even-indexed Fibonacci numbers.

 (b) 

The labels of two adjacent (sharing a common endpoint) edges cannot correspond to Fibonacci numbers with consecutive indices.

Proof. 

The labeling can also be introduced for the edges of graph $\mathcal{F}$. It is worth noting that both statements are false in $\mathcal{F}$. In ${\mathcal{F}}_0$, both statements become true due to the definition of ${\mathcal{F}}_0$, which is a result of sparsifying $\mathcal{F}$.

In $\mathcal{F}$, all Fibonacci numbers appear on edges incident to 0. In the definition of ${\mathcal{F}}_0$, we precisely excluded those edges whose labels correspond to odd-indexed Fibonacci numbers. This yields statement (a).

Let us consider two adjacent edges in $\mathcal{F}$ with label Fibonacci numbers that correspond to consecutive indices. Suppose these two edges are $u{u}^{\prime }$ and $u^{\prime }{v}^{\prime }$ with labels $F_k$ and $F_{k+1}$. Then, due to the $C_{k-2}\left(u\right)$ cycle, the edge $u^{\prime }{v}^{\prime }$ is not present in ${\mathcal{F}}_0$. This confirms statement (b). □

The claim of this lemma and the fact that ${\mathcal{F}}_0$ is a tree leads to a new numeral system. The logic is the same: we have a tree defined on the set of natural numbers. From a vertex n, there is unique path to 0. This path can be converted to a representation of n. The existence and uniqueness follow from graph theory.

Theorem 7 (Fibonacci-alternating representation).

Every natural number n can be written uniquely as a sum

$$n=F_{\ell }-F_{i_1}+F_{i_2}-F_{i_3}+\cdots +{(-1)}^{t-1}{F}_{i_{t-1}},$$

with $i_0=\ell \gg i_1\gg i_2\gg \cdots \gg i_{t-3}\gg i_{t-2}\gg i_{t-1}\ge 2$, where $i\gg j$ denotes $i>j+1$ (i.e., $i\ge j+2$); furthermore, $i_{t-1}$ is even. This sum is called the alternating representation of n.

The proof of Theorem 7 is based on Theorem 6.

Proof. 

Any natural number n can be considered as a vertex in ${\mathcal{F}}_0$. There is a unique $n\to 0$ path in ${\mathcal{F}}_0$. Let $n=n_0,n_1,\dots ,n_{\ell }=0$ be the sequence of its nodes. $n=(n+n_1)-(n_1+n_2)+(n_2+n_3)-\dots +s·(n_{\ell -1}+n_{\ell })$, where s is a sign depending on the parity of ℓ. The values of the expressions in the brackets are Fibonacci numbers. We obtain the existence of the presentation.

For the uniqueness, assume that we have two representations of n. Both of them can be interpreted as the $0\to n$ path in ${\mathcal{F}}_0$ (see the proof of the binary case). Since ${\mathcal{F}}_0$ is a tree, we obtain a contradiction that proves the theorem. □

As previously, we can extend this representation to integers. We give a few examples of this new representation that we denote by $\mathit{F-Alt}$ indices:

$$-11=\overline{1}0010{\overline{1}}_{\mathit{F-Alt}},-10=\overline{1}{00100}_{\mathit{F-Alt}},-9=\overline{1}0100{\overline{1}}_{\mathit{F-Alt}},-8=\overline{1}{0000}_{\mathit{F-Alt}},$$

$$-7=\overline{1}{0001}_{\mathit{F-Alt}},-6=\overline{1}010{\overline{1}}_{\mathit{F-Alt}},-5=\overline{1}{0100}_{\mathit{F-Alt}},-4=\overline{1}{001}_{\mathit{F-Alt}},-3=\overline{1}{00}_{\mathit{F-Alt}},$$

$$-2=\overline{1}{0}_{\mathit{F-Alt}},-1={\overline{1}}_{\mathit{F-Alt}},0=0_{F-Alt},1=1_{F-Alt},2=10{\overline{1}}_{F-Alt},3={100}_{F-Alt},$$

$$4=100{\overline{1}}_{F-Alt},5=10\overline{1}{00}_{F-Alt},6=1010{\overline{1}}_{F-Alt},7=1000{\overline{1}}_{F-Alt},$$

$$8={10000}_{F-Alt},9=10\overline{1}{001}_{F-Alt},10=100\overline{1}{00}_{F-Alt},11=100\overline{1}{01}_{F-Alt}.$$

The new numeral system is based on a spanning tree of $\mathcal{G}$. The graph $\mathcal{G}$ has many cycles. Finding a spanning tree of it is not natural. There are several ways to construct one.

It is possible to describe a different spanning tree and introduce a new numeral system with Fibonacci numbers as place-values. Such numeral systems already exist; for example, see [30,31] for considered numeral systems. The connection between them and graph theory has not been explored so far.

5. Conclusions

The representations we described are very simple (one can say beautiful). Our results may inspire new research. The new number system raises many questions. How can basic operations be performed with numbers based on the new representation? How can numbers in the conventional notation be converted to the new one? What is the complexity of our algorithms? These questions have led to numerous results in the case of previous number systems (see [16,32,33,34,35,36,37]).

A new number system stimulates new research. The Zeckendorf number system is a good example [25]. After the introduction of that number system, research in several directions was initiated. The distribution of digits and algorithms for arithmetic were studied [38]. Later versions with negative digits [30,31,39] were developed. Many other areas of mathematics were connected to these notions. We mention only one, the research of automatic sequences.

The graph $\mathcal{G}$ in the last section is also natural; the proof of the fact that ${\mathcal{G}}_0$ is a tree is simple. Finally, I found some hints to this claim in the literature. The graph ${\mathcal{G}}_0$ arises naturally when one considers “Problems with Powers of Two”, the problem introduced by B. Haran and N.J.A. Sloane [40]. In the Online Encyclopedia of Integer Sequences (QEIS), T. Scheuerle makes a comment to A352178 [41]. He is probably formulating this claim.

After stating the theorems on representing integers, the uniqueness and existence of the state representation can be easily proven through elementary means, much like we did with the binary system. There are automated proofs as well. However, the essence of everything lies in stating the theorem; this is where mathematics begins.

Our article highlights that graphs can be defined in various ways from numbers. Often, a spanning tree for these graphs can be naturally identified. This tree can be viewed as a tree rooted at 0. Each vertex/natural number has a unique path leading to 0. This corresponds to a number-theoretic representation of n. The recognition of this relationship between graph theory and number systems seems entirely novel.