by Arne Sommer

# Out of Linear with Raku and Friends

[266] Published 9. December 2023.

This is my response to The Weekly Challenge #246.

## Challenge #246.1: 6 out of 49

6 out of 49 is a German lottery.

Write a script that outputs six unique random integers from the range 1 to 49.

Output: ```3 10 11 22 38 49 ```

This is extremely easy:

File: 6-out-of-49 ```#! /usr/bin/env raku (1..49).pick(6).sort>>.say; ```

We start with the sequence `1..49`, then `pick` 6 random values (without repetition) from that sequence. Then we `sort` the selection (numerically, as the values are integers) as the challenge seems to imply that we should, and finally apply `say` on each value (with the `>>.` invocation) so that each one is printed on a seperate line.

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

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

Running it:

```\$ ./6-out-of-49 12 13 28 41 43 45 \$ ./6-out-of-49 1 3 13 16 17 33 ```

The numbers may look random. But you should not bet your life (or money, or somebody else's life or money) on a computer being able to generate truly random numbers.

### A Perl Version

This is much more work in Perl:

File: 6-out-of-49.perl ```#! /usr/bin/env perl my %six; # [1] while (keys %six < 6) # [2] { \$six{ int(1+ rand(48)) } = 1; # [2a] } foreach my \$key (sort { \$a <=> \$b } keys %six) # [3] { print "\$key\n"; # [3a] } ```

[1] We are going to store the random numbers in this hash, thus eliminating duplicates automatically.

[2] As long as have not gotten the six numbers, add a new one to the hash.

[3] Sort the keys (the numbers) numerically, and print them on separate lines.

Running ut gives the (un)expected result:

```\$ ./6-out-of-49.perl 12 19 34 38 42 45 \$ ./6-out-of-49.perl 5 7 12 21 23 40 ```

### A Ruby Version

This is a little trickier than the Perl version. As we replace the [Perl: 3,3a] step with a loop pushing the keys to an array [Ruby: 1], and then print the values in a separate loop [Ruby: 2]. I have called the array «seven», just for fun.

File: 6-out-of-49.ruby ```#! /usr/bin/env ruby six = {} while six.length < 6 do six[ rand(1...49) ] = 1 end seven = []; six.each do |key, value| # [1] seven.push key end seven.sort { |a,b| a <=> b }.each do |key| # [2] puts key end ```

Running it:

```\$ ./6-out-of-49.ruby 7 11 12 24 33 47 \$ ./6-out-of-49.ruby 30 36 38 43 44 48 ```

### A Shell (bash) Version

The Ruby version was complicated, but let us have a go at a shell script version, as this is even more convoluted.

File: 6-out-of-49.sh ```#! /bin/bash declare -A SIX for (( ; ; )) do key=\$((\$RANDOM % 49 + 1)) SIX[\$key]=1 if [ \${#SIX[*]} -gt 5 ]; then break fi done IFS=\$'\n' sorted=(\$(sort -n <<<"\${!SIX[*]}")) unset IFS for value in \${sorted[@]}; do echo "\$value" done ```

Running it:

```\$ ./6-out-of-49.sh 5 6 17 29 44 48 \$ ./6-out-of-49.sh 4 6 27 29 35 46 ```

### An SQL Version

This one was quite fun to write. I installed «sqlite» (version «sqlite3»), as I could then work with a throw away in-memory database.

File: 6-out-of-49.sql ```CREATE TABLE lotto (Value INT NOT NULL); INSERT INTO lotto VALUES (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),(39),(40), (41),(42),(43),(43),(45),(46),(47),(48),(49); -- SELECT * FROM lotto ORDER BY RANDOM() LIMIT 6; SELECT * FROM (SELECT * FROM lotto ORDER BY RANDOM() LIMIT 6) ORDER BY Value; ```

The first block (`CREATE`) is the creation of a database table.

The second block (`INSERT`) adds 49 rows to this table, each with a single value (from 1 to 49).

The third block (`-- SELECT`) selects 6 values randomly, without repetition. But the order is random as well, so it is commented out (with the sql `--` start of comment marker.

The fourth and final block (`SELECT`) wraps the expression from the third block into a select that orders the values.

Run it by feeding the file to the «sqlite3» command:

```\$ sqlite3 < ./6-out-of-49.sql 2 10 33 36 39 49 \$ sqlite3 < ./6-out-of-49.sql 2 5 7 10 46 49 ```

## Challenge #246.2: Linear Recurrence of Second Order

You are given an array `@a` of five integers.

Write a script to decide whether the given integers form a linear recurrence of second order with integer factors.

A linear recurrence of second order has the form ```a[n] = p * a[n-2] + q * a[n-1] with n > 1 where p and q must be integers. ```

Example 1: ```Input: @a = (1, 1, 2, 3, 5) Output: true @a is the initial part of the Fibonacci sequence a[n] = a[n-2] + a[n-1] with a[0] = 1 and a[1] = 1. ``` Example 2: ```Input: @a = (4, 2, 4, 5, 7) Output: false a[1] and a[2] are even. Any linear combination of two even numbers with integer factors is even, too. Because a[3] is odd, the given numbers cannot form a linear recurrence of second order with integer factors. ``` Example 3: ```Input: @a = (4, 1, 2, -3, 8) Output: true a[n] = a[n-2] - 2 * a[n-1] ```

Let us take a look at the first example, the Fibonacci sequence (the 1 based version of it). Here both `p` and `q` are `1`.

We can specify it with this Raku code:

```(1, 1, * + * ... Inf) ```

This is Sequence #041 in my Centenary Sequences with Raku - Part 4: Primes and Fibonacci article.

Ok. But that does not really help us.

Let us go back to the examples. Som observations:

1. All the values are single digits. This (hopefully) implies that the `p` and `q` values are low.
2. The 4th value in the third example is negative. This implies that either `p` or `q` is negative.

We are going to solve this with loops for the `p` and `q` values. I have chosen to use -10 and 10 as lower and upper limits. But is this reasonable? Let use try to reverse engineer the task, and find out.

The following program gives us the sequence, given the two first values and `p` and `q`:

File: reverse-lroso ```#! /usr/bin/env raku unit sub MAIN (Int \$first, # [1] Int \$second, # [1a] Int :\$p = 1, # [2] Int :\$q = 1, # [2a] UInt :\$limit = 10); # [3] my \$seq := (\$first, \$second, \$p * * + \$q * * ... Inf); # [4] say \$seq[^\$limit].join(", "); # [5] ```

[1] The first and second values.

[2] The `p` and `q` values, as named parameters with default value 1.

[3] The number of values to print from the sequence.

[4] The first and third stars are mutiplication operators, and the second and fourth ones are placeholder variables that refer back to the previous values in the sequence.

[5] Pretty print the requested number of vales. Note that the sequnce is lazy, so it will only generate the values that is requested (printed, in this case).

Running it:

```\$ ./reverse-lroso 1 1 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ```

That is the Fibonacci sequence.

Let us try with different `p` and `q` values:

```\$ ./reverse-lroso -p=10 -q=10 1 1 1, 1, 20, 210, 2300, 25100, 274000, 2991000, 32650000, 356410000 \$ ./reverse-lroso -p=10 -q=-10 1 1 1, 1, 0, 10, -100, 1100, -12000, 131000, -1430000, 15610000 \$ ./reverse-lroso -p=12 -q=-12 1 1 1, 1, 0, 12, -144, 1872, -24192, 312768, -4043520, 52275456 \$ ./reverse-lroso -p=12 -q=-2 1 1 1, 1, 10, -8, 136, -368, 2368, -9152, 46720, -203264 \$ ./reverse-lroso -p=12 -q=1 1 1 1, 1, 13, 25, 181, 481, 2653, 8425, 40261, 141361 \$ ./reverse-lroso -p=-1 -q=-1 1 1 1, 1, -2, 1, 1, -2, 1, 1, -2, 1 \$ ./reverse-lroso -p=-1 -q=-2 1 1 1, 1, -3, 5, -7, 9, -11, 13, -15, 17 \$ ./reverse-lroso -p=-2 -q=-1 1 1 1, 1, -3, 1, 5, -7, -3, 17, -11, -23 \$ ./reverse-lroso -p=-2 -q=-2 1 1 1, 1, -4, 6, -4, -4, 16, -24, 16, 16 \$ ./reverse-lroso -p=10 -q=9 1 1 1, 1, 19, 181, 1819, 18181, 181819, 1818181, 18181819, 181818181 ```

The -10 and 10 limits seems reasonable, for the examples given in the challenge.

But the program will not be able to detect the examples above where either `p`, `q` or both are outside of those limits. That may be a problem...

File: lroso ```#! /usr/bin/env raku unit sub MAIN (*@a where @a.elems == 5 && all(@a) ~~ Int, # [1] :v(:\$verbose)); for -10 .. 10 -> \$p # [2] { for -10 .. 10 -> \$q # [3] { is-lroso(@a, \$p, \$q) if \$p * @a[0] + \$q * @a[1] == @a[2]; # [4] } } say 'false'; # [5] sub is-lroso (@a is copy, \$p, \$q) # [6] { my \$first = @a.shift; # [7] my \$second = @a.shift; # [8] my \$target; # [9] while (@a.elems) # [10] { \$target = @a.shift; # [11] return unless \$p * \$first + \$q * \$second == \$target; # [12] \$first = \$second; # [13] \$second = \$target; # [14] } say ": p:\$p, q:\$q" if \$verbose; say 'true'; # [15] exit; # [15a] } ```

[1] The 5 integers.

[2] Iterate over the possible values for `p`.

[3] Ditto for `q`.

[4] Check the rest of the values, but only if the third one is as expected. The condition is here to speed up the program. Feel free to remove it.

[5] We have not found a match at all, then we have failed. Say so.

[6] Procedure cheking if the sequence can be generated with the `p` and `q` values. Note the `is copy` so that we can change this variable.

See docs.raku.org/type/Signature#index-entry-trait_is_copy for more information about `is copy`.

[7] Get the first value.

[8] And the second.

[9] The target, or the third value, will be placed here.

[10] As long as we have more values to check.

[11] Set the target, what we expect to get as the next value in the sequence.

[12] Return if we do not get the target by applying the rule.

[13,14] Set the first and second values ready for the next iteration.

[15] We have verified the rule if we get here. Say so, and terminate the porgram.

Running it:

```\$ ./lroso 1 1 2 3 5 true \$ ./lroso 4 2 4 5 7 false \$ ./lroso 4 1 2 -3 8 true ```

Looking good.

Verbose mode will give you the values of `p` and `q`:

```\$ ./lroso -v 1 1 2 3 5 : p:1, q:1 true \$ ./lroso -v 4 2 4 5 7 false \$ ./lroso -v 4 1 2 -3 8 : p:1, q:-2 true ```

Do remember that `p` and/or `q` outside the limits (-10 .. 10) will not be detected:

```\$ ./reverse-lroso -p=12 -q=12 1 1 1, 1, 24, 300, 3888, 50256, 649728, 8399808, 108594432, 1403930880 \$ ./lroso 1 1 24 300 3888 false ```

And that's it.