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[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:

• 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