Task — Sort language

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.

Examples

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

Analysis

Let's start by noting that we can (usually) calculate the only p and q consistent with the supplied s0 to s3 (using s0 to s4 to represent the 5 supplied sequence members):

# Given:
s0 * p + s1 * q = s2
s1 * p + s2 * q = s3

# multiply 1st line by s0 and 2nd line by s1
∴ s0 * s2 * p + s1 * s2 * q = s2^2
  s1^2    * p + s1 * s2 * q = s3 * s1

# subtract 2nd line from 1st line and thus get p
∴ [(s0 * s2) - s1^2] * p = s2^2 - s3 * s1
∴ p = [s2^2 - s3 * s1] / [(s0 * s2) - s1^2]

# derive q from p
  s1 * q = s2 - s0 * p
∴ q = (s2 - s0 * p) / s1

We can then calculate n = p * s2 + q * s3, and if that equals p4 we can return 'true', or if doesn't we can return 'false'.

This is a trivial calculation, regardless of the magnitude of the numbers concerned.

But there are a number of difficult cases because the calculations above include two divisions, and in certain circumstances the divisor is zero. For example the sequence 2, 0, 2, 4, 10 is valid with p = 1 and q = 2, but the equation for q above evaluates as q = 0 / 0.

In such cases we can try calculating q first and then deriving p, analogously to the above, and that will work for some sequences but not others. But before we tackle those difficult cases we need to note that p and/or q as calculated above may not be integers, but the task requires that they are. The second supplied example is such a case:
4, 2, 4, 5, 7 is valid if p = 0.5 and q = 1, but 0.5 is not an allowed value for p so we must mark this sequence as 'false'.

So then we are left with some sequences where p and q can't be derived as above, and the reason is that they are not unique: for example 5, 5, 5, 5, 5 is possible for either p = 0, q = 1, or p = 1, q = 0.
I could not come up with a better solution for those sequences than testing all the possible values of p and q, positive and negative, which are less in magnitude than s2.

I believe that covers all the possibilities, but I am open to challenge.

Try it 

Try running the script with any input:

Your @a =

example: 2, 0, 2, 4, 10

⤡

#!/usr/bin/perl

use v5.26;    # The Weekly Challenge - 2023-12-04
use utf8;     # Week 246 task 2 - Linear recurrence of second order
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

linear_recurrence(1, 1, 2, 3, 5);
linear_recurrence(4, 2, 4, 5, 7);
linear_recurrence(4, 1, 2, -3, 8);
linear_recurrence(4, 1, 2, -3, 9);
linear_recurrence(2, 0, 2, 4, 10);
linear_recurrence(5, 5, 5, 5, 5);
linear_recurrence(7, 8, 0, 0, 0);
linear_recurrence(5, 5, -10, 5, 5);
linear_recurrence(5, 5, -10, 5, 6);
linear_recurrence(-1000, 999, 36977, 836485, 18721477);

sub linear_recurrence {
    
    my (@s, $p, $q, $good, $j, $z);
    
    # initialise
    @s = @_;
    say qq[\nInput:  ] . join(', ', @s);
    if ($#s != 4) {
        say qq[   bad input - must have 5 integers];
        return;
    }
    $good = '';
    
    # check for well-behaved-ness
    if ($s[0] * $s[2] - $s[1] ** 2 != 0 and $s[1] != 0) {
        $p = ($s[2] ** 2 - $s[3] * $s[1]) / ($s[0] * $s[2] - $s[1] ** 2);
        $q = ($s[2] - $s[0] * $p) / $s[1];
    } elsif ($s[1] ** 2 - $s[2] * $s[0] != 0 and $s[0] != 0) {
        $q = ($s[2] * $s[1] - $s[3] * $s[0]) / ($s[1] ** 2 - $s[2] * $s[0]);
        $p = ($s[2] - $s[1] * $q) / $s[0];
    } else {

        # loop over possible p and q values
        $good = 'false';
        P: for ($p = 0; $p <= abs($s[2]); $p ++) {
            for ($q = 0; $q <= abs($s[2]); $q ++) {
                
                # check +ve and -ve p and q
                for $z (0 .. 3) {
                    if ($p * $s[0] + $q * $s[1] == $s[2]
                        and $p * $s[1] + $q * $s[2] == $s[3]
                        and $p * $s[2] + $q * $s[3] == $s[4]) {
                        $good = 'true';
                        last P;
                    }
                    
                    $q = -$q;
                    $p = -$p if $z == 1;
                }
            }
        }
    }   
            
    $good = ($p == int($p) and $q == int($q) and $s[4] == $p * $s[2] + $q * $s[3]) ? 'true' : 'false';
    $good .= qq[ (p = $p, q = $q)] if $good eq 'true';
    
    say qq[Output: $good];
    
    # show the first 12 members
    if ($good =~ m|^true|) {
        for $j (5 .. 11) {
            $s[$j] = $s[$j - 2] * $p + $s[$j - 1] * $q;
        }
        say '   ' . join(', ', @s) . ' ...';
    }
}
    

Output

Input:  1, 1, 2, 3, 5
Output: true (p = 1, q = 1)
   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

Input:  4, 2, 4, 5, 7
Output: false

Input:  4, 1, 2, -3, 8
Output: true (p = 1, q = -2)
   4, 1, 2, -3, 8, -19, 46, -111, 268, -647, 1562, -3771 ...

Input:  4, 1, 2, -3, 9
Output: false

Input:  2, 0, 2, 4, 10
Output: true (p = 1, q = 2)
   2, 0, 2, 4, 10, 24, 58, 140, 338, 816, 1970, 4756 ...

Input:  5, 5, 5, 5, 5
Output: true (p = 0, q = 1)
   5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ...

Input:  7, 8, 0, 0, 0
Output: true (p = 0, q = 0)
   7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ...

Input:  5, 5, -10, 5, 5
Output: true (p = -1, q = -1)
   5, 5, -10, 5, 5, -10, 5, 5, -10, 5, 5, -10 ...

Input:  5, 5, -10, 5, 6
Output: false

Input:  -1000, 999, 36977, 836485, 18721477
Output: true (p = -14, q = 23)
   -1000, 999, 36977, 836485, 18721477, 418883181, 
   9372212485, 209696522621, 4691809045493, 
   104975856729645, 2348759378144933, 
   52551803703118429 ...