#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc1[20]
\end_layout

\end_inset

Suppose that you wish to obtain a decimal digit at random,
 not using a computer.
 Which of the following methods would be suitable?
\end_layout

\begin_layout Enumerate
Open a telephone directory to a random place by sticking your finger in it somewhere,
 and use the units digit of the first number found on the selected page.
\end_layout

\begin_layout Enumerate
Same as (a),
 but use the units digit of the 
\emph on
page
\emph default
 number.
\end_layout

\begin_layout Enumerate
Roll a die that is in the shape of a regular icosahedron,
 whose twenty faces have been labeled with the digits 0,
 0,
 1,
 1,
 ...,
 9,
 9.
 Use the digit that appears on the top,
 when the die comes to rest.
 (A felt-covered table with a hard surface is recommended for rolling dice.)
\end_layout

\begin_layout Enumerate
Expose a geiger counter to a source of radioactivity for one minute (shielding yourself) and use the units digit of the resulting count.
 Assume that the geiger counter displays the number of counts in decimal notation,
 and that the count is initially zero.
\end_layout

\begin_layout Enumerate
Glance at your wristwatch;
 and if the position of the second-hand is between 
\begin_inset Formula $6n$
\end_inset

 and 
\begin_inset Formula $6(n+1)$
\end_inset

 seconds,
 choose the digit 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Enumerate
Ask a friend to think of a random digit,
 and use the digit he names.
\end_layout

\begin_layout Enumerate
Ask an enemy to think of a random digit,
 and use the digit he names.
\end_layout

\begin_layout Enumerate
Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications.
 Assign to these horses the digits 0 to 9,
 in arbitrary fashion,
 and after the race use the winner's digit.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
This would work for a typical phone book.
 It wouldn't work if the book has,
 say,
 entries ordered by number with a fixed number of entries per page that is a multiple of 2 or 5.
 And,
 according to the official solution,
 in some places people can choose phone numbers (presumably in the US where Knuth lives) so it wouldn't work there as people would tend to choose round numbers.
\end_layout

\begin_layout Enumerate
This would be suitable,
 although some adjustment would have to be made to account for the fact that left pages would have even numbers and right pages would have round numbers (say,
 we could take the even number and divide it by two) and to avoid the last few pages if the total number is not a multiple of 20.
\end_layout

\begin_layout Enumerate
This would work very well.
\end_layout

\begin_layout Enumerate
This would work well assuming there are several digits between the most significant one and the units.
\end_layout

\begin_layout Enumerate
This would work assuming you only have to do it once at a time and not at a specific time.
\end_layout

\begin_layout Enumerate
This wouldn't work,
 as humans are not good at mentally generating random numbers.
\end_layout

\begin_layout Enumerate
This definitely wouldn't work,
 as the enemy would probably be compelled to choose the number strategically instead of randomly.
\end_layout

\begin_layout Enumerate
This could work,
 although it would be time consuming.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc3[10]
\end_layout

\end_inset

What number follows 1010101010 in the middle-square method?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Formula $1010101010^{2}=1020304050403020100$
\end_inset

,
 so the next number would be 3040504030.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc6[M21]
\end_layout

\end_inset

Suppose that we want to generate a sequence of integers 
\begin_inset Formula $X_{0},X_{1},X_{2},\dots$
\end_inset

,
 in the range 
\begin_inset Formula $0\leq X_{n}<m$
\end_inset

.
 Let 
\begin_inset Formula $f(x)$
\end_inset

 be any function such that 
\begin_inset Formula $0\leq x<m$
\end_inset

 implies 
\begin_inset Formula $0\leq f(x)<m$
\end_inset

.
 Consider a sequence formed by the rule 
\begin_inset Formula $X_{n+1}=f(X_{n})$
\end_inset

.
 (Examples are the middle-square method and Algorithm K.)
\end_layout

\begin_layout Enumerate
Show that the sequence is ultimately periodic,
 in the sense that there exist numbers 
\begin_inset Formula $\lambda$
\end_inset

 and 
\begin_inset Formula $\mu$
\end_inset

 for which the values
\begin_inset Formula 
\[
X_{0},X_{1},\dots,X_{\mu},\dots,X_{\mu+\lambda-1}
\]

\end_inset

are distinct,
 but 
\begin_inset Formula $X_{n+\lambda}=X_{n}$
\end_inset

 when 
\begin_inset Formula $n\geq\mu$
\end_inset

.
 Find the maximum and minimum possible values of 
\begin_inset Formula $\mu$
\end_inset

 and 
\begin_inset Formula $\lambda$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e316b"

\end_inset

(R.
 W.
 Floyd.) Show that there exists an 
\begin_inset Formula $n>0$
\end_inset

 such that 
\begin_inset Formula $X_{n}=X_{2n}$
\end_inset

;
 and the smallest such value of 
\begin_inset Formula $n$
\end_inset

 lies in the range 
\begin_inset Formula $\mu\le n\leq\mu+\lambda$
\end_inset

.
 Furthermore the value of 
\begin_inset Formula $X_{n}$
\end_inset

 is unique in the sense that if 
\begin_inset Formula $X_{n}=X_{2n}$
\end_inset

 and 
\begin_inset Formula $X_{r}=X_{2r}$
\end_inset

,
 then 
\begin_inset Formula $X_{r}=X_{n}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Use the idea of part 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e316b"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

 to design an algorithm that calculates 
\begin_inset Formula $\mu$
\end_inset

 and 
\begin_inset Formula $\lambda$
\end_inset

 for any given function 
\begin_inset Formula $f$
\end_inset

 and any given 
\begin_inset Formula $X_{0}$
\end_inset

,
 using only 
\begin_inset Formula $O(\mu+\lambda)$
\end_inset

 steps and only a bounded number of memory locations.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Assume 
\begin_inset Formula $f:\mathbb{Z}_{m}\to\mathbb{Z}_{m}$
\end_inset

,
 as otherwise the statements below are not necessarily true (e.g.
 if 
\begin_inset Formula $f:\mathbb{R}\to\mathbb{R}$
\end_inset

,
 
\begin_inset Formula $f(x)\coloneqq\frac{x}{2}$
\end_inset

,
 and 
\begin_inset Formula $X_{0}=\frac{m}{2}$
\end_inset

).
\end_layout

\begin_layout Enumerate
Require that 
\begin_inset Formula $\mu\in\mathbb{N}$
\end_inset

 and 
\begin_inset Formula $\lambda\in\mathbb{N}^{*}$
\end_inset

,
 as otherwise it is unclear what is meant and,
 in particular,
 the statement is obviously true when 
\begin_inset Formula $\mu\in\mathbb{N}$
\end_inset

 and 
\begin_inset Formula $\lambda=0$
\end_inset

.
 Now,
 since 
\begin_inset Formula $\{X_{0},\dots,X_{m}\}\subseteq\{0,\dots,m-1\}$
\end_inset

,
 then 
\begin_inset Formula $|\{X_{0},\dots,X_{m}\}|\leq m$
\end_inset

 and there must be integers 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $j$
\end_inset

,
 
\begin_inset Formula $0\leq i<j\leq m$
\end_inset

,
 such that 
\begin_inset Formula $X_{i}=X_{j}$
\end_inset

.
 We choose 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $j$
\end_inset

 such that 
\begin_inset Formula $j$
\end_inset

 is minimum,
 which ensures that 
\begin_inset Formula $X_{0},\dots,X_{j-1}$
\end_inset

 are distinct and uniquely determines 
\begin_inset Formula $i$
\end_inset

,
 and we set 
\begin_inset Formula $\mu\coloneqq i$
\end_inset

 and 
\begin_inset Formula $\lambda\coloneqq j-i$
\end_inset

;
 then 
\begin_inset Formula $X_{0},\dots,X_{\mu+\lambda-1=j-1}$
\end_inset

 are all distinct and,
 for 
\begin_inset Formula $n\geq\mu$
\end_inset

,
\begin_inset Formula 
\[
X_{n+\lambda}=X_{n-i+j}=f^{n-i}(X_{j})=f^{n-i}(X_{i})=X_{n}.
\]

\end_inset

It's easy to check that these values are unique:
 
\begin_inset Formula $\mu+\lambda$
\end_inset

 must be the first value such that 
\begin_inset Formula $X_{\mu+\lambda}$
\end_inset

 equals some other value earlier in the sequence,
 and 
\begin_inset Formula $\mu$
\end_inset

 must be the only value less than 
\begin_inset Formula $\mu+\lambda$
\end_inset

 such that 
\begin_inset Formula $X_{\mu}=X_{\mu+\lambda}$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard
As for the maximum and minimum,
 since 
\begin_inset Formula $0\leq i<j\leq m$
\end_inset

,
 we have 
\begin_inset Formula $0\leq\mu\leq m-1$
\end_inset

 and 
\begin_inset Formula $1\leq\lambda\leq m$
\end_inset

.
 These bounds can be reached:
 when 
\begin_inset Formula $f$
\end_inset

 is the identity,
 
\begin_inset Formula $\mu=0$
\end_inset

 and 
\begin_inset Formula $\lambda=1$
\end_inset

;
 when 
\begin_inset Formula $f(x)=(x+1)\bmod m$
\end_inset

,
 
\begin_inset Formula $\lambda=m$
\end_inset

,
 and when 
\begin_inset Formula $f(x)=\max\{0,x-1\}$
\end_inset

 and 
