Assign1 (Fall-2025.Specifications.Assign1)

Programming (70%)

Practice Problems (Ungraded)

These problems come from a list of Exercises on OCaml's webpage. We won't grade these (the solutions are given with the problem statements) but we'll typically include a couple with each assignment for additional practice.

Number of factors

val num_factors : int -> int

Implement num_factors so that num_factors n is the number of prime factors of n. For example, num_factors 18 is 3 because $18 = 2 * 3 * 3$ . The behavior of the function is undefined if n is not positive (i.e., there will be no test cases in which n is not positive).

Perfect Power

val perfect_power : int -> int -> bool

Implement perfect_power so that perfect_power i n is true if there is a integer $k$ such that $k^i = n$ , and false otherwise. For example, perfect_power 3 (-8) is true since $-8 = (-2)^3$ .

Collatz

val collatz : int -> int

The Collatz conjecture asks if the following procedure halt for all positive integers $n$ :

if $n = 1$ then HALT;
if $n$ is even, divide $n$ by $2$ ;
if $n$ is odd, multiply $n$ by $3$ and add $1$ .

Implement collatz so that collatz n is the number of steps it takes for the above procedure to halt. For example collatz 5 is 5 because the above procedure has the following behavior:

5 \longrightarrow 16 \longrightarrow 8 \longrightarrow 4 \longrightarrow 2 \longrightarrow 1

Note that, if the conjecture is false, your function is not guaranteed to halt!

Total Stopping Time Records

val tst_records : int -> int

In this problem, we define a different sequence based on the collatz function from the previous problem. The number collatz n is sometimes called the total stopping time of n. We say that n is a total stopping time record if its total stopping time is greater than that of any previous numbers. That is, n is a total stopping time record if collatz m < collatz n for all m satisfying 1 <= m && m < n.

Implement tst_records so that tst_records n is the $n$ th largest number with total stopping time record (by 0-indexing).

Written (30%)

FRACTRAN

In this course, we take up the programming language as an object of formal study. We will focus on "good" programming languages. But before we do this, here is a puzzle about a "bad" programming language. FRACTRAN is an esoteric (joke) programming language in which programs are sequences of fractions (i.e., this is the syntax of the language). A FRACTRAN program $(a_1, \dots, a_k)$ is run on a positive integer $n$ as follows (i.e., the semantics of the language is given by the following procedure):

Start with a program counter $i \gets 1$ ;
Determine if $a_in$ is an integer. If it is, set $n \gets a_in$ and reset $i \gets 1$ . If it isn't, increment $i$ , i.e., set $i \gets i + 1$ ;
If $i > k$ then HALT and output $n$ ;
Go back to step 2.

We encode the input of a program in the exponents of the prime factorization of $n$ . If we want to run a program on two positive integers $j$ and $k$ , we run it on $n = 2^j3^k$ . For example, the program

\left( \frac{3}{2} \right)

computes addition; given an input of the form $2^{j}3^k$ , it halts with output $3^{j + k}$ and the exponent has the sum of $j$ and $k$ .

Determine the output of the following program on an input of the form $2^{j}3^{k}$ . Describe in English what this program computes.

\left( \frac{5}{6}, \frac{5}{2}, \frac{5}{3} \right)