\ansno4.1:
 $1$, $2$, $4$, $6$, $16$, $12$.

\ansno4.2:
 Note that $m_p+n_p=\min(m_p,n_p)+\max(m_p,n_p)$. The recurrence
$\lcm(m,n)=\bigl(n/(n\bmod m)\bigr)\lcm(n\bmod m,m)$ is true but not
really advisable for computing lcm's; the best way known to compute
$\lcm(m,n)$ is to compute $\gcd(m,n)$ first and then to divide $mn$
by the gcd.

\ansno4.3:
 This holds if $x$ is an integer, but $\pi(x)$ is defined
for all real~$x$. The correct formula,
\begindisplay
\pi(x)-\pi(x-1)=\bigl(\hbox{$\lfloor x\rfloor$ is prime}\bigr)\,,
\enddisplay
is easily verified.

\ansno4.4:
 Between $1\over0$ and $0\over-1$ we'd have a left-right reflected
Stern-Peirce tree with all denominators negated, etc. So the result is
{\it all\/} fractions $m/n$ with $m\rp n$. The condition $m'n-mn'=1$
still holds throughout the construction. [This is called the
{\it Stern-Peirce wreath}, because we can conveniently regard the final
$0\over1$ as identical to the first~$0\over1$, thereby joining the
trees in a cycle at the top. The Stern-Peirce wreath has interesting
applications to computer graphics because it represents all rational
directions in the plane.]
\source{[|knuthd|, \S526].}

\ansno4.5:
 $L↑k={1\,k\choose0\,1}$ and $R↑k={1\,0\choose k\,1}$; this
holds even when $k<0$. (We will find a general formula for any product
of $L$'s and $R$'s in Chapter~6.)

\ansno4.6:
 $a=b$. (Chapter 3 defined $x\bmod0=x$,
primarily so that this would be true.)

\ansno4.7:
 We need $m\bmod10=0$, $m\bmod9=k$, and $m\bmod8=1$. But $m$
can't be both even and odd.

\ansno4.8:
 We want $10x+6y\=10x+y$ \tmod{15}, hence $5y\=0$ \tmod{15},
hence $y\=0$ \tmod3. We must have $y=3$, and $x$ can be arbitrary.

\ansno4.9:
 $3↑{2k+1}\bmod4=3$, so $(3↑{2k+1}-1)/2$ is odd. The
stated number is divisible by $(3↑7-1)/2$ and $(3↑{11}-1)/2$
(and by other numbers).

\ansno4.10:
 $999(1-{1\over3})(1-{1\over37})=738$.

\ansno4.11:
 $\sigma(0)=1$; $\sigma(1)=-1$; $\sigma(n)=0$ for $n>1$.
(Generalized M\"obius functions defined on arbitrary partially ordered
structures have interesting and important properties first explored by
Rota [|rota-mobius|].)

\ansno4.12:
 $\sum_{d\divides m}\sum_{k\divides d}\mu(d/k)g(k)=
\sum_{k\divides m}\sum_{d\divides(m/k)}\mu(d)g(k)=
\sum_{k\divides m}g(k)\*\(m/k=1)=g(m)$,
by \eq(|swap-div|) and \eq(|interch-div|).

\ansno4.13:
 (a) $n_p\le1$ for all $p$; (b) $\mu(n)\ne0$.

\ansno4.14:
 True when $k>0$. Use \eq(|prod-exp|), \eq(|gcd-exp|), \eq(|lcm-exp|).

\ansno4.15:
 No. For example, $e_n\bmod5=(2\,{\rm or}\,3)$;
$e_n\bmod11=(2,3,7,{\rm or}\,10)$.

\ansno4.16:
 $1/e_1+1/e_2+\cdots+1/e_n=1-1/e_n(e_n-1)=1-1/(e_{n+1}-1)$.
\source{[|sylvester|].}

\ansno4.17:
 We have $f_n\bmod f_m=2$, hence $\gcd(f_n,f_m)=\gcd(2,f_m)=1$.
