19
$\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$
3
  • 14
    $\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$ Commented Mar 1, 2015 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$ Commented Mar 1, 2015 at 5:16
  • $\begingroup$ Those look interesting; thanks! $\endgroup$
    – joshlf
    Commented Mar 1, 2015 at 6:23

4 Answers 4

31
$\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$
4
  • 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
    Commented Mar 1, 2015 at 5:48
  • $\begingroup$ @Quincunx You are correct, edited to reflect issues. $\endgroup$
    – Bill Trok
    Commented Mar 1, 2015 at 6:05
  • $\begingroup$ What about b < 2? (assuming those systems can even represent rational numbers) $\endgroup$
    – Ixrec
    Commented Mar 1, 2015 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$ Commented Mar 2, 2015 at 0:51
24
$\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$
4
  • 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
    Commented Mar 2, 2015 at 10:39
  • 3
    $\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$ Commented Mar 2, 2015 at 13:44
  • $\begingroup$ Can you do arithmetic with this representation? $\endgroup$ Commented Oct 17, 2016 at 22:11
  • 2
    $\begingroup$ @PyRulez It appears yes, see Exact arithmetic on the Stern–Brocot tree. $\endgroup$ Commented Oct 17, 2016 at 22:20
10
$\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$
3
  • $\begingroup$ Do you happen to know where I might find a proof of this? $\endgroup$
    – joshlf
    Commented Mar 1, 2015 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
    Commented Mar 1, 2015 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$
    – anon
    Commented Mar 1, 2015 at 18:14
5
$\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$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .