62 |
62 |
63 |
63 |
64 \newpage |
64 \newpage |
65 \subsection*{Preliminary Part (3 Marks, file collatz.scala)} |
65 \subsection*{Preliminary Part (3 Marks, file collatz.scala)} |
66 |
66 |
67 This part is about recursion. You are asked to implement a Scala program |
67 This part is about function definitions and recursion. You are asked |
68 that tests examples of the \emph{$3n + 1$-conjecture}, also called |
68 to implement a Scala program that tests examples of the |
69 \emph{Collatz |
69 \emph{$3n + 1$-conjecture}, also called \emph{Collatz |
70 conjecture}.\video{https://www.youtube.com./watch?v=LqKpkdRRLZw} This |
70 conjecture}.\video{https://www.youtube.com./watch?v=LqKpkdRRLZw} |
71 conjecture can be described as follows: Start with any positive number |
71 This conjecture can be described as follows: Start with any positive |
72 $n$ greater than $0$: |
72 number $n$ greater than $0$: |
73 |
73 |
74 \begin{itemize} |
74 \begin{itemize} |
75 \item If $n$ is even, divide it by $2$ to obtain $n / 2$. |
75 \item If $n$ is even, divide it by $2$ to obtain $n / 2$. |
76 \item If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n + |
76 \item If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n + |
77 1$. |
77 1$. |
132 numbers} \here{https://medium.com/cantors-paradise/the-collatz-conjecture-some-shocking-results-from-180-000-iterations-7fea130d0377} |
132 numbers} \here{https://medium.com/cantors-paradise/the-collatz-conjecture-some-shocking-results-from-180-000-iterations-7fea130d0377} |
133 in the Collatz series---these are the last odd numbers just before a |
133 in the Collatz series---these are the last odd numbers just before a |
134 power of two is reached. For this, implement an |
134 power of two is reached. For this, implement an |
135 \textit{is-power-of-two} function which tests whether a number is a |
135 \textit{is-power-of-two} function which tests whether a number is a |
136 power of two. The easiest way to implement this is by using the |
136 power of two. The easiest way to implement this is by using the |
137 bit-operator $\&$. For a power of two, say $n$ with $n > 0$, it |
137 bit-operator $\&$ of Scala. For a power of two, say $n$ with $n > 0$, it |
138 holds that $n \;\&\; (n - 1)$ is equal to zero. I let you think why |
138 holds that $n \;\&\; (n - 1)$ is equal to zero. I let you think why |
139 this is the case. The function \textit{is-hard} calculates whether |
139 this is the case. The function \textit{is-hard} calculates whether |
140 $3n + 1$ is a power of two. Finally the \textit{last-odd} function |
140 $3n + 1$ is a power of two. Finally the \textit{last-odd} function |
141 calculates the last odd number before a power of 2 in the Collatz |
141 calculates the last odd number before a power of 2 in the Collatz |
142 series. This means for example when starting with 6 and also with 9, |
142 series. This means for example when starting with 6 and also with 9, |
149 The \textit{last-odd} function will only be called with numbers that are not |
149 The \textit{last-odd} function will only be called with numbers that are not |
150 powers of 2 themselves. |
150 powers of 2 themselves. |
151 \end{itemize} |
151 \end{itemize} |
152 |
152 |
153 \noindent |
153 \noindent |
154 \textbf{Test Data:} Some test ranges are: |
154 \textbf{Test Data:} Some test ranges and cases are: |
155 |
155 |
156 \begin{itemize} |
156 \begin{itemize} |
157 \item 1 to 10 where $9$ takes 19 steps |
157 \item 1 to 10 where $9$ takes 19 steps |
158 \item 1 to 100 where $97$ takes 118 steps, |
158 \item 1 to 100 where $97$ takes 118 steps, |
159 \item 1 to 1,000 where $871$ takes 178 steps, |
159 \item 1 to 1,000 where $871$ takes 178 steps, |
160 \item 1 to 10,000 where $6,171$ takes 261 steps, |
160 \item 1 to 10,000 where $6,171$ takes 261 steps, |
161 \item 1 to 100,000 where $77,031$ takes 350 steps, |
161 \item 1 to 100,000 where $77,031$ takes 350 steps, |
162 \item 1 to 1 Million where $837,799$ takes 524 steps |
162 \item 1 to 1 Million where $837,799$ takes 524 steps |
163 %% runs out of stack space |
163 %% runs out of stack space |
164 %% \item[$\bullet$] $1 - 10$ million where $8,400,511$ takes 685 steps |
164 %% \item[$\bullet$] $1 - 10$ million where $8,400,511$ takes 685 steps |
|
165 \item 21 is the last odd number for 84 |
|
166 \item 341 is the last odd number for 201, 604, 605 and 8600 |
|
167 |
165 \end{itemize} |
168 \end{itemize} |
166 |
169 |
167 |
170 |
168 |
171 |
169 |
172 |