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$ 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$ Mar 1, 2015 at 5:16
  • $\begingroup$ Those look interesting; thanks! $\endgroup$
    – joshlf
    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
    Mar 1, 2015 at 5:48
  • $\begingroup$ @Quincunx You are correct, edited to reflect issues. $\endgroup$
    – Bill Trok
    Mar 1, 2015 at 6:05
  • $\begingroup$ What about b < 2? (assuming those systems can even represent rational numbers) $\endgroup$
    – Ixrec
    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$ 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
    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$ Mar 2, 2015 at 13:44
  • $\begingroup$ Can you do arithmetic with this representation? $\endgroup$
    – PyRulez
    Oct 17, 2016 at 22:11
  • 2
    $\begingroup$ @PyRulez It appears yes, see Exact arithmetic on the Stern–Brocot tree. $\endgroup$ 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
    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
    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$
    – whacka
    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

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.