|
|
|
Viewing Version
3
of
'any rational number is a sum of unit fractions'
|
[ view 'any rational number is a sum of unit fractions'
|
back to history
]
| Title of object: |
any rational number is a sum of unit fractions |
| Canonical Name: |
AnyRationalNumberIsASumOfUnitFractions |
| Type: |
Derivation |
| Created on: |
2002-06-23 03:10:54 |
| Modified on: |
2004-02-16 02:03:44 |
| Classification: |
msc:11A67 |
| Keywords: |
greedy algorithm |
| Synonyms: |
any rational number is a sum of unit fractions=Egyptian algorithm |
Revision comment (for changes between this and next version):
Changes for correction #3353 ('broken').
\qed is broken; changed to use proof environment.
This is probably a PlanetMath breakage rather than specific to this writeup. |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newcommand{\Prob}[2]{\mathbb{P}_{#1}\left\{#2\right\}}
\newcommand{\Expect}{\mathbb{E}}
\newcommand{\norm}[1]{\left\|#1\right\|}
% Some sets
\newcommand{\Nats}{\mathbb{N}}
\newcommand{\Ints}{\mathbb{Z}}
\newcommand{\Rats}{\mathbb{Q}}
\newcommand{\Reals}{\mathbb{R}}
\newcommand{\Complex}{\mathbb{C}}
%%%%%% END OF SAVED PREAMBLE %%%%%% |
Content:
\subsubsection*{Representation}
Any rational number $\frac{a}{b}\in\Rats$ between 0 and 1 can be represented as a sum of different unit fractions. This result was known to the Egyptians, whose way for representing rational numbers was as a sum of different unit fractions.
The following greedy algorithm can represent any $0\le \frac{a}{b} <1$ as such a sum:
\begin{enumerate}
\item Let
n = \left \lceil \frac{b}{a} \right \rceil
be the smallest natural number for which $\frac{1}{n} \le \frac{a}{b}$. If $a=0$, terminate.
\item Output $\frac{1}{n}$ as the next term of the sum.
\item Continue from step 1, setting
$$\frac{a'}{b'} = \frac{a}{b}-\frac{1}{n}.$$
\end{enumerate}
\subsubsection*{Proof of correctness}
\begin{proof}
The algorithm can never output the same unit fraction twice. Indeed, any $n$ selected in step 1 is at least 2, so $\frac{1}{n-1} < \frac{2}{n}$ -- so the same $n$ cannot be selected twice by the algorithm, as then $n-1$ could have been selected instead of $n$.
It remains to prove that the algorithm terminates. We do this by induction on $a$.
\begin{description}
\item[For $a=0$:] The algorithm terminates immediately.
\item[For $a>0$:]
The $n$ selected in step 1 satisfies
$$b \le an < b+a.$$
\frac{a}{b}-\frac{1}{n} = \frac{an-b}{bn},
and $0 \le an-b < a$ -- by the induction hypothesis, the algorithm terminates for $\frac{a}{b}-\frac{1}{n}$.
\end{description}
\end{proof}
\subsubsection*{Problems}
\begin{enumerate}
\item
The greedy algorithm always works, but it tends to produce unnecessarily large denominators. For instance, $$\frac{47}{60}=\frac{1}{3}+\frac{1}{4}+\frac{1}{5},$$
but the greedy algorithm selects $\frac{1}{2}$, leading to the representation
\frac{47}{60}=\frac{1}{2}+\frac{1}{4}+\frac{1}{30}.
\item
The representation is \emph{never} unique. For instance, for any $n$ we have the representations
\frac{1}{n} = \frac{1}{n+1} + \frac{1}{n\cdot(n+1)}
So given any one representation of $\frac{a}{b}$ as a sum of different unit fractions we can take the largest denominator appearing $n$ and replace it with two (larger) denominators. Continuing the process indefinitely, we see infinitely many such representations, always.
7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/5619/l2h/img34.png HTTP/1.1" 200 288 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/2339/l2h/img15.png HTTP/1.1" 200 248 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/2339/l2h/img16.png HTTP/1.1" 200 244 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/5619/l2h/img35.png HTTP/1.1" 200 288 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/2339/l2h/img17.png HTTP/1.1" 200 623 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/5619/l2h/img33.png HTTP/1.1" 200 305 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:19 -0400] "GET /cache/objects/2339/l2h/img18.png HTTP/1.1" 200 244 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/1238/l2h/img2.png HTTP/1.1" 200 423 "http://planetmath.org/encyclopedia/GaussianElimination.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; .NET CLR 1.1.4322)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/2339/l2h/img20.png HTTP/1.1" 200 619 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/5619/l2h/img36.png HTTP/1.1" 200 288 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/1238/l2h/img3.png HTTP/1.1" 200 1431 "http://planetmath.org/encyclopedia/GaussianElimination.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; .NET CLR 1.1.4322)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/5619/l2h/img37.png HTTP/1.1" 200 384 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/2339/l2h/img19.png HTTP/1.1" 200 1308 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/2339/l2h/img21.png HTTP/1.1" 200 582 "http://planetmath.org/encyclopedia/NegativeHypergeometricDistribution.html" "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)"
127.0.0.1 - - [26/Jul/2004:06:44:20 -0400] "GET /cache/objects/1238/l2h/img4.png HTTP/1.1" 200 372 "http://planetmath.org/encyclopedia/GaussianElimination.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; .NET CLR 1.1.4322)"
127.0.0.1 - - [26/Jul/2004:06:44:21 -0400] "GET /cache/objects/5619/l2h/img39.png HTTP/1.1" 200 230 "http://planetmath.org/encyclopedia/DirectLimit.html" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Hotbar 4.4.7.0)"
127.0.0.1 - - [26/Jul/2004:06:44:21 -0400] "GET /cache/objects/1238/l2h/img5.png HTTP/1.1" 200 247 "http://planetmath.org/encyclopedia/GaussianElimination.html" "Mozilla/4\end{enumerate} |
|
|
|
|
|
