Representations found by the greedy algorithm

[Max A.]

On 12/19/06, Alec Mihailovs <alec at mihailovs.com> wrote:
> From: "Max A." <maxale at gmail.com>
>
> > Theorem 2. For any non-negative integer N, there exists an unique
> > representation
> > N = c1*F(1) - c2*F(2) + c3*F(3) - ...
> > where every coefficient is either 0 or 1 with no adjacent unit
> > coefficients.
>
> That is true also for negative integers and 0. I remember seeing it
> somewhere called ternary Fibonacci number system, with a suggestion of using
> it in computers instead of binary system. I couldn't find a reference
> though. As far as I recall, in some Russian articles it was also called the
> Mendeleev number system (following the idea that everything was invented in
> Russia :) Again, I couldn't find a reference.

I've never heard of the ternary Fibonacci number system. But simply
"ternary number system" is a known beast. In the balanced form (with
the digit set {0,-1,1}) it was implemented in hardware in Setun
computer back in 1970-th. See
http://hitechravlik.blogspot.com/2006_08_01_hitechravlik_archive.html

In Russian literature, Mendeleev is related again to the ternary number system
e.g., see Section 11 in http://www.math.ru/lib/book/pdf/mp-seria/book.29.pdf

Max