Exercises

Question 1

The Collatz Conjecture:

The Collatz Conjecture, named after Lothar Collatz, states that, starting from any natural number, it is possible to reach 1 by following certain rules:

  1. Take n:
    • If n is odd, set n = 3n+1.
    • Else, if n is even, set n = n/2.
  2. Repeat the procedure until 1 is reached.

Part 1

Write a program that takes a number and find numbers of steps before a number converges to 1 by the Collatz Conjecture. See here for examples.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# This function takes a number and calculates value of the num
# at each step, returns array from the number to 1
# and total number of steps before converging to 1

sub collatz_conjecture_count_and_vals($num) {
    my $count = 0;
    my @sequence = [$num];
    my $number = $num;
    until $number == 1 {
        if $number % 2 == 0 {
            $number = $number/2;
            $count = $count + 1;
            say "Step $count: ", $number;
            @sequence.append($number);
        } else {
            $number = 3*$number + 1;
            $count = $count + 1;
            say "Step $count: ", $number;
            @sequence.append($number);
        }
    }
    say @sequence;
    return "Total steps: ", $count;
}

say collatz_conjecture_count_and_vals(10)


# Output

# Step 1: 5
# Step 2: 16
# Step 3: 8
# Step 4: 4
# Step 5: 2
# Step 6: 1
# [10 5 16 8 4 2 1]
# (Total steps:  6)

The conjecture is currently unproven, although it has been shown to hold for numbers up to 5476377146882523136.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Lets calculate number of steps before 5476377146882523136
# converges to 1

sub collatz_conjecture_steps($num) {
    my $count = 0;
    my $number = $num;
    until $number == 1 {
        if $number % 2 == 0 {
            $number = $number/2;
            $count = $count + 1;
        } else {
            $number = 3*$number + 1;
            $count = $count + 1;
        }
    }
    return "Total steps: ", $count;
}

say collatz_conjecture_steps(5476377146882523136)

# Output

#(Total steps:  78)

Part 2

Now write a program that takes as command-line input a single number, representing a number of Collatz steps (steps required to reach 1 by following the Collatz procedure), and computes the lowest number (starting from 1) which requires this number of Collatz steps. For example, if the number input was 949, your program should output 63,728,127; similarly, if you input 1132, it should output 9,780,657,630 as the lowest number requiring 1132 Collatz steps. Since these are fairly large numbers, and it might take your code a very long time to reach them (unless you use a more advanced technique, such as in some manner memoizing previous results and efficiently checking to see if you’ve already found the number of steps remaining from a given number - but I digress) you can use the following smaller test cases: For an input of 6, your code should output 10. For an input of 45, it should output 361. Finally, for an input of 260, it should print 18514.

Question 2

Implement a function, increment that takes as input a vector of integers and returns a new vector of integers that has the values of the original list each incremented by one. For example:

[1,2,3] –> [2,3,4]

Answer 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# This is list
# Lists are immutable while Arrays are mutable in Raku

my $vector = (1,2,3);

sub increment($vec) {
    return $vec.map: * + 1;
}

say increment($vector);
say $vector;

# Original vector is not modified/mutated

# Output

(2 3 4)
(1 2 3)

Question 3

Implement a function, incrementMut that takes as input a vector of integers and modifies the values of the original list by incrementing each value by one. For example:

[1,2,3] –> [2,3,4]