By Doron Zeilberger
This version: Aug. 5, 2010.
To use it, download it, save it as DALIA, and type
ezra();
for the list of the main procedures. For help with a specific procedure type: ezra(ProcedureName);
For example, with help with procedure FK, type:
ezra(FK);
The main functions are
An(n0,X,c,n): the n-th term of the recurrence
A(n)=mex[1]({A(i),i=n0..n-1} union {A(i)+c*i,i=n0..n-1} union X )
(where for any finite set, S, mex[1](S) is the smallest positive integer NOT in S)
using the definition. It is much slower (exp. time) than the amazing
AnFK(n0,X,c,n). Only use it for testing purposes!
AnFK(n0,X,c,n): The same as An(n0,X,c,n), BUT much faster, using the amazing Fraenkel-Krieger algorithm. Once the initial investment of finding FK(c,n0,X) has been spent, it is poly time (w.r.t. to bit-size) rather than exp. time.
FK(n0,c,X): implements the Fraenkel-Krieger algorithm described in their beautiful paper. The inputs are:
The output is a list of length 4 that completely describes
the sequence described by the Fraenkel-Krieger recurrence
A(n)=mex({A(i),i=n0..n-1} union {A(i)+c*i,i=n0..n-1} union X )
FKv(n0,c,X): A very verbose version of FK(c,n0,X). Outputs a mathematical paper.
CheckFK(n0,X,c,N): empirically checks that the Fraenkel-Krieger algorithm is correct for the given parameters and for the first N terms.
To see the Fraenkel-Krieger description of the sequence given in Table 1 of their article, in TERSE style
the input
gives the output.
To see the Fraenkel-Krieger description of the sequence given in Table 1 of their article, in VERBOSE style
the input
gives the output.
To see the Fraenkel-Krieger description of the sequence given in Example 11 (p. 32) of their article, in TERSE style,
the
input
gives the output.
[Now there are 108 sequences of irregular shifts!]
To see the Fraenkel-Krieger description of the sequence given in Example 11 (p. 32) of their article, in VERBOSE style,
the
input
gives the output.
To empirically check the amazing Fraenkel-Krieger recurrence, the
the
input
gives the output.
To get the one-hundred-thousand-th term of the sequence A_{n} of Table 1,
the
input
gives the output.
[This is amazingly fast! Using the definition directly would take for ever.]