## Perl Weekly Challenge 246: Linear Recurrence of Second Order

These are some answers to the Week 246, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

*Spoiler Alert:* This weekly challenge deadline is due in a few days from now (on December 10, 2023 at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

## Task 1: 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]
```

Finding whether:

```
a[n] = p * a[n-2] + q * a[n-1]
```

isn't very difficult, except that `p`

and `q`

can both take an infinite number of values. We need to limit the range of these two integers. I initially wrote a Raku program in which `p`

and `q`

iterated over hard-coded integers from -5 to +5. It was OK for testing (and it worked for the test cases outlined in the task specification), but I did not find that satisfactory. So, I changed the range for `p`

and `q`

to be the minimum and maximum of the input array. This seems to work in all cases, but I can't prove it. Also, there may be a better solution to use a narrower range. But I do not have the energy to investigate the math aspect of it.

### Linear Recurrence of Second Order in Raku

We have three nested loops iterating over the values of `p`

and `q`

as described above and over the input array. Note that, in most cases, the most inner loop short-circuits almost immediately when the values of `p`

and `q`

are found to be not suitable for the input array.

```
sub linear-rec (@in) {
my @range = @in.minmax;
for @range -> $p {
for @range -> $q {
for 2..@in.end -> $i {
last if @in[$i] !=
$p * @in[$i-2] + $q * @in[$i-1];
# say "$p $q $i";
return ("True: p = $p, q = $q")
if $i == @in.end;
}
}
}
return (False);
}
my @tests = <1 1 2 3 5>, <4 2 4 5 7>, <4 1 2 -3 8>;
for @tests -> @test {
printf "%-12s => ", "@test[]";
say linear-rec @test;
}
```

This program displays the following output:

```
$ raku ./linear-recurrence.raku
1 1 2 3 5 => True: p = 1, q = 1
4 2 4 5 7 => False
4 1 2 -3 8 => True: p = 1, q = -2
```

### Linear Recurrence of Second Order in Perl

This is a port to Perl of the above Raku program (see the previous sections for explanations).

```
use strict;
use warnings;
use feature 'say';
sub linear_rec {
my @in = @_;
my ($min, $max) = (sort {$a <=> $b} @in)[0, -1];
for my $p ($min .. $max) {
for my $q ($min .. $max) {
for my $i (2..$#in) {
last if $in[$i] !=
$p * $in[$i-2] + $q * $in[$i-1];
# say "$p $q $i";
return ("True: p = $p, q = $q")
if $i == $#in;
}
}
}
return "False";
}
my @tests = ([<1 1 2 3 5>], [<4 2 4 5 7>], [<4 1 2 -3 8>]);
for my $test (@tests) {
printf "%-12s => ", "@$test";
say linear_rec @$test;
}
```

This program displays the following output:

```
$ perl linear-recurrence.pl
1 1 2 3 5 => True: p = 1, q = 1
4 2 4 5 7 => False
4 1 2 -3 8 => True: p = 1, q = -2
```

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on December 17, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Leave a comment