by Arne Sommer

# Sequential Conjectures with Raku

 Published 3. April 2020.

This is my response to the Perl Weekly Challenge #54.

## Challenge #54.1: kth Permutation Sequence

 Write a script to accept two integers n (>=1) and k (>=1). It should print the kth permutation of n integers. For more information, please follow the wiki page. For example, n=3 and k=4, the possible permutation sequences are listed below: ```123 132 213 231 312 321 ``` The script should print the 4th permutation sequence 231.

We can do this in REPL, and `permutations` is exactly what we need:

```> (1..3).permutations ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) ```

Note that `permutations` gives a list well, actually a sequence, but the destinction doesn't matter here. Note that this has nothing to do with the «sequence» word in the challenge) of lists, as we can see if we add the `raku` method:

```> (1..3).permutations.raku ((1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)).Seq ```

The example asked for the fourth one, so we apply an index on the list. The first value has index (or offset) 0, so the fourth one has index 3:

```> (1..3).permutations (2 3 1) ```

This is a list, so we can use `join` to combine (or join) them into a single string:

```> (1..3).permutations.join; 231 ```

See docs.raku.org/routine/permutations for more information about `permutations`.

See docs.raku.org/routine/raku for more information about `raku`.

See docs.raku.org/routine/join for more information about `join`.

The challenge wanted a script where we can specify different values for n and k. That is easy:

File: kth-perm ```unit sub MAIN (Int \$n where \$n >= 1, Int \$k where \$k >= 1); say (1..\$n).permutations[\$k-1].join; ```

I have added constraints on the input variables. It is possible to use a custom type (with `subset`), but that would add another line of code to the program - and the `where` clauses work well enough here.

Running it:

```\$ raku kth-perm 3 4 231 \$ raku kth-perm 10 10 12345689107 ```

## Challenge #54.2: Collatz Conjecture

 It is thought that the following sequence will always reach 1: `\$n = \$n / 2` when `\$n` is even `\$n = 3*\$n + 1` when `\$n` is odd For example, if we start at 23, we get the following sequence: 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Write a function that finds the Collatz sequence for any positive integer. Notice how the sequence itself may go far above the original starting number.
File: collatz ```unit sub MAIN (Int \$start where \$start >= 1); #  my \$sequence := gather #  { take \$start; #  my \$prev = \$start; #  loop #  { my \$new = \$prev %% 2 ?? \$prev / 2 !! 3 * \$prev + 1; #  \$prev = \$new; #  take \$new; #  last if \$prev == 1; #  } } say \$sequence.join(", "); #  ```

 The same way of ensuring correct input as in challenge #54.1 (above).

 `gather`/`take` is suitable here.

 The initial value is the first one in the sequence.

 Note the current value, as the next one is derived from it.

 An eternal loop (with an exit strategy in ).

 Compute the next value. If the previous one was even (`\$prev %% 2 == 0`), we halve it (`\$prev / 2`), and if not (it is odd), we apply the other rule (`3 * \$prev +1`).

 As .

 Deliver the new value.

 We are finished when we reach «1», using `last` to exit the loop.

 Print the sequence.

Running it:

```\$ collatz 23 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 \$ raku collatz 5 5, 16, 8, 4, 2, 1 \$ raku collatz 4 4, 2, 1 \$ raku collatz 3 3, 10, 5, 16, 8, 4, 2, 1 \$ raku collatz 2 2, 1 \$ raku collatz 1 1, 4, 2, 1 ```

The last one is wrong. The problem is that the `last` condition should come after the first 1, but that one comes before the loop. And when we get to the loop, we have passed it (with the «4» as the current value).

The solution is to move the condition to the start of the loop:

File: collatz (fixed) ```unit sub MAIN (Int \$start where \$start >= 1); my \$sequence := gather { take \$start; my \$prev = \$start; loop { last if \$prev == 1; my \$new = \$prev %% 2 ?? \$prev / 2 !! 3 * \$prev + 1; \$prev = \$new; take \$new; # last if \$prev == 1; } } say \$sequence.join(", "); ```