(Incidentally, the relation
$f_n=f_0f_1\ldots f_{n-1}+2$ is very similar to the recurrence that
defines the Euclid numbers $e_n$.)

\ansno4.18:
 If $n=qm$ and $q$ is odd, $2↑n+1=(2↑m+1)(2↑{n-m}-2↑{n-2m}+\cdots
-2↑m+1)$.

\ansno4.19:
 Let $p_1=2$ and $p_n$ the smallest prime greater than $2↑{p_{n-1}}$.
Then $2↑{p_{n-1}}<p_n<2↑{p_{n-1}+1}$, and it follows that we can take
$b=\lim_{n\to\infty}\lg↑{(n)}p_n$ where $\lg↑{(n)}$ is the function $\lg$
iterated $n$~times. The stated numerical value comes from $p_2=5$,
$p_3=37$. It turns out that $p_4=2↑{37}+9$, and this gives the more
precise value
\begindisplay
b\approx1.2516475977905
\enddisplay
(but no clue about $p_5$).
\source{[|bertrand|], [|chebyshev|], [|wright-primes|].}

\ansno4.20:
 By Bertrand's postulate, $P_n<10↑n$. Let
\begindisplay
K=\sum_{k\ge1}10↑{-k↑2}P_k=.200300005\ldots\,\,.
\enddisplay
Then $10↑{n↑2}K\=P_n+{\rm fraction}$ \tmod{10↑{2n-1}}.

\ansno4.21:
 The first sum is $\pi(n)$, since the summand is $(k+1$ is prime$)$.
The inner sum in the second is $\sum_{1\le k<m}\(k\divides m)$, so it is
greater than~$1$ if and only if $m$ is composite; again we get $\pi(n)$.
Finally $\bigl\lceil\{m/n\}\bigr\rceil=\(n\ndivides m)$,
so the third sum is an application of Wilson's theorem. To evaluate $\pi(n)$
by any of these formulas is, of course, sheer lunacy.
\source{[|texbook|, pp.~148--149].}

\ansno4.22:
 $(b↑{mn}-1)/(b-1)=\bigl((b↑m-1)/(b-1)\bigr)(b↑{mn-m}+\cdots+1)$.
[The only prime numbers of the form $(10↑p-1)/9$ for $p<2000$ occur when
$p=2$, $19$, $23$, $317$, $1031$.]
\source{[|brillhart|], [|williams-dubner|].}

\ansno4.23:
 $\rho(2k+1)=0$; $\rho(2k)=\rho(k)+1$, for $k\ge1$. By induction
we can show that $\rho(n)=\rho(n-2↑m)$, if $n>2↑m$ and $m>\rho(n)$.
The $k$th Hanoi move is disk $\rho(k)$, if we number the disks $0$,
$1$, \dots,~$n-1$. This is clear if $k$ is a power of~$2$. And if
$2↑m<k<2↑{m+1}$, we have $\rho(k)<m$; moves $k$ and $k-2↑m$ correspond
in the sequence that transfers $k+1$ disks in $T_k+1+T_k$ steps.
\source{[|crowe|].}

\ansno4.24:
 The digit that contributes $dp↑m$ to $n$ contributes
$dp↑{m-1}+\cdots+d=d(p↑m-1)/(p-1)$ to $\epsilon_p(n!)$, hence
$\epsilon_p(n!)=\bigl(n-\nu_p(n)\bigr)/(p-1)$.
\source{[|legendre-theorie|, second edition, introduction].}

\ansno4.25:
 $m\edivides n\iff m_p=0$ or $m_p=n_p$, for all $p$. It follows that
(a)~is true. But (b) fails, in our favorite example $m=12$, $n=18$.
(This is a common fallacy.)

\ansno4.26:
 Yes, since ${\scr G}_N$ is a subtree of the Stern-Peirce tree.
\source{[|knuth2|, exercise 4.5.3--43].}

\ansno4.27:
 Extend the shorter string with $M$'s until both strings are
the same length, then use dictionary order. For example, the topmost
levels of the tree are $LL<LM<LR<MM<RL<RM<RR$.
(Another solution is to append the infinite string $RL↑\infty$ to both
inputs, and to keep comparing until finding $L<R$.)

\ansno4.28:
 We need to use only the first part of the representation:
\begindisplay
\unitlength=15pt
\countdef\m=0 \countdef\mp=2 \countdef\n=4 \countdef\np=6
\m=0 \mp=1 \n=1 \np=0
\def\\#1{\if #1R\advance\m\mp \advance\n\np{\number\m\over\number\n}
 \else\advance\mp\m \advance\np\n{\number\mp\over\number\np}\fi
 ,\mskip-8mu\raise\unitlength\hbox{$\scriptstyle#1$}}
\textstyle
\\R\\R\\R\\L\\L\\L\\L\\L\\L\\L\\R\\R\\R\\R\\R\\R
\ldots\,.
\enddisplay
Note that $4\over1$ appears because it is a better upper bound than $1\over0$,
not because it's closer than $3\over1$. Similarly, $25\over8$ is a better
lower bound than $3\over1$. The simplest upper bounds and the simplest
lower bounds all appear,
but the next really good approximation doesn't occur until just before the
string of $R$'s switches back to $L$.

\ansno4.29:
 $1/\alpha$. To get $1-x$ from~$x$ in binary notation,
 we interchange $0$ and~$1$;
to get $1/\alpha$ from~$\alpha$ in Stern-Peirce notation,
 we interchange $L$ and $R$. (The
finite cases must also be considered, but they must work since the
correspondence is order-preserving.)

\ansno4.30:
 The $m$ integers $x\in[A,A+m)$ are different mod~$m$, hence their
residues $(x\bmod m_1,\ldots,x\bmod m_r)$ run through all $m_1\ldots m_r=m$
possible values, one of which must be $(a_1\bmod m_1,\ldots,a_r\bmod m_r)$
by the pigeonhole principle.

\ansno4.31:
 A number in radix-$b$ notation is divisible by~$d$ if and only
if the sum of its digits is divisible by~$d$, whenever $b\=1$ \tmod d.
This follows because $(a_m\ldots a_0)_b=a_mb↑m+\cdots+a_0b↑0\=a_m+\cdots+a_0$.
\source{[|pascal-digits|].}

\ansno4.32:
 The $\phi(m)$ numbers $\{\,kn\bmod m\mid k\rp m$ and $0\le k<m\,\}$
are the numbers $\{\,k\mid k\rp m$ and $0\le k<m\,\}$ in some order.
Multiply them together and divide by $\prod_{0\le k<m,\,k\rp m}k$.

\ansno4.33:
 Clearly $h(1)=1$. If $m\rp n$ then $h(mn)=
\sum_{d\divides mn}f(d)g(mn/d)=\sum_{c\divides m,d\divides n}f(cd)
 g\bigl((m/c)(n/d)\bigr)=\sum_{c\divides m}\sum_{d\divides n}f(c)g(m/c)
 f(d)g(n/d)$; this is $h(m)h(n)$ since $c\rp d$ for every term in the sum.

\ansno4.34:
 $g(m)=\sum_{d\divides m}f(d)=\sum_{d\divides m}f(m/d)
=\sum_{d\ge1}f(m/d)$ if $f(x)$ is zero when $x$ is not an integer.

\ansno4.35:
 The base cases are
\begindisplay
I(0,n)=0\,;\qquad I(m,0)=1\,.
\enddisplay
When $m,n>0$, there are two rules, where the first is trivial if $m>n$
and the second is trivial if $m<n$:
\begindisplay
I(m,n)&=I(m,n\bmod m)-\lfloor n/m\rfloor I(n\bmod m,m)\,;\cr
I(m,n)&=I(m\bmod n, n)\,.
\enddisplay

\ansno4.36:
 A factorization of any of the given quantities into nonunits
must have $m↑2-10n↑2=\pm2$ or $\pm3$, but this is impossible mod~$10$.
\source{[|hardy-wright|, \S14.5].}

\ansno4.37:
 Let $a_n=2↑{-n}\ln(e_n-\half)$ and $b_n=2↑{-n}\ln(e_n+\half)$.
Then
\begindisplay
\textstyle e_n=\lfloor E↑{2↑n}+\half\rfloor\iff a_n\le\ln E<b_n\,.
\enddisplay
Since $a_{n-1}<a_n<b_n<b_{n-1}$, we can take $E=\lim_{n\to\infty}e↑{a_n}$.
In fact, it turns out that
\begindisplay
E↑2={3\over2}\prod_{n\ge1}\left(1+{1\over(2e_n-1)↑2}\right)↑{\!1/2↑n},
\enddisplay
a product that converges rapidly to $(1.26408473530530111)↑2$.
But this doesn't tell us what $e_n$ is, unless we can find another expression
for~$E$ that doesn't depend on Euclid's numbers.
\source{[|aho-sloane|].}

\ansno4.38:
 $a↑n-b↑n=(a↑m-b↑m)(a↑{n-m}b↑0+a↑{n-2m}b↑m+\cdots
 +a↑{n\bmod m}b↑{n-m-n\bmod m})+b↑{\lfloor n/m\rfloor}(a↑{n\bmod m}-b↑{n\bmod m})$.
\source{[|lucas-gcd|].}

\ansno4.39:
 Let $f(n)=\prod_{1\le k\le n,\,p\ndivides k}k=n!/p↑{\lfloor n/p\rfloor}
\lfloor n/p\rfloor!$ and $g(n)=n!/p↑{\epsilon_p(n!)}$. Then
\begindisplay
g(n)=f(n)f\bigl(\lfloor n/p\rfloor\bigr)f\bigl(\lfloor n/p↑2\rfloor\bigr)
 \ldots\, =f(n)g\bigl(\lfloor n/p\rfloor\bigr)\,.
\enddisplay
Also $f(n)\=a_0!(p-1)!↑{\lfloor n/p\rfloor}\=a_0!(-1)↑{\lfloor n/p\rfloor}$
\tmod p, and $\epsilon_p(n!)=\lfloor n/p\rfloor +
\epsilon_p\bigl(\lfloor n/p\rfloor!\bigr)$. These recurrences make it easy
to prove the result by induction. (Several other solutions are possible.)
\source{[|stickelberger|].}

\ansno4.40:
 (a)~If $n↑2\=-1$ \tmod p then $(n↑2)↑{(p-1)/2}\=-1$; but
Fermat says it's $+1$. (b)~Let $n=\bigl((p-1)/2\bigr)!$; we have
$n\=(-1)↑{(p-1)/2}\prod_{1\le k<p/2}(p-k)=(p-1)!/n$, hence $n↑2\=(p-1)!$.
\source{??}

\ansno4.41:
 First we observe that $k\rp l\iff k\rp l+ak$ for any integer~$a$,
since $\gcd(k,l)=\gcd(k,l+ak)$ by Euclid's algorithm. Now
$\bigl(m\rp n$ and $n'\rp n\bigr)\iff mn'\rp n\iff mn'+nm'\rp n$. Similarly
$\bigl(m'\rp n'$ and $n\rp n'\bigr)\iff mn'+nm'\rp n'$. Hence
$\bigl(m\rp n$ and $m'\rp n'$ and $n\rp n'\bigr)\iff mn'+nm'\rp n'$.
\source{[|knuth2|, exercise 4.5.1--6].}

\ansno4.42:
 We want to multiply by $L↑{-1}R$, then by $R↑{-1}L↑{-1}RL$, then
$L↑{-1}R$, then $R↑{-2}L↑{-1}RL↑2$, etc.; the $n$th multiplier is
$R↑{-\rho(n)}L↑{-1}RL↑{\rho(n)}$, since we must cancel $\rho(n)$ $R$'s.
And $R↑{-m}L↑{-1}RL↑m=\setmathsize{\scriptstyle 2m+1}
{0\,\mathsize{\scriptstyle\hfil-1}\choose1\,2m+1}$.

\ansno4.43:
 The simplest rational number that lies in
\begindisplay
\textstyle[\mskip1mu.3155,.3165)=\bigl[{631\over2000},{633\over2000}\bigr)
\enddisplay
can be found by looking at
the Stern-Peirce representations of $631\over2000$ and $633\over2000$
and stopping just before the former has~$L$ where the latter has~$R$:
\begindisplay
&(m_1,n_1,m_2,n_2):=(631,2000,633,2000);\hidewidth\cr
&\hbox{{\bf while} \ $m_1>n_1$ \ {\bf or} \ $m_2<n_2$ \ {\bf do}}\hidewidth\cr
&\quad\hbox{\bf if} \ m_2<n_2 \ &\hbox{\bf then} \ &\bigl(\hbox{output}(L); \
(n_1,n_2):=(n_1,n_2)-(m_1,m_2)\bigr)\cr
&&\hbox{\bf else} \ &\bigl(\hbox{output}(R); \
(m_1,m_2):=(m_1,m_2)-(n_1,n_2)\bigr)\,.\cr
\enddisplay
The output is $LLLRRRRR={6\over19}\approx.3158$. Incidentally, an
average of $.334$ implies at least 287 at bats.
\source{[|knuth2|, exercise 4.5.3--39].}

\ansno4.44:
 $x↑2\=x$ \tmod{10↑n} $\iff$ $x(x-1)\=0$ \tmod{2↑n} and
$x(x-1)\=0$ \tmod{5↑n} $\iff$ $x\bmod2↑n=(0\,{\rm or}\,1)$ and
$x\bmod5↑n=(0\,{\rm or}\,1)$. (The last step is justified because
$x(x-1)\bmod5=0$ implies that either $x$ or~$x-1$ is a multiple of~$5$,
in which case the other factor is relatively prime to $5↑n$ and can
be divided from the congruence.)\par
So there are at most four solutions, of which two ($x=0$ and $x=1$)
don't qualify for the title ``$n$-digit number'' unless $n=1$.
The other two solutions have the forms $x$ and $10↑n+1-x$, and at
least one of these numbers is $\ge10↑{n-1}$.
 When $n=4$ the other solution
is $10001-9376=625$, not a $4$-digit number. We expect to get two
$n$-digit solutions for about $9/10$ of all~$n$, but this conjecture
has not been proved.
\par (Such self-reproducing numbers
have been called ``automorphic.'')
\source{[|knuth2|, exercise 4.3.2--13].}

\ansno4.45:
 (a) If $j'j-k'k=\gcd(j,k)$, we have $n↑{k'k}n↑{\gcd(j,k)}=n↑{j'j}\=1$
and $n↑{k'k}\=1$. (b)~Let $n=pq$, where $p$ is the smallest prime
divisor of~$n$.
If $2↑n\=1$ \tmod n then $2↑n\=1$ \tmod p. Also $2↑{p-1}\=1$ \tmod p, hence
$2↑{\gcd(p-1,n)}\=1$ \tmod p. But $\gcd(p-1,n)=1$ by definition of~$p$.

\ansno4.46:
 If $n↑{m-1}\=1$ \tmod m we must have $n\rp m$. If
$n↑k\=n↑j$ for some $1\le j<k<m$, then $n↑{k-j}\=1$ because we can
divide by~$n↑j$. Therefore if the numbers $n↑1\bmod m$, \dots,
$n↑{m-1}\bmod m$ are not distinct, there is a $k<m-1$ with $n↑k\=1$.
The least such $k$ divides $m-1$, by exercise |order-mod-n|(a).
But then $kq=(m-1)/p$ for some prime~$p$ and some positive integer~$q$;
this is impossible, since $n↑{kq}\not\=1$. Therefore the numbers
$n↑1\bmod m$, \dots, $n↑{m-1}\bmod m$ are distinct and relatively prime to~$m$.
Therefore the numbers $1$, \dots,~$m-1$ are relatively prime to~$m$,
and $m$ must be prime.
\source{[|lehmer-primality|].}

\ansno4.47:
 By pairing numbers up with their inverses, the product reduces to
$\prod_{1\le n<m,\,n↑2\bmod m=1}n$, modulo~$m$, and we have studied the
solutions to $n↑2\bmod m=1$. By residue arithmetic we find that the
result is $m-1$ if $m=4$, $p↑k$, or $2p↑k$ ($p>2$); otherwise it's~$+1$.
\source{[|gauss-disq|, \S78], [|crelle|].}

\ansno4.48:
 (a) Either $m<n$ ($\Phi(N-1)$ cases) or $m=n$ (one case) or
$m>n$ ($\Phi(N-1)$ again). Hence $R(N)=2\Phi(N-1)+1$.
(b)~From \eq(|bigphi-gen|) we get
\begindisplay
2\Phi(N-1)+1=1+\sum_{d\ge1}\mu(d)\lfloor N/d\rfloor\lfloor N/d-1\rfloor\,;
\enddisplay
hence the stated result holds if and only if
\begindisplay
\sum_{d\ge1}\mu(d)\lfloor N/d\rfloor=1\,,\qquad\hbox{for $N\ge1$}.
\enddisplay
And this is a special case of \eq(|mobius-real-inversion|) if we
set $f(x)=(x\ge1)$.

\ansno4.49:
 (a) If $f$ is any function,
\begindisplay \openup3pt
\sum_{0\le k<m}f(k)
&=\sum_{d\divides m}\sum_{0\le k<m}f(k)\bigi(d=\gcd(k,m)\bigr)\cr
&=\sum_{d\divides m}\sum_{0\le k<m}f(k)\bigi(k/d\rp m/d\bigr)\cr
&=\sum_{d\divides m}\sum_{0\le k<m/d}f(kd)\bigi(k\rp m/d\bigr)\cr
&=\sum_{d\divides m}\sum_{0\le k<d}f(km/d)\bigi(k\rp d\bigr)\,;\cr
\enddisplay
we've seen a special
case of this in the derivation of \eq(|necklaces|). An analogous derivation
holds for $\prod$ instead of~$\sum$. Thus we have
\begindisplay
z↑m-1=\prod_{0\le k<m}(z-\omega↑k)=\prod_{d\divides m}\,
 \prod\twoconditions{0\le k<d}{k\rp d}(z-\omega↑{km/d})
 =\prod_{d\divides m}\Psi_d(z)
\enddisplay
because $\omega↑{m/d}=e↑{2\pi i/d}$.\par
Part (b) follows from part (a) by the analog of \eq(|mobius-inversion|)
for products instead of sums. Incidentally, this formula shows that
$\Psi_m(z)$ has integer coefficients, since $\Psi_m(z)$ is obtained
by multiplying and dividing polynomials whose leading coefficient is~$1$.

\ansno4.50:
 $(x_1+\cdots+x_n)↑p=\sum_{k_1+\cdots+k_n=p}(p!/k_1!\ldots k_n!)
x_1↑{k_1}\ldots x_n↑{k_n}$, and the coefficient is divisible by~$p$
unless some $k_j=p$. Hence $(x_1+\cdots+x_n)↑p\=x_1↑p+\cdots+x_n↑p$
\tmod p. Set all the $x$'s to $1$, obtaining $n↑p\=n$.

\ansno4.51:
 First show that if $m\ge6$ and $m$ is not prime then $(m-2)!
\=0$ \tmod m. (If $m=p↑2$, the product for $(m-2)!$ includes $p$ and $2p$;
otherwise it includes $d$ and $m/d$ where $d<m/d$.) Next consider cases:
\par Case 0, $n<5$. The condition holds for $n=1$ only.
\par Case 1, $n\ge5$ and $n$ is prime. Then
$(n-1)!/(n+1)$ is an integer and it can't be a multiple of~$n$.
\par Case 2, $n\ge5$, $n$ is composite, and $n+1$ is composite. Then
$n$ and $n+1$ divide $(n-1)!$, and $n\rp n+1$, hence $n(n+1)\divides
(n-1)!$.
\par Case 3, $n\ge5$, $n$ is composite, and $n+1$ is prime. Then $(n-1)!
\=1$ \tmod{n+1} by Wilson's theorem, and
\begindisplay
\bigl\lfloor(n-1)!/(n+1)\bigr\rfloor=\bigl((n-1)!+n\bigr)/(n+1)\,;
\enddisplay
this is divisible by~$n$.
\par Therefore the answer is: $n=1$ or $n\ne4$ is composite.
\source{1973 midterm, inspired by [|d-r-rao|].}

\ansno4.52:
 $\epsilon_2(1000!)>500$ and $\epsilon_5(1000!)=249$, hence
$1000!=a\cdt10↑{249}$ for some even integer~$a$.
Since $1000=(1300)_5$, exercise |factorial-residue| tells us that
$a\cdt2↑{249}=1000!/5↑{249}\=-1$ \tmod5.
Also $2↑{249}\=2$, hence $a\=2$, hence $a\bmod10=2$ or~$7$,
hence the answer is $2\cdt10↑{249}$.
\source{1974 midterm.}

\ansno4.53:
 One way is to prove by induction that $P(2n)/P(n)↑4(n+1)$
is an integer; this stronger result helps the induction go through.
Another way is based on showing that each prime~$p$ divides the numerator
at least as often as it divides the denominator. This reduces to
proving the inequality
\begindisplay
\sum_{k=1}↑{2n}\lfloor k/m\rfloor\ge4\sum_{k=1}↑n\lfloor k/m\rfloor\,,
\enddisplay
which follows from
\begindisplay
\bigl\lfloor(2n-1)/m\bigr\rfloor+\bigl\lfloor 2n/m\bigr\rfloor
 \ge\lfloor n/m\rfloor\,.
\enddisplay
The latter is true when $0\le n<m$, and both sides increase by~$4$ when
$n$ is increased by~$m$.

\ansno4.54:
 The hint is a standard interchange of summation, since
\begindisplay
\sum_{1\le m\le n}(d\divides m)=\sum_{0<k\le n/d}\(m=dk)=\lfloor n/d\rfloor\,.
\enddisplay
Calling the hinted sum $\Sigma(n)$, we have
\begindisplay
\Sigma(m+n)-\Sigma(m)-\Sigma(n)
=\sum_{d\in S(m,n)}\phi(d)\,.
\enddisplay
On the other hand we know from \eq(|phi-sum|) that
$\Sigma(n)=\half n(n+1)$. Hence $\Sigma(m+n)-\Sigma(m)-\Sigma(n)=mn$.
\source{A special case appears in [|amm-phi-problem|].}

\ansno4.55:
 The function $f(m)$ is multiplicative, and when $m=p↑k$
it equals $1+p+\cdots+p↑k$. This is a power of~$2$ if and only if
$p$ is a Mersenne prime and $k=1$. For $k$ must be odd, and in that case
the sum is
\begindisplay
(1+p)(1+p↑2+p↑4+\cdots+p↑{k-1})
\enddisplay
and $(k-1)/2$ must be odd, etc.
The necessary and sufficient condition is that $m$ be a product of
distinct Mersenne primes.
\source{[|sierpinski-2|].}

\ansno4.56:
 It's also true that if $1/x_1+\cdots+1/x_n<1$, then
$1/x_1+\cdots+1/x_n\le1/e_1+\cdots+1/e_n$; see exercise |recip-euclid|.
[I'm still trying to figure out a short proof of this; the second
statement implies the first.]
\source{[|curtiss|].}

\ansno4.57:
 The main point is that $\theta<{2\over3}$. Then we can take
$p_1$ sufficiently large (to meet the conditions below) and $p_n$ to
be the least prime greater than $p_{n-1}↑3$. With this definition let
$a_n=3↑{-n}\ln p_n$ and $b_n=3↑{-n}\ln(p_n+1)$. If we can show that
$a_{n-1}\le a_n<b_n\le b_{n-1}$, we can take $P=\lim_{n\to\infty}e↑{a_n}$
as in exercise~|euclid-sol-proof|. But this is equivalent to
$p_{n-1}↑3\le p_n<(p_{n-1}+1)↑3$. If there's no prime $p_n$ in this
range, there must be a prime~$p<p_{n-1}↑3$ such that $p+cp↑\theta>
(p_{n-1}+1)↑3$. But this implies that $cp↑\theta>3p↑{2/3}$, which is
impossible when $p$~is sufficiently large.\par
We can almost certainly take $p_1=2$, since all available evidence
indicates that the known bounds on gaps between primes are much
weaker than the truth (see exercise |prime-gaps|). Then $p_2=11$,
$p_3=1361$, $p_4=2521008887$, and $1.306377883863<P<1.306377883869$.
\source{[|mills|].}

\ansno4.58:
 Let $\hat m$ and $\hat n$ be the righthand sides; observe that
$\hat mn'-m'\hat n=1$, hence $\hat m\rp\hat n$. Also $\hat m/\hat n>
m'/n'$ and $N=\bigl((n+N)/n')n'-n\ge\hat n>\bigl((n+N)/n'-1)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].}

\ansno4.59:
 \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, 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

\ansno4.60:
 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
-pa↑{p-1}$ is a multiple of~$x$ when $p$ is odd. Assume that
$a\rp x$. If $x$ is not
divisible by~$p$, $x$ is relatively prime to $c↑p/x$, hence $x=m↑p$
for some~$m$. 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$.
\par (The values of $a$, $b$, $c$ must, in fact, be even higher than this
result indicates! Inkeri [|inkeri|] has proved that
\begindisplay
\min(a,b)>\left(2p↑3+p\over\ln(3p)\right)↑p\,.
\enddisplay
A sketch of his proof appears in [|ribenboim|, pages 228--229],
a book that contains an extensive survey of progress on
Fermat's Last Theorem.)
\source{[|barlow|], [|abel|].}

\ansno4.61:
 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
and 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
&= \half(kN-d+1)\,,\quad d\!=\!\gcd(k{-}1,N{+}1),
\enddisplay
by \equ(3.|f-progression|).
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-(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, than $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 `$=$'.

\ansno4.62:
 The analogous question for the (analogous) Fermat numbers $f_n$
is a famous unsolved problem. This one might be easier or harder.

\ansno4.63:
 This is known to be true in many cases; see [|erdos-graham|,
pp.~78--79].
\source{[|graham-amm|].}

\ansno4.64:
 This is a much weaker conjecture than the result in the
following exercise.

\ansno4.65:
 Cram\'er [|cramer|] showed that this conjecture is plausible on
probabilistic grounds, and computational experience bears this out:
Brent~[|brent-gaps|] has shown that $P_{n+1}-P_n\le602$ for
$P_{n+1}<2.686\times10↑{12}$. But the much weaker bounds in
exercise~|mills-proof| are the best currently proved~[|mozzochi|].
The previous exercise has a ``yes'' answer if $P_{n+1}-P_n<2P_n↑{1/2}$
for all sufficiently large~$n$.
According to [|guy|, problem A8], Paul Erd\"os offers \$10,000 for proof
that there are infinitely many $n$ such that
\begindisplay
P_{n+1}-P_n>{c\ln n\,\ln\ln n\,\ln\ln\ln\ln n\over
 (\ln\ln\ln n)↑2}
\enddisplay
for all $c>0$.
\source{[|cramer|].}

\ansno4.66:
 This holds if and only if $\nu_2(n)=\nu_3(n)$, according
to exercise~|epsilon-nu|. The methods of [|ruzsa-et-al|] may
help to crack this conjecture.
\source{Unpublished conjecture of P. Erd\H os.}

\ansno4.67:
 When $k=3$ the smallest solution is $n=4700063497=19\cdt47\cdt
5263229$; no other solutions are known in this case.
\source{[|erdos-graham|, p.~96].}

\ansno4.68:
 Experimental evidence suggests that there are about
${p(1-1/e)}$ distinct values, just as if the factorials were randomly
distributed modulo~$p$.