Question

What sequence of pseudorandom numbers is generated using the linear congruential generator$\mathbf{xn}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{(}\mathbf{4}\mathbf{xn}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{mod}\mathbf{7}$with seed $\mathit{x}\mathbf{0}\mathbf{=}\mathbf{3}$?

Short answer

Numbers is generated using the linear congruential generator is$\mathbf{6}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{6}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{6}\mathbf{,}\mathbf{\dots }$

Step-by-step solution

Step 1

${\mathit{x}}_{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{=}\mathbf{(}\mathbf{4}\mathit{x}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{,}{\mathit{x}}_{\mathbf{0}}\mathbf{=}\mathbf{3}$

The given recursive function and the initial value.

Step 2

$$\begin{gathered} {\mathbf{x}}_{\mathbf{0}}\mathbf{=}\mathbf{3} \\ \mathbf{n}\mathbf{=}\mathbf{0}\mathbf{,}{\mathbf{x}}_{\mathbf{1}}\mathbf{=}\mathbf{\left(}\mathbf{13}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{6} \\ \mathbf{n}\mathbf{=}\mathbf{1}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{=}\mathbf{\left(}\mathbf{25}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{4} \\ \mathbf{n}\mathbf{=}\mathbf{2}\mathbf{,}{\mathbf{x}}_{\mathbf{3}}\mathbf{=}\mathbf{\left(}\mathbf{17}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{3} \\ \mathbf{n}\mathbf{=}\mathbf{3}\mathbf{,}{\mathbf{x}}_{\mathbf{4}}\mathbf{=}\mathbf{\left(}\mathbf{13}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{6} \\ \mathbf{n}\mathbf{=}\mathbf{4}\mathbf{,}{\mathbf{x}}_{\mathbf{5}}\mathbf{=}\mathbf{\left(}\mathbf{25}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{4} \\ \mathbf{n}\mathbf{=}\mathbf{5}\mathbf{,}{\mathbf{x}}_{\mathbf{6}}\mathbf{=}\mathbf{\left(}\mathbf{17}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{3} \\ \mathbf{n}\mathbf{=}\mathbf{6}\mathbf{,}{\mathbf{x}}_{\mathbf{7}}\mathbf{=}\mathbf{\left(}\mathbf{13}\mathbf{\right)}\mathbf{mod}\mathbf{\left(}\mathbf{7}\mathbf{\right)}\mathbf{=}\mathbf{6} \end{gathered}$$

It is easily observed that this linear congruential generator is inherently pseudo-random as it only produces the numbers, $\mathbf{6}$,$\mathbf{4}$and$\mathbf{3}$ .