The Fraenkel-Krieger Solution to a certain mex recurrence
By Shalosh B. Ekhad
Theorem: Define the sequence A(n) for n>=n0, with n0=, 6
in terms of the following recurrence
A(n)=mex_1({A(i);i=n0..n-1)} Union {A(i)+c*i;i=n0..n-1} Union X )
where c=, 2, n0=, 6, (as above) and
where the set X is, {1, 5}, and mex_1(S) is the smallest pos. integer
NOT in S, for example mex({1,2,3,5})=4, mex({3,4,9})=1.
We have the following very fast way of computing A(n),
without using the recurrence (it is polynomial time vs.
exponential time (in bit-size, i.e. in log(n),
the number of digits of n))
The first, 18, members of the sequence are
starting with n=, 6, all the way to n=, 23
2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 18, 19, 21, 22, 23
Starting at n=, 24
A(n) is given by the succinct expression
1/2
IntegerPart(2 n) + 8 + r(n)
where r(n) is usually 0, and otherwise it is 1 or -1
as follows:
consider the following, 7, sequences
each satisfying the recurrence
n[j] = 2 n[j - 1] + n[j - 2]
with the following initial conditions
n[0] = 36, n[1] = 87
n[0] = 38, n[1] = 92
n[0] = 41, n[1] = 99
n[0] = 43, n[1] = 104
n[0] = 48, n[1] = 116
n[0] = 53, n[1] = 128
n[0] = 55, n[1] = 133
for each , n[j], j>=0 , with j even, r(n):=1
for each , n[j], j>=1 , with j odd, r(n):=-1
Also consider the following, 3, sequences
each satisfying the recurrence
n[j] = 2 n[j - 1] + n[j - 2]
with the following initial conditions
n[0] = 25, n[1] = 60
n[0] = 27, n[1] = 65
n[0] = 29, n[1] = 70
for each , n[j], j>=1 , with j odd, r(n):=1
for each , n[j], j>=0 , with j even, r(n):=-1
Proof: it follows from the beautiful proof of Dalia Krieger
and Aveizri Fraenkel, in their paper:
The structure of complementary sets of integers: A 3-shift theorem
Inter. J. of Pure and Applied Math. 10 (2004) 1-49, available on-line
http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/tsopaper1.pdf .
To sum up the "noisy" beginning has, 18, terms
The regular-shift is, 8
The irregular shifts belong to, 10, recursive sequences.
Just to demonstrate how fast this is, the millionth-term,
A(1000000) equals
1414205
and this took, 0.002, seconds (once we computed the F-K scheme)
Note that we didn't have to compute all the previous
almost million terms!
Thanks for reading this computer-generated paper!
generated by a humanly-generated Maple program
(written by Doron Zeilberger) based on
a humanly-generated brilliant algorithm invented (or discovered(?))
by Dalia Krieger and Aviezri Fraenkel.
This took , 0.108, seconds .