25

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

Joe
  • 1,253
  • 2
  • 10
  • 21
  • Does the coding for $\frac{1}{4}$ repeat? – Asinomás Jan 19 '16 at 18:46
  • 1
    $\sum\limits_{i=1}^n\frac{1}{F_n}$ is larger than $1$ isn't it? – Asinomás Jan 19 '16 at 18:49
  • @dREaM, good questions. I can see that $\sum{\frac{1}{F_n}} > 1$, but I'm not sure how to even begin to prove whether $\frac{1}{4}$ repeats or not. – Joe Jan 19 '16 at 19:41
  • We won't even have unique representations for each number in this base, right? – Ivoirians Jan 19 '16 at 20:11
  • @Ivoirians, integers at least can have a unique representation using Zeckendorf notation. – Joe Jan 19 '16 at 20:27
  • 1
    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
  • 2
    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
  • @JimBelk, thanks for the illustration! – Joe Jan 20 '16 at 02:31
  • A comment from the other question, repeated over here for folks who might look at one but not the other: representations are highly nonunique ($\frac12$ has the obvious terminating representation but also has another which arises from writing $\frac12=\frac13+\frac16$ and then applying a greedy algorithm to $\frac16$; etc.) I suspect numbers have continuum many representations but my topology isn't strong, enough to prove it, sadly. – Steven Stadnicki Jan 21 '16 at 01:37
  • The sequence of place values $1/2, 1/3, 1/5, 1/8, \ldots$ does not appear to be at all suitable for Zeckendorf notation, for the simple reason that $1/3 + 1/5 \ne 1/2$. This seems like a case of wishful thinking that one obtains a sensible fractional base system by taking reciprocals just because it works for $b^x$ and factorial base. – Erick Wong Jan 21 '16 at 03:41
  • @ErickWong, I'm aware that Zeckendorf notation doesn't work here. Whether this system is sensible is an entirely different question. – Joe Jan 21 '16 at 04:59
  • 1
    @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 05:22
  • 2
    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: http://cc.oulu.fi/~tma/TAPANI20.pdf – Random Jun 01 '18 at 16:29

1 Answers1

-2

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

Not a Mathematician
  • 1