1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
# Compute linear recursive sequences using Galois stepping (I think --
# or maybe I have it backwards)
# FIXME: Check names for this stuff!
# Galois Matrix
# Given a linear combining rule (a_1*x_+...+a_n*x_n=x_(n+1)),
# gives the Galois stepping matrix
SetHelp ("GaloisMatrix", "combinatorics", "Galois matrix given a linear combining rule (a_1*x_1+...+a_n*x_n=x_(n+1))")
function GaloisMatrix(combining_rule) = (
[[0;I(columns(combining_rule)-1)],combining_rule.']
)
# Linear recursive sequence
SetHelp ("LinearRecursiveSequence", "combinatorics", "Compute linear recursive sequence using Galois stepping")
function LinearRecursiveSequence(seed_values,combining_rule,n) =
(
if IsNull(n) then return null;
if IsMatrix(n) then (
for j=1 to elements(n) do (
n@(j) = LinearRecursiveSequence(seed_values,combining_rule,n@(j))
);
return n
);
k=columns(seed_values);
if (k > n >= 0) then # If asks for one of the seed values, return it
seed_values@(n+1)
else # otherwise...
(
G=GaloisMatrix(combining_rule); # form the Galois matrix
if (n >= k) then
(seed_values*G^(n-k+1))@(k) # ...and step it enough times
else if (IsInvertible(G)) then
(seed_values*G^n)@(1) # ...or step it backwards
else null # (if sequence is reversible)
)
)
|