\begin_inset Formula $X_{0}=m-1$
\end_inset

,
 
\begin_inset Formula $\mu=m-1$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Let 
\begin_inset Formula $k\coloneqq\lceil\frac{\mu}{\lambda}\rceil$
\end_inset

 and 
\begin_inset Formula $n\coloneqq k\lambda$
\end_inset

,
 then 
\begin_inset Formula $\frac{\mu}{\lambda}\leq k\leq\frac{\mu}{\lambda}+1$
\end_inset

 and therefore 
\begin_inset Formula $\mu\leq n\leq\mu+\lambda$
\end_inset

,
 and 
\begin_inset Formula $X_{n}=X_{n+\lambda}=X_{n+2\lambda}=\dots=X_{n+k\lambda=2n}$
\end_inset

.
 For the uniqueness,
 let 
\begin_inset Formula $r>0$
\end_inset

 be such that 
\begin_inset Formula $X_{r}=X_{2r}$
\end_inset

,
 so necessarily 
\begin_inset Formula $2r\geq\mu+\lambda$
\end_inset

.
 We note that,
 for any 
\begin_inset Formula $s\geq\mu$
\end_inset

,
 by induction,
 
\begin_inset Formula $X_{s}=X_{s-\lfloor\frac{s-\mu}{\lambda}\rfloor\lambda}=X_{\mu+((s-\mu)\bmod\lambda)}$
\end_inset

,
 and we call 
\begin_inset Formula $R(s)\coloneqq\mu+((s-\mu)\bmod\lambda)\in\{\mu,\dots,\mu+\lambda-1\}$
\end_inset

.
 With this,
 
\begin_inset Formula $X_{R(2r)}=X_{2r}=X_{r}$
\end_inset

,
 so either 
\begin_inset Formula $r=R(2r)$
\end_inset

 or 
\begin_inset Formula $r\geq\mu+\lambda$
\end_inset

;
 in any case 
\begin_inset Formula $r\geq\mu$
\end_inset

 and 
\begin_inset Formula $X_{R(2r)}=X_{R(r)}$
\end_inset

.
 This means 
\begin_inset Formula $R(2r)=R(r)$
\end_inset

,
 so 
\begin_inset Formula $r\equiv0\mod{\lambda}$
\end_inset

 and 
\begin_inset Formula $R(r)=\mu+(-\mu\bmod\lambda)\equiv0\bmod\lambda$
\end_inset

,
 so 
\begin_inset Formula $R(r)$
\end_inset

 is unique and 
\begin_inset Formula $X_{r}=X_{R(r)}=X_{R(n)}=X_{n}$
\end_inset

.
\end_layout

\begin_layout Enumerate
First we set 
\begin_inset Formula $a,b\gets X_{0}$
\end_inset

 and then repeatedly set 
\begin_inset Formula $a\gets f(a)$
\end_inset

 and 
\begin_inset Formula $b\gets f^{2}(b)$
\end_inset

 until 
\begin_inset Formula $a=b$
\end_inset

;
 the number of times we do this operation is 
\begin_inset Formula $n$
\end_inset

,
 and in the end 
\begin_inset Formula $a=X_{n}$
\end_inset

.
 Then we set 
\begin_inset Formula $b\gets a$
\end_inset

 and repeat 
\begin_inset Formula $b\gets f(b)$
\end_inset

 until 
\begin_inset Formula $b=a$
\end_inset

;
 the number of times we do this operation is 
\begin_inset Formula $\lambda$
\end_inset

.
 Finally,
 since 
\begin_inset Formula $a$
\end_inset

 is a multiple of 
\begin_inset Formula $\lambda$
\end_inset

,
 
\begin_inset Formula $X_{\mu}=X_{\mu+n}$
\end_inset

,
 so we set 
\begin_inset Formula $b\gets X_{0}$
\end_inset

 and repeat 
\begin_inset Formula $b\gets f(b)$
\end_inset

 and 
\begin_inset Formula $a\gets f(a)$
\end_inset

 until 
\begin_inset Formula $a=b$
\end_inset

;
 the number of times we do this operation is 
\begin_inset Formula $\mu$
\end_inset

.
 In total this uses two slots of memory and runs in time 
\begin_inset Formula $O(n)+O(\lambda)+O(\mu)=O(\mu+\lambda)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[M21]
\end_layout

\end_inset

(R.
 P.
 Brent,
 1977.) Let 
\begin_inset Formula $\ell(n)$
\end_inset

 be the greatest power of 2 that is less than or equal to 
\begin_inset Formula $n$
\end_inset

;
 thus,
 for example,
 
\begin_inset Formula $\ell(15)=8$
\end_inset

 and 
\begin_inset Formula $\ell(\ell(n))=\ell(n)$
\end_inset

.
\end_layout

