By Doron Zeilberger
This version: Aug. 5, 2010.
To use it, download it, save it as DALIA, and type
The main functions are
An(n0,X,c,n): the n-th term of the recurrence
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
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
To see the Fraenkel-Krieger description of the sequence given in Table 1 of their article, in VERBOSE style
To see the Fraenkel-Krieger description of the sequence given in Example 11 (p. 32) of their article, in TERSE style,
To see the Fraenkel-Krieger description of the sequence given in Example 11 (p. 32) of their article, in VERBOSE style,
To empirically check the amazing Fraenkel-Krieger recurrence, the
To get the one-hundred-thousand-th term of the sequence An of Table 1,
Written: Aug. 4, 2010.
This page is a short description of the Maple package
DALIA.
It implements the beautiful algorithm implicit in the proofs of Theorems 1 and 2
in Aviezri Fraenkel and Dalia Krieger's masterpiece
The Structure of Complementary sets of integers: a 3-shift theorem,
that appeared in Internat. J. Pure and Appl. Math. 10 (2004) 1--49.
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);
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!
A(n)=mex({A(i),i=n0..n-1} union {A(i)+c*i,i=n0..n-1} union X )
Sample Input and Output for DALIA
the input
gives the output.
the input
gives the output.
the
input
gives the output.
[Now there are 108 sequences of irregular shifts!]
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
[This is amazingly fast! Using the definition directly would take for ever.]
Doron Zeilberger's Maple Programs