3

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

After the radix point (what we'd call a decimal point), it works the same way: $0.1_F = \frac{1}{2}$, $0.01_F = \frac{1}{3}$, $0.001_F = \frac{1}{5}$, and so on. Numbers that are the sum of these are easy:

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

But what about $\frac{1}{4}$? Greedily adding up the first places that are smaller than the remainder of $\frac{1}{4}$, it turns out to be:

$$\frac{1}{4} = \frac{1}{5}+\frac{1}{21}+\frac{1}{610}+\frac{1}{1597}... = 0.001001000000101..._F$$

Does the Fibonacci coding of $\frac{1}{4}$ ever repeat?

(If you can answer this question, you might be able to answer a more general question: whether or not all rationals eventually repeat in Fibonacci coding.)

Community
  • 1
Joe
  • 1,253
  • 2
  • 10
  • 21
  • 2
    How do you know that $1/4$ is even expressible in this form? – ASKASK Jan 21 '16 at 01:15
  • 1
    Presumably you only allow digits $0$ and $1$, otherwise it's too easy: $\frac14=0.0002$. – David Jan 21 '16 at 01:20
  • @ASKASK Since $\phi\lt 2$ it should be possible to prove that a greedy representation exists, but by the same standard it's highly unlikely that representations are unique. – Steven Stadnicki Jan 21 '16 at 01:22
  • @ASKASK, as more digits are added in this form, the value quickly approaches 1/4. – Joe Jan 21 '16 at 01:22
  • 1
    @Joe but how do you know that a series of reciprocals of fib numbers must eventually converge to $1/4$? – ASKASK Jan 21 '16 at 01:23
  • @StevenStadnicki, it wouldn't surprise me at all if representations are not unique. For integers at least, Zeckendorf coding allows unique representations in Fibonacci base. – Joe Jan 21 '16 at 01:26
  • @Joe Thinking about it more, representations are guaranteed to be highly nonunique, so you may want to talk about some form of canonical representation. (For instance, $\frac12$ is obviously $0.1$, but it also has a representation $0.0101001010000100000000001\ldots$, obtained by 'skipping' the obvious term and writing $\frac12=\frac13+\frac16$ and then expanding $\frac16$ greedily.) In fact, every number in $0\ldots 1$ should have infinitely many and possibly (my topology isn't great) continuum many expansions. – Steven Stadnicki Jan 21 '16 at 01:29
  • @StevenStadnicki, I'll clarify that I'm only looking at a greedy representation. – Joe Jan 21 '16 at 01:30
  • Possibly relevant (note that it's irrational) – Akiva Weinberger Jan 21 '16 at 04:27

0 Answers0