\begin_layout Enumerate
Show that,
 in terms of the notation in exercise 6,
 there exists an 
\begin_inset Formula $n>0$
\end_inset

 such that 
\begin_inset Formula $X_{n}=X_{\ell(n)-1}$
\end_inset

.
 Find a formula that expresses the least such 
\begin_inset Formula $n$
\end_inset

 in terms of the periodicity numbers 
\begin_inset Formula $\mu$
\end_inset

 and 
\begin_inset Formula $\lambda$
\end_inset

.
\end_layout

\begin_layout Enumerate
Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type 
\begin_inset Formula $X_{n+1}=f(X_{n})$
\end_inset

,
 to prevent it from cycling indefinitely.
 Your algorithm should calculate the period length 
\begin_inset Formula $\lambda$
\end_inset

,
 and it should only use a small amount of memory space—
you must not simply store all the computed sequence values!
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
For sufficiently large 
\begin_inset Formula $r$
\end_inset

,
 
\begin_inset Formula $n\coloneqq2^{r}-1+\lambda<2^{r+1}$
\end_inset

 and then 
\begin_inset Formula $X_{\ell(n)-1}=X_{2^{r}-1}=X_{n}$
\end_inset

,
 and it's easy to convince ourselves that all such 
\begin_inset Formula $n$
\end_inset

 are of the form 
\begin_inset Formula $2^{r}-1+k\lambda$
\end_inset

 with 
\begin_inset Formula $r\in\mathbb{N}$
\end_inset

,
 
\begin_inset Formula $k\in\mathbb{N}^{*}$
\end_inset

,
 
\begin_inset Formula $k\lambda-1<2^{r}$
\end_inset

,
 and 
\begin_inset Formula $2^{r}-1\geq\mu$
\end_inset

.
 The minimum value,
 then,
 happens with 
\begin_inset Formula $k=1$
\end_inset

 and 
\begin_inset Formula $2^{r}$
\end_inset

 is the minimum such that 
\begin_inset Formula $\lambda,\mu+1\leq2^{r}$
\end_inset

,
 so if 
\begin_inset Formula $u(n)$
\end_inset

 is the lowest power of 2 that is greater than or equal to 
\begin_inset Formula $n$
\end_inset

,
 then
\begin_inset Formula 
\[
n=u(\max\{\lambda,\mu+1\})+\lambda-1.
\]

\end_inset


\end_layout

\begin_layout Enumerate
We set 
\begin_inset Formula $a\gets b\gets X_{0}$
\end_inset

 and 
\begin_inset Formula $r\gets0$
\end_inset

.
 Then repeat 
\begin_inset Formula $b\gets f(b)$
\end_inset

 up to 
\begin_inset Formula $2^{r}$
\end_inset

 times;
 if at any point 
\begin_inset Formula $b=a$
\end_inset

,
 terminate with 
\begin_inset Formula $\lambda$
\end_inset

 equal to the number of times that 
\begin_inset Formula $b\gets f(b)$
\end_inset

 has been run in this iteration;
 otherwise set 
\begin_inset Formula $a\gets b$
\end_inset

,
 
\begin_inset Formula $r\gets r+1$
\end_inset

,
 and repeat this step.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc16[15]
\end_layout

\end_inset

A sequence generated as in exercise 6 must begin to repeat after at most 
\begin_inset Formula $m$
\end_inset

 values have been generated.
 Suppose we generalize the method so that 
\begin_inset Formula $X_{n+1}$
\end_inset

 depends on 
\begin_inset Formula $X_{n-1}$
\end_inset

 as well as on 
\begin_inset Formula $X_{n}$
\end_inset

;
 formally,
 let 
\begin_inset Formula $f(x,y)$
\end_inset

 be a function such that 
\begin_inset Formula $0\leq x,y<m$
\end_inset

 implies 
\begin_inset Formula $0\leq f(x,y)<m$
\end_inset

.
 The sequence is constructed by selecting 
\begin_inset Formula $X_{0}$
\end_inset

 and 
\begin_inset Formula $X_{1}$
\end_inset

 arbitrarily,
 and then letting
\begin_inset Formula 
\begin{align*}
X_{n+1} & =f(X_{n},X_{n-1}), & \text{for }n & >0.
\end{align*}

\end_inset

What is the maximum period conceivably attainable in this case?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

See exercise 17.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc17[10]
\end_layout

\end_inset

Generalize the situation in the previous exercise so that 
\begin_inset Formula $X_{n+1}$
\end_inset

 depends on the preceding 
\begin_inset Formula $k$
\end_inset

 values of the sequence.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The maximum conceivable would be 
\begin_inset Formula $m^{k}$
\end_inset

.
 Why this is always attainable is not at all obvious.
\end_layout

\end_body
\end_document