16
$\begingroup$

In base 10, 1/3 cannot be represented in a finite number of digits. Examples exist in many other bases (notably base 2, as it's relevant to computing). I'm wondering: does there exist any base in which every rational number can be represented in a finite number of digits? My intuition is that the answer is no. If so, what is a proof of this?

$\endgroup$
  • 13
    $\begingroup$ You might be interested in mixed radix systems, such as the factorial system, in which integers are represented as $\sum a_k k!$, where $0\le a_k\le k$. The natural extension to real numbers has the property that all rationals have a terminating representation. $\endgroup$ – André Nicolas Mar 1 '15 at 4:57
  • 8
    $\begingroup$ If you want another system where all rationals can be expressed in a finite number of digits, consider looking into continued fractions. $\endgroup$ – Steven Stadnicki Mar 1 '15 at 5:16
  • $\begingroup$ Those look interesting; thanks! $\endgroup$ – joshlf Mar 1 '15 at 6:23
29
$\begingroup$

Your intuition is correct for instance for all $b > 2$, $\frac{1}{b-1}$ is not going to have a finite representation, and will have the representation $\frac{1}{b-1} = 0.1111111...._b.$ Eg, $\frac{1}{9} = .11111111$ in base 10.

$\endgroup$
  • 2
    $\begingroup$ When you say "is not going to have a repeating representation", don't you mean that it will have a repeating representation? Also, consider $b=2$. $\dfrac{1}{2-1}=\dfrac{1}{1}=1=0.11111...$ but it has a non-repeating representation $\endgroup$ – Justin Mar 1 '15 at 5:48
  • $\begingroup$ @Quincunx You are correct, edited to reflect issues. $\endgroup$ – Bill Trok Mar 1 '15 at 6:05
  • $\begingroup$ What about b < 2? (assuming those systems can even represent rational numbers) $\endgroup$ – Ixrec Mar 1 '15 at 20:23
  • 1
    $\begingroup$ If you want an example that also works in base 2, you could use $1/(b^2-1)$ which has base $b$ expansion $0.01010101\dots_b$. $\endgroup$ – Nate Eldredge Mar 2 '15 at 0:51
22
$\begingroup$

A representation, though not positional, which yields a finite string for rational numbers is the Stern-Brocot representation which derives from the Stern-Brocot tree (also here).

The Stern-Brocot tree is a binary tree which can be used to enumerate all the rationals and which has useful applications in the rational approximation of real numbers. Here is a portion of this curious tree (the horizontal axis has a logarithmic scale):

enter image description here

Since the nodes of this special tree are in one-to-one correspondence with the rationals, one can represent each rational by a string which specifies how to walk down the tree, starting from the root 1/1, to reach the given rational. Since the tree is binary, a rational can be specified by a string of L(eft) and R(ight) letters. The representation is finite because all fractions can be reached with a finite number of turns.

For example, the fraction 8/5 can be specified by RLRL.

Real numbers have, instead, an infinite representation. For example, the golden ratio has the nice representation RLRLRLRLRL...

$\endgroup$
  • 1
    $\begingroup$ I don't see how this has anything to do with the question, which clearly asks about expansions in positional systems. $\endgroup$ – JiK Mar 2 '15 at 10:39
  • 2
    $\begingroup$ @JiK The OP might not have been aware of the existence of non-positional systems, and this is just an example. Consider it as an extended comment. $\endgroup$ – Massimo Ortolano Mar 2 '15 at 13:44
  • $\begingroup$ Can you do arithmetic with this representation? $\endgroup$ – PyRulez Oct 17 '16 at 22:11
  • 1
    $\begingroup$ @PyRulez It appears yes, see Exact arithmetic on the Stern–Brocot tree. $\endgroup$ – Massimo Ortolano Oct 17 '16 at 22:20
9
$\begingroup$

A rational number $x$ has a finite digital expansion in base $b$ if and only if it's expressible as $a/b^n$ for an integer $a$ and some $n\ge1$. In particular $u/v$ (written in simplest terms) cannot be written in base $b$ if and only if the denominator $v>1$ has a prime factor that $b$ doesn't.

$\endgroup$
  • $\begingroup$ Do you happen to know where I might find a proof of this? $\endgroup$ – joshlf Mar 1 '15 at 6:24
  • 5
    $\begingroup$ @synful I suggest trying to prove it yourself, it's very easy. Think about what multiplying by a power of $10$ does to a number's decimal expansion. $\endgroup$ – Jack M Mar 1 '15 at 9:00
  • $\begingroup$ @synful If $x$ has finite digital expansion in base $b$, that means it's a finite sum of powers (possibly negative powers) of $b$. If there are any negative powers, add the fractions using the highest power of $b$ as the LCD to obtain a fraction of the form $a/b^n$. Conversely, given $a/b^n$, we can write $a$ in base $b$ and then just shift $n$ digits to the right. $\endgroup$ – whacka Mar 1 '15 at 18:14
4
$\begingroup$

In standard positional notation, no. Just pick any number p which is relatively prime to the base and 1/p will not terminate.

There is however a delightful way of doing this if we play a little bit loose and lovely with what is a "base", called "factorial base" (if you Google it, their are 6 million hits!). This has the exact property you ask for. Even if it doesn't meet your needs, it is a very interesting idea.

$\endgroup$

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.