n_1$ \ {\bf or} \ $m_2
m'/n'$ and $N=\bigl((n+N)/n'\bigr)n'-n\ge\hat n>\bigl((n+N)/n'-1\bigr)n'-n
=N-n'\ge0$.
So we have $\hat m/\hat n\ge m''/n''$. If equality doesn't hold, we have
$n''=(\hat mn'-m'\hat n)n''=n'(\hat mn''-m''\hat n)+\hat n(m''n'-m'n'')
\ge n'+\hat n>N$, a contradiction.\par
Incidentally, this exercise implies that $(m+m'')/(n+n'')=m'/n'$, although
the former fraction is not always reduced.
\source{[|knuth1|, exercise 1.3.2--19].}
\ex:
What binary number corresponds to~$e$, in the binary $\leftrightarrow$
Stern--Brocot correspondence? (Express your answer as an infinite sum;
you need not evaluate it in closed form.)
\answer \def\\#1 {2^{-#1}}$\\1 +\\2 +\\3 -\\6 -\\7 +\\12 +\\13 -\\20
-\\21 +\\30 +\\31 -\\42 -\\43 +\cdots\,$ can be written
\begindisplay
\half+3\sum_{k\ge0}\bigl(2^{-4k^2-6k-3}-2^{-4k^2-10k-7}\bigr)\,.
\enddisplay
This sum, incidentally, can be expressed in closed form using the ``"theta
function"'' $\theta(z,\lambda)=\sum_ke^{-\pi\lambda k^2+2izk}$; we have
\begindisplay
\textstyle e\;\leftrightarrow\;\half+{3\over8}\theta({4\over\pi}\ln 2,\,
3i\ln 2)-{3\over128}\theta({4\over\pi}\ln 2,\,5i\ln 2)\,.
\enddisplay
\ex:
Using only the methods of this chapter,
show that if "Fermat's Last Theorem" \eq(|fermat-last|) were false,
the least $n$ for which it fails would have to be prime. (You may assume that
\eq(|fermat-last|) holds when $n=4$.) Furthermore, if $a^p+b^p=c^p$
is the smallest counterexample, show that
\begindisplay \postdisplaypenalty=10000
a+b=\cases{m^p,&if $p\ndivides c$,\cr
\noalign{\smallskip}
p^{p-1}m^p,&if $p\divides c$,\cr}
\enddisplay
for some integer $m$.
Thus $c\ge m^p\!/2$ must be really huge.
\Hint: Let $x=a+b$, and note that
$\gcd\bigl(x,(a^p+(x-a)^p)/x\bigr)=\gcd(x,pa^{p-1})$.
\answer Any $n>2$ either has a prime divisor $d$ or is divisible
by $d=4$. In either case, a solution with exponent~$n$ implies
\g I have discovered a wonderful proof of Fermat's Last Theorem,
but there's no room for it here.\g
a solution $(a^{n/d})^d+(b^{n/d})^d=(c^{n/d})^d$
with exponent~$d$. Since $d=4$ has no solutions, $d$~must be prime.
\par The hint follows from the binomial theorem, since $(a^p+(x-a)^p)/x\=
pa^{p-1}$ (mod~$x$) when $p$ is odd. The smallest counterexample,
if \equ(4.|fermat-last|) fails, has $a\rp x$. If $x$ is not
divisible by~$p$ then $x$ is relatively prime to $c^p\!/x$; this means that
whenever $q$ is prime and $q^e\edivides x$ and $q^f\edivides c$, we have
$e=fp$. Hence $x=m^p$ for some~$m$. On the other hand
if $x$ is divisible by~$p$, then $c^p\!/x$ is divisible
by $p$ but not by $p^2$, and $c^p$ has no other factors in common with~$x$.
\source{"Barlow" [|barlow|]; "Abel" [|abel|].}
\ex:
The {\it "Peirce sequence"\/ $\Pscr_N$ of order\/ $N$} is an infinite
string of fractions separated by `$<$' or `$=$' signs, containing all
the nonnegative fractions $m/n$ with $m\ge0$ and $n\le N$ (including
fractions that are not reduced). It is defined recursively by starting
with
\begindisplay \def\\#1{{#1\over1}{<}}
\Pscr_1=\textstyle
\\0\\1\\2\\3\\4\\5\\6\\7\\8\\9\\{10}\cdots\,.
\enddisplay
For $N\ge1$, we form $\Pscr_{N+1}$ by inserting two symbols just
before the $kN$th symbol of $\Pscr_N$, for all $k>0$. The two inserted
symbols are
\begindisplay
&{k-1\over N+1}\quad=\,\,,\qquad&\hbox{if $kN$ is odd};\cr
&\Pscr_{N,kN}\quad{k-1\over N+1}\,,\qquad&\hbox{if $kN$ is even}.\cr
\enddisplay
Here $\Pscr_{N,j}$ denotes the $j$th symbol of $\Pscr_N$, which
will be either `$<$' or `$=$' when $j$ is even; it will be a fraction
when $j$ is odd. For example,
\begindisplay \def\\#1#2#3{{#1\over#2}{#3}} \openup2pt
&\textstyle\Pscr_2\!=\!
\\02=\\01<\\12<\\22=\\11<\\32<\\42=\\21<\\52<\\62=\\31<\\72<\\82=\\41<\\92<
\\{10}2=\\51<\cdots\,;\cr
&\textstyle\Pscr_3\!=\!
\\02=\\03=\\01<\\13<\\12<\\23<\\22=\\33=\\11<\\43<\\32<\\53<\\42=\\63=\\21<
\\73<\\52<\cdots\,;\cr
&\textstyle\Pscr_4\!=\!
\\02=\\04=\\03=\\01<\\14<\\13<\\24=\\12<\\23<\\34<\\22=\\44=\\33=\\11<\\54<
\\43<\\64=\cdots\,;\cr
&\textstyle\Pscr_5\!=\!
\\02=\\04=\\05=\\03=\\01<\\15<\\14<\\13<\\25<\\24=\\12<\\25<\\23<\\34<\\45<
\\22=\\44=\cdots\,;\cr
&\textstyle\Pscr_6\!=\!
\\02=\\04=\\06=\\05=\\03=\\01<\\16<\\15<\\14<\\26=\\13<\\25<\\24=\\36=\\12<
\\35<\\46=\cdots\,.\cr
\enddisplay
(Equal elements occur in a slightly peculiar order.) Prove that the `$<$'
and `$=$' signs defined by the rules above correctly describe the
relations between adjacent fractions in the Peirce sequence.
\answer Equal fractions in $\Pscr_N$ appear in
``"organ-pipe order"'':
\begindisplay \def\\#1{{#1m\over#1n}}
\\2,\,\\4,\,\ldots,\,\\r,\,\ldots,\,\\3,\,\\{}\,.
\enddisplay
Suppose that $\Pscr_N$ is correct; we want to prove that $\Pscr_{N+1}$ is
correct. This means that if $kN$ is odd, we want to show that
\begindisplay
{k-1\over N+1}=\Pscr_{N,kN}\,;
\enddisplay
if $kN$ is even, we want to show that
\begindisplay
\Pscr_{N,kN-1}\;\Pscr_{N,kN}\;{k-1\over N+1}\;\Pscr_{N,kN}\;\Pscr_{N,kN+1}\,.
\enddisplay
In both cases it will be helpful to know the number of fractions that
are strictly less than $(k-1)/(N+1)$
in $\Pscr_N$; this is
\begindisplay
\sum_{n=1}^N\sum_m\Bigi[\displaystyle0\le{m\over n}<{k-1\over N+1}\Bigr]
&=\sum_{n=1}^N\biggl\lceil{(k-1)n\over N+1}\biggr\rceil
=\sum_{n=0}^N\biggl\lfloor{(k-1)n+N\over N+1}\biggr\rfloor\cr
&={(k-2)N\over2}+{d-1\over2}+d\left\lfloor N\over d\right\rfloor\cr
\enddisplay
by \equ(3.|f-progression|), where $d=\gcd(k-1,N+1)$. And this reduces
to $\half(kN-d+1)$, since $N\bmod d=d-1$.\par
Furthermore, the number of fractions equal to $(k-1)/(N+1)$ in
$\Pscr_N$ that should precede it in $\Pscr_{N+1}$ is
$\half\bigl(d-1-\[\hbox{$d$~even}]\bigr)$, by the nature of organ-pipe order.
\par If $kN$ is odd, then $d$ is even and $(k-1)/(N+1)$ is preceded by
$\half(kN-1)$ elements of $\Pscr_N$; this is just the correct
number to make things
work. If $kN$ is even, then $d$ is odd and $(k-1)/(N+1)$ is preceded by
$\half(kN)$ elements of~$\Pscr_N$. If $d=1$, none of these equals $(k-1)/(N+1)$
and $\Pscr_{N,kN}$ is `$<$'; otherwise $(k-1)/(N+1)$ falls between two
equal elements and $\Pscr_{N,kN}$ is `$=$'.
(C.\thinspace S. "Peirce" [|peirce-tree|] independently discovered
the "Stern--Brocot tree" at about the same time as he discovered
$\Pscr_N$.)
\source{"Peirce" [|peirce-seq|].}
\subhead Research problems
\ex:
Are the "Euclid numbers" $e_n$ all "squarefree"?
\answer The analogous question for the (analogous) Fermat numbers $f_n$
\g\noindent\llap{``}No square less than $25\times10^{14}$ divides a Euclid number.''\par
\hfill\dash---Ilan "Vardi"\g
is a famous unsolved problem. This one might be easier or harder.
\ex:
Are the "Mersenne numbers" $2^p-1$ all "squarefree"?
\answer It is known that no square less than $36\times10^{18}$ divides
a Mersenne number or Fermat number.
But there has still been no proof of "Schinzel"'s
conjecture that there exist infinitely many squarefree Mersenne numbers.
It is not even known if there are infinitely many~$p$ such that
$p\edivides(a\pm b)$, where all prime factors of $a$ and~$b$ are~$\le31$.
\source{"Ribenboim" [|ribenboim|];
"Sierpi\'nski"~[|sierpinski-probs|, problem $\rm P_{10}^2$].}
\ex:
Prove or disprove that $\max_{1\le j