Running it:

```\$ collatz 23 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 \$ raku collatz 5 5, 16, 8, 4, 2, 1 \$ raku collatz 4 4, 2, 1 \$ raku collatz 3 3, 10, 5, 16, 8, 4, 2, 1 \$ raku collatz 2 2, 1 \$ raku collatz 1 1 ```

Looking good.

## Challenge #54.3: Extra Credit

 Have your script calculate the sequence length for all starting numbers up to 1000000 (1e6), and output the starting number and sequence length for the longest 20 sequences.
File: collatz-1e6 ```unit sub MAIN (Int \$limit = 1_000_000, :\$verbose, :\$chop = 20); #  my %length; #  for 1 .. \$limit #  { my @list = collatz(\$_); #  %length{@list.elems}.push(\$_); #  say "_ \$_ -> @list[]" if \$verbose; } my \$count = 0; #  my \$elems; #  for %length.keys.sort({ \$^b <=> \$^a }) -> \$l #  { \$elems = %length{\$l}; #  for @\$elems #  { last if \$count++ >= \$chop; #  say "{ \$count }: Number \$_ (with length \$l)"; #  } } sub collatz (\$start) #  { my \$sequence := gather { take \$start; my \$prev = \$start; loop { last if \$prev == 1; my \$new = \$prev %% 2 ?? \$prev / 2 !! 3 * \$prev + 1; \$prev = \$new; take \$new; } } return \$sequence; } ```

 The first argument is positional. If we don't specify an integer on the command line, it defaults to the value given in the challenge. Note the underscores used to enhance human readability. The second one is a named parameter, defaulting to `False`. The third one is (also) a named parameter giving the chop off limit, with 20 as default value.

 We collect the length of the sequences in this one. The length is the index, and the value is a list of starting numbers.

 For every value we should compute,

 • get the Collatz sequence.

 • add the starting number and the length to the hash.

 The number of values we have printed so far as part of the solution. We use this to ensure that we don't exceed the chop off limit.

 The starting numbers for the given length.

 Iterate over the hash keys (the lengths), sorted as numbers. If we don't, the sort will be as strings.

 • get the list of starting numbers.

 • iterate over those numbers.

 • • exit the loop if we have reached the chop off limit.

 • • show the number.

 The procedure is an almost verbatim copy of the «collatz» program.

Running it with a low number:

```\$ raku collatz-1e6 100 1: Number 97 (with length 119) 2: Number 73 (with length 116) 3: Number 54 (with length 113) 4: Number 55 (with length 113) 5: Number 27 (with length 112) 6: Number 82 (with length 111) 7: Number 83 (with length 111) 8: Number 41 (with length 110) 9: Number 62 (with length 108) 10: Number 63 (with length 108) 11: Number 31 (with length 107) 12: Number 94 (with length 106) 13: Number 95 (with length 106) 14: Number 47 (with length 105) 15: Number 71 (with length 103) 16: Number 91 (with length 93) 17: Number 78 (with length 36) 18: Number 79 (with length 36) 19: Number 39 (with length 35) 20: Number 57 (with length 33) ```

And finally with the specified upper limit 1000000:

```\$ raku collatz-1e6 1: Number 837799 (with length 525) 2: Number 626331 (with length 509) 3: Number 939497 (with length 507) 4: Number 704623 (with length 504) 5: Number 910107 (with length 476) 6: Number 927003 (with length 476) 7: Number 511935 (with length 470) 8: Number 767903 (with length 468) 9: Number 796095 (with length 468) 10: Number 970599 (with length 458) 11: Number 546681 (with length 452) 12: Number 818943 (with length 450) 13: Number 820022 (with length 450) 14: Number 820023 (with length 450) 15: Number 410011 (with length 449) 16: Number 615017 (with length 447) 17: Number 886953 (with length 445) 18: Number 906175 (with length 445) 19: Number 922524 (with length 445) 20: Number 922525 (with length 445) ```

The program used 21 minutes on my pc this time, which is quite some time. It does a lot of calculations, so that is pretty much as expected.

And that's it.