DALIA: A Maple package for implementing the amazing Fraenkel-Krieger algorithm for solving certain mex-type recurrences

By Doron Zeilberger

Written: Aug. 4, 2010.

This version: Aug. 5, 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);

The main functions are

• An(n0,X,c,n): the n-th term of the recurrence
A(n)=mex({A(i),i=n0..n-1} union {A(i)+c*i,i=n0..n-1} union X )
(where for any finite set, S, mex(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:

• c: a positive integer ;
• n0: a positive integer ;
• X: a set of positive integers .

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.

# Sample Input and Output for DALIA

• 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 An of Table 1,
the input gives the output.
[This is amazingly fast! Using the definition directly would take for ever.]

Doron Zeilberger's Maple Programs