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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.