perm filename CHAP4.ANS[GKP,DEK]1 blob sn#846244 filedate 1987-09-24 generic text, type T, neo UTF8

\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$.