PWC 246 Random use of algebra

It's December, and that means neglecting our responsibilities with

6 out of 49 is a German lottery.

Write a script that outputs six unique

random integers from the range 1 to 49.

Let's be random. 6 out of 49.

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: 1,1,2,3,5 is a second-order linear recurrence because a[n] = a[n-2] + a[n-1] (it's the beginning of the Fibonacci sequence of course).


• Example 2: 2,4,2,5,7 can't be a linear recurrence because it starts with multiples of even numbers, and therefore no combination of them will yield an odd number.


• Example 3: 4,1,2,-3,8 is a sequence that can be created with the recurrence a[n] = a[n-2] - 2 * a[n-1]
  

It's time to smugly take revenge on the bozos in algebra class who used to whine, "But when will we ever use this in real life?" Ha! The time has come, and as far as I can tell, this is real life. Or a damn good simulation.

To be a second-order recurrence relation, we have to find p and q that solve the pair of equations

• a[0]*p + a[1]*q = a[2]


• a[1]*p + a[2]*q = a[3]

and using those values of p and q, we also have to verify that a[4] can be generated from a[2]*p + a[3]*q = a[4]

From the first equation, we will get

p = (a[2] - a[1]*q)/a[0]

Substituting that into the second equation, we will get

q = (a[1]*a[2] - a[0]*a[3]) / (a[1]*a[1] - a[0]*a[2] )

So, given a sequence of at least 4 values, we can determine q, and from that we can determine p. Both have to be integers, per the problem statement. It's also possible that one of those denominators is zero, meaning that the recurrence can't be satisfied.

We could golf this down to some pretty cryptic code, but let's throw a bone to readability this week. First step, let's define the function that produces q:

sub fq($a0, $a1, $a2, $a3)

{

    my $denom = $a1*$a1 - $a0*$a2;

    return undef if $denom == 0;

    my $q = ($a1*$a2 - $a0*$a3)/$denom;

    return $q;

}

Amusing aside: I originally wanted to call this function q, but it gave me weird results. Do you see it? Of course: q is the built-in single-quote operator. A function q can be defined, but it can't be called because it won't override the operator.

Second step, let's define the function that produces p.

sub fp($q, $a0, $a1, $a2)

{

    return undef if $a0 == 0;

    my $p = ($a2 - $a1 * $q) / $a0;

    return $p;

}

And if we can find p and q, then we can write the code to check for a linear recurrence:

sub isl2(@a)

{

    my $q = fq( @a[0..3] );

    return false unless defined $q && int($q) == $q;



    my $p = fp($q, @a[0..2]);

    return false unless defined $p && int($p) == $p;



    # Must also be true for remaing values of @a

    for my $i ( 4 .. $#a )

    {

        my $nexta = $p * $a[$i-2] + $q * $a[$i-1];

        if ( $a[$i] != $nexta )

        {

            return false;

        }

    }

    return true;

}

Where did true and false come from? Since version 5.36, these booleans are available as built-ins, and this was a natural place to use them. They're still experimental, so using them requires

use builtin qw/true false/; no warnings "experimental::builtin"