$25
CSE102 - Computer Programming with C - Assignment 8 - Collatz Conjecture - Solved
In this assignment, you will experiment with pointers, recursions and an interesting mathematical conjecture, namely Collatz.
Collatz conjecture has not been proven yet even though it is seemingly a simple problem. Consider the following function:
3𝑥 + 1 𝑖𝑓 𝑥 𝑖𝑠 𝑜𝑑𝑑
𝑓(𝑥) = { 𝑥/2 𝑖𝑓 𝑥 𝑖𝑠 𝑒𝑣𝑒𝑛
Starting with an integer 𝑥0 the sequence 𝑥1 = 𝑓( 𝑥0), 𝑥2 = 𝑓( 𝑥1), … tends end up with a loop 4, 2, 1, 4, 2, 1… Conjecture says that any starting integer should send this sequence to the same loop. (See https://www.youtube.com/watch?v=094y1Z2wpJg for an overview of this conjecture).
Towards the analysis of this conjecture, you are asked to write a few C functions: 1. (25 pts) Write a recursive function to generate and return the sequence.
void generate_sequence (int xs, int currentlen, int seqlen, int *seq)
Where xs is the first element of the sequence, seqlen is the length of the sequence, currentlen is the length of the sequence in the time of the function called, *seq is the array of the sequence.
2. (30 pts) Write a recursive function such that given any function and a starting integer check if the sequence ends up in a loop.
void check_loop_iterative(void (*f)(?), int xs, int seqlen, int *loop, int *looplen)
The first input is the function for which the sequence will be generated (fill its parameters declared with “?” above), starting from the first integer xs with a length of seqlen. The last two arguments will return the loop and its length. If no loop is found, the function will not update *loop array and return 0 with looplen variable.
Note that the loop's length can be n/2 at most and 2 at least, you should search for a loop with every possible length (until you find one) in descending order.
3. (20 pts) To be used in the previous function, you are asked to write a function to check if a given sequence of numbers has a loop in it.
int has_loop(int *arr, int n, int looplen, int *ls, int *le)
The function will receive a sequence starting from arr[0] and ending at arr[n-1]. It will check if there are any loops with a length of looplen. The first occurrence of the loop will be output with parameters ls and le.
This is not a void function, it will return 1 if a loop exists, 0 otherwise.
For example,
{15, 7, 4, 2, 1, 4, 2, 1} has a loop starting at arr[2] and ending at ar[4]. In this case ls=2 and le=4.
4. (25 pts) Write another recursive function that calculates the histogram of the first digits of the sequence generated by a given function.
void hist_of_firstdigits(void (*f)(?), int xs, int seqlen, int *h, int digit)
As before the first three parameters are for the generation of the sequence. h is the histogram of the first digits of the numbers that appear in the sequence. The size of this array will be 9 (you will ignore digit 0).
For the following sequence:
{340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1, 4, 2, 1}
The first digits of each integer:
{3, 1, 8, 2, 1, 6, 3, 1, 8, 4, 2, 1, 4, 2, 1}
The resulting histogram (*h) would be:
{5,3,2,2,0,1,0,2,0}
meaning that there are 0 numbers starting with digit 5 while there is only one number starting with digit 6.
Every time this function is being called; it should find the total numbers of integers starting with digit.
Program flow:
❖ In main, take the first element and the size of the sequence as inputs from the user (assume that the inputs will be proper, i.e., positive integers).
❖ In main, call the check_loop_iterative function.
❖ In check_loop_iterative function, generate & print the sequence (print it only once). Also, check if the sequence has a loop. If there is a loop, print its size and the indexes of its first occurrence. Do not print the loop itself in this function.
❖ In main, print the loop (if any). If there is no loop, print this information.
❖ In main, call the hist_of_firstdigits function. ❖ Print the histogram array in main.
