Lotteries and sequences

Weekly challenge 246 — 4 December 2023

Week 246 - 4 Dec 2023

Task 2

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 1Input: @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 2Input: @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 3Input: @a = (4, 1, 2, -3, 8) Output: true

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.

#!/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) . ' ...'; } }

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 ...

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain