18
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ $\sum\limits_{i=1}^n\frac{1}{F_n}$ is larger than $1$ isn't it? $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 18:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Ivoirians Jan 19 '16 at 21:17
  • 2
    $\begingroup$ Here are the first 515 digits of 1/4, using a greedy algorithm from left to right: 0.00100100000010100010010000100100010101010000000010101000000010000010001000100010010101010000001000010010100000010101000001001010101010100010100000100000100001010000101000101010010100101010000000010010010010001010101010000000000100100000000001010100101000000100101000001000101001001010010010010001010101001010010000000001010101010000010101001010010101000001010001000100000100010001010010101010010001001010001010100100001000000100100010001001010010001010101000010001000101010010001010010100101010000100100010100000100 $\endgroup$ – Jim Belk Jan 19 '16 at 21:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Erick Wong Jan 21 '16 at 5:22
  • 2
    $\begingroup$ 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 $\endgroup$ – Random Jun 1 '18 at 16:29
-1
$\begingroup$

I'm not sure if this is what you meant, but integers, such as your examples 17 and 40, are also rational numbers (as they can be represented by x/1, where x is an integer), and they don't repeat in Fibonacci coding, so there are some rational numbers (such as integers) that do not repeat in Fibonacci coding

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.