RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved random generation and spotting a linear recurrence. (Note that this ends today.)

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

There are basically three standard ways of picking from a list without repetition: delete the entries from the list as they're used, keep a cache of the used entries and check each pick from the original list against them, and shuffle the entire list, whch is generally the fastest.

This specific problem is most easily done in shell, laying out the four steps:

seq 1 49 | shuf | head -n6 | sort -n | xargs echo

Generate the sequence; shuffle it; take six entries; sort them. In Perl:

sub sixoffortynine {
  my @candidates = (1..49);
  @candidates = shuffle @candidates;
  splice @candidates, 6;
  @candidates = sort {$a <=> $b} @candidates;
  print join(', ', @candidates), "\n";
}

Most of the languages have a shuffle operator, and the rest can easily have it added: like 245's task 1 last week, I can assign a random number to each, then sort the list based on that. JavaScript:

function shuffleArray(input) {
    let keys = Array(input.length).fill().map((element, index) => Math.random());
    let ix = Array(input.length).fill().map((element, index) => index);
    ix.sort(function(a, b) {
        return keys[a] - keys[b];
    });
    return ix.map(n => input[n]);
}

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

One can do cunning things to build a generating function for this kind of recurrence, but the key insight is given in the question:

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

With a sequence of 5 numbers, we have three sets of a[n-2…n] values, which means we can build three simultaneous equations:

a[2] = p * a[0] + q * a[1]
a[3] = p * a[1] + q * a[2]
a[4] = p * a[2] + q * a[3]

With all a values known, two of those are enough to determine the values of p and q, with the third serving as a check.

I ended up laying out the three slices as a (indices 0 to 2), b (1 to 3) and c (2 to 4) for my convenience. Then it's a standard elmination of variables:

a0 * p + a1 * q = a
p = (a2 - a1 * q) / a0
b0 * p + b1 * q = b2
b0 * (a2 - a1 * q) / a0 + b1 * q = b2
...
q = (a0 * b2 - a2 * b0) / (a0 * b1 - a1 * b0)

(Because we know p and q are integers, this formulation minimises the divisions and potential rounding errors in intermediate stages. But in untyped languages it's essential to clamp each step to integer resolution.)

Then it's just a matter of running each of the three original equations and checking that it produces the right result - strictly only the third should be necessary, but I run the first two to check for rounding errors. This is pretty much the same in every language, apart from the rearrangement needed for PostScript's RPN.

In Scala:

def linearrecurrencesecondorder(seq: List[Int]): Boolean = {
  val a = seq.take(3)
  val b = seq.take(4).takeRight(3)
  val c = seq.take(5).takeRight(3)
  val q = (b(2) * a(0) - b(0) * a(2)) / (b(1) * a(0) - b(0) * a(1))
  val p = (a(2) - a(1) * q) / a(0)
  return p * a(0) + q * a(1) == a(2) && p * b(0) + q * b(1) == b(2) && p * c(0) + q * c(1) == c(2)
}

Full code on github.