# Do all rational numbers repeat in Fibonacci coding?

In a regular, positional number system (like our decimal numbers), every rational number ends in a repeating sequence (even if it's just 0). For example, $\frac{1}{3}$ in base 10 is $0.33333...$, in base 5 it's $0.131313...$, and in base 3 it's just $0.1$.

A less common number system uses the Fibonacci sequence as its base, so the first few digit places represent $1, 2, 3, 5, 8, 13, 21$, and so on (instead of the decimal $1, 10, 100, 1000,$ etc.). In this system:

\begin{aligned} 17_{10} &= 100101_F \\ 40_{10} &= 10001001_F \end{aligned}

This can easily be extended to digits after the radix point, so $0.1_F = \frac{1}{2}_{10}$, $0.01_F = \frac{1}{3}_{10}$, $0.001_F = \frac{1}{5}_{10}$, and so on.

\begin{aligned} \frac{5}{6}_{10} &= 0.11_F \\ \frac{7}{10}_{10} &= 0.101_F \end{aligned}

Some numbers aren't as easy to write. Greedily adding up the first places that are smaller than the remainder of the number we're trying to write: $$\frac{1}{4} = \frac{1}{5}+\frac{1}{21}+\frac{1}{610}+\frac{1}{1597}... = 0.001001000000101..._F \\ \frac{2}{3} = \frac{1}{2}+\frac{1}{8}+\frac{1}{34}+\frac{1}{89}... = 0.10010010100001..._F$$

Do all rational numbers end in a repeating sequence in Fibonacci coding?

(For the specific case of $\frac{1}{4}$, see here.)

• $\sum\limits_{i=1}^n\frac{1}{F_n}$ is larger than $1$ isn't it? – Jorge Fernández Hidalgo Jan 19 '16 at 18:49
• Right, but I'm guessing that since $\sum{\frac{1}{F_n}} > 1$, that might suggest our rational numbers don't have unique representations. But that also might not affect the answer to the question. – Ivoirians Jan 19 '16 at 21:17
• Here are the first 515 digits of 1/4, using a greedy algorithm from left to right: 0.00100100000010100010010000100100010101010000000010101000000010000010001000100010010101010000001000010010100000010101000001001010101010100010100000100000100001010000101000101010010100101010000000010010010010001010101010000000000100100000000001010100101000000100101000001000101001001010010010010001010101001010010000000001010101010000010101001010010101000001010001000100000100010001010010101010010001001010001010100100001000000100100010001001010010001010101000010001000101010010001010010100101010000100100010100000100 – Jim Belk Jan 19 '16 at 21:25
• @Joe Ah okay. Actually I wonder whether any rational numbers repeat (without terminating) in Fibonacci coding. Apparently $\sum 1/F_n$ is known to be irrational, so it's not inconceivable that all infinite periodic sums have irrational limits. – Erick Wong Jan 21 '16 at 5:22
• In fact, no rational numbers repeat in Fibonacci coding. See this paper by Matala-Aho and Prevost, where they prove a generalization of this fact: cc.oulu.fi/~tma/TAPANI20.pdf – Random Jun 1 '18 at 16:29

• They do repeat: $17 = 100101.000 \cdots$, and similarly $40 = 10001001.000 \cdots$. – Toby Mak Oct 25 '18 at 9:28