##################################################################
##subgames.txt: This file is made to accompany the paper         #
##"On Aperiodic Subtraction Games with Bounded Nim Sequence"     #
##                                                               #
##Save this file as subgames.txt                                 #
##To use it, stay in the                                         #
##same directory, start Maple (by typing: maple <Enter> )        #
##and then type:  read subgames.txt <Enter>                      #
##Then follow the instructions given there                       #
##                                                               #
##This file depends on mapledoc.txt, which can be found in the   #
##same online directory as this file                             #
##                                                               #
##Written by Nathan Fox, Rutgers University,                     #
##fox at math dot rutgers dot edu                                #
##################################################################

##Stuff for MapleDoc##
Input:=`Input`:
Output:=`Output`:
Note:=`Note`:
read(`mapledoc.txt`):

__doc:=DocManager():

checkinput:="check (optional): true or false (defaults to true)":
checknote:="If check is false, does not check for type errors in arguments.  This may speed up the code marginally, but it may also result in undefined behavior if the argument types are incorrect.":
errnote:="Never returns false; throws an error instead.":
rsq:="A: an increasing sequence of positive integers starting with 1":
##End Stuff for MapleDoc##

printf("%s\n\n%s\n\n%s@math.rutgers.edu\n\n%s\n%s\n\n%s\n%s\n",
    "This is subgames.txt",
    "It accompanies the article \"On Aperiodic Subtraction Games with Bounded Nim Sequence\" by Nathan Fox",
    "Please report bugs to fox",
    "The most current version of this package is available from",
    "http://www.math.rutgers.edu/~nhf12/research/subgames.txt",
    "For a list of the procedures in this package, along with their usage, type Help();.",
    "For help with a specific procedure, type Help(procedure_name);."):

##Error Checking Subroutines##

#Validate Integer Set
#Given S, is it a set of integers
#all of which are greater than or equal to lbd?
#If lbd is not an integer, then is S a set of integers?
register(__doc, "ValidateIntegerSet(S, [lbd])",
    Input::"S: some argument",
    Input::"lbd (optional): an integer",
    Output::"If lbd is specified, returns true if S is a set of ",
        "integers, all of which are greater than or equal to ",
        "lbd.\nIf lbd is not specified, returns true if S is a ",
        "set of integers.",
    Note::errnote
):
ValidateIntegerSet:=proc(S::set, lbd:=false) local l, s:
    if type(lbd, integer) then
        l:=lbd:
    else
        l:=-infinity:
    fi:
    #Make sure S is a set of correct-valued integers
    for s in S do
        if not type(s, integer) then
            error "S is not a set of integers":
        elif s < l then
            error "S is not a set of integers >= %1", l:
        fi:
    od:
    return true:
end:

#Validate Integer List
#Given L, is it a list of integers, all of which are
#greater than or equal to lbd?
#If lbd is not an integer, then is L a list of integers?
register(__doc, "ValidateIntegerList(L, [lbd])",
    Input::"L: some argument",
    Input::"lbd (optional): an integer",
    Output::"If lbd is specified, returns true if L is a list ",
        "of integers, all of which are greater than or equal to ",
        "lbd.\nIf lbd is not specified, returns true if L is a ",
        "list of integers.",
    Note::errnote
):
ValidateIntegerList:=proc(L::list, lbd:=false) local l, s:
    if type(lbd, integer) then
        l:=lbd:
    else
        l:=-infinity:
    fi:
    #Make sure L is a list of correct-valued integers
    for s in L do
        if not type(s, integer) then
            error "L is not a list of integers":
        elif s < l then
            error "L is not a list of integers >= %1", l:
        fi:
    od:
    return true:
end:

#Validate Representing Sequence
#Given A, is it a list of distinct integers starting with 1
#in increasing order?
register(__doc, "ValidateRepresentingSequence(A)",
    Input::"A: some argument",
    Output::"Returns whether A is a list of distinct integers ",
        "starting with 1 in increasing order.",
    Note::errnote
):
ValidateRepresentingSequence:=proc(A::list) local i:
    #Check everything that could go wrong
    if A[1] <> 1 then
        error "A[1] <> 1":
    fi:
    for i from 2 to nops(A) do
        if not type(A[i], integer) then
            error "A[%1] is not an integer", i:
        elif A[i] <= A[i-1] then
            error "A[%1] <= A[%2]", i, i-1:
        fi:
    od:
    return true:
end:

#Validate Zeckendorf Representation
#Given R, is it a list of zeroes and ones
#with no two consecutive ones?
register(__doc, "ValidateZeckendorf(R)",
    Input::"R: some argument",
    Output::"Returns whether R is a list of zeroes and ones ",
        "with no two consecutive ones.",
    Note::errnote
):
ValidateZeckendorf:=proc(R::list) local i:
    #Check everything that could go wrong
    if R[1] <> 0 and R[1] <> 1 then
        error "R[1] is neither 0 nor 1":
    fi:
    for i from 2 to nops(R) do
        if not type(R[i], integer) then
            error "R[%1] is not an integer", i:
        elif R[i] <> 0 and R[i] <> 1 then
            error "R[%1] is neither 0 nor 1", i:
        elif R[i] = 1 and R[i-1] = 1 then
            error "R contains consecutive ones in positions %1 and %2", i-1, i:
        fi:
    od:
    return true:
end:

#Validate Odd Index Fibonacci Representation
#Given R, is it a list of zeroes, ones, and twos
#such that every two is preceded (in the order of the list)
#by some number of ones and a zero (going backward, due to list
#order conventions)
register(__doc, "ValidateOddIndexFib(R)",
    Input::"R: some argument",
    Output::"Returns whether R is a list of zeroes, ones, and ",
        "twos such that every two is preceded (in the order of ",
        "the list) by some number of ones and a zero.",
    Note::"Preceding here means in the order of the list, which ",
        "is reversed from the order digital representations are ",
        "usually written in.",
    Note::errnote
):
ValidateOddIndexFib:=proc(R::list) local i, j:
    #Check everything that could go wrong
    if R[1] <> 0 and R[1] <> 1 and R[1] <> 2 then
        error "R[1] is not 0, 1, or 2":
    fi:
    for i from 2 to nops(R) do
        if not type(R[i], integer) then
            error "R[%1] is not an integer", i:
        elif R[i] <> 0 and R[i] <> 1 and R[i] <> 2 then
            error "R[%1] is not 0, 1, or 2", i:
        elif R[i] = 2 then
            for j from i-1 by -1 to 0 do
                if j = 0 or R[j] = 2 then
                    error "R contains an illegal 2 in position %1", i:
                    return false:
                elif R[j] = 0 then
                    break:
                fi:
            od:
        fi:
    od:
    return true:
end:

##Main Procedures##

##Minimal Excluded Element
#Given a finite set S of nonnegative integers, find the minimal
#excluded element of S, mex(S)
#if check is set to false, skips the error checking phase
register(__doc, "mex(S, [check])",
    Input::"S: a finite set of nonnegative integers",
    Input::checkinput,
    Output::"The minimal excluded element of S, mex(S)",
    Note::checknote,
    Example::["{0,1,3,5}", "returns 2"]
):
mex:=proc(S, check:=true) local s, m:
    #Error checking
    if check and not ValidateIntegerSet(S, 0) then
        return FAIL:
    fi:
    
    #Return the mex
    for m from 0 to nops(S) do
        if not(m in S) then
            return m:
        fi:
    od:
end:

##Legal Moves
#Given a finite subtraction set S
#returns the set of legal moves from position n
#if check is set to false, skips the error checking phase
register(__doc, "LegalMoves(S, n, [check])",
    Input::"S: a finite set of positive integers",
    Input::"n: a nonnegative integer",
    Input::checkinput,
    Output::"The set of legal moves from position n in the ",
        "subtraction game with subtraction set S",
    Note::checknote,
    Example::["{1,2,4,8}, 7", "returns {3,5,6}"]
):
LegalMoves:=proc(S, n, check:=true) local s, T:
    #Error checking
    if check then
        #Make sure S is a valid subtraction set
        if not ValidateIntegerSet(S, 1) then
            return FAIL:
        #Make sure n is a nonnegative integer
        elif not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n < 0 then
            printf("%s\n", "ERROR: n is not a nonnegative integer"):
            return FAIL:
        fi:
    fi:
    
    #Build the set
    T:={}:
    for s in S do
        if s <= n then
            T:=T union {n-s}:
        fi:
    od:
    return T:
end:

##Period and Prefix (Algorithm 3 in paper)
#Given a finite subtraction set S, find the period
#and prefix of its Nim sequence (returned as prefix, period)
#n is a tuning parameter of the algorithm. It defaults to 50.
#if check is set to false, skips the error checking phase
register(__doc, "GetPeriodAndPrefix(S, [n, [check]])",
    Input::"S: a finite set of positive integers",
    Input::"n (optional): a positive integer (defaults to 50)",
    Input::checkinput,
    Output:: "S union {i}, where i is the smallest integer ",
        "greater than or equal to start such that S union {i} ",
        "is a subtraction set with empty prefix, maximum Nim ",
        "value at most k, and not the same Nim sequence as S ",
        "(if no such i exists, runs forever)",
    Note::"This is Algorithm 1 in the paper.",
    Note::"The subtraction set S must have empty prefix.",
    Note::"The subtraction set S must have maximum Nim value ",
        "at most k.",
    Note::checknote,
    Example::["{2,4,7}", "returns [0, 0, 1, 1, 2, 2, 0, 3], [1, 0, 2]"]
):
GetPeriodAndPrefix:=proc(S, n:=50, check:=true)
local s, w, i, j, v, u, x, reps, maxs, ok, sqmex, nn:
    #Error checking
    if check then
        #Make sure S is a valid subtraction set
        if not ValidateIntegerSet(S, 1) then
            return FAIL:
        #Make sure n is a positive integer
        elif not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n <= 0 then
            printf("%s\n", "ERROR: n is not a positive integer"):
            return FAIL:
        fi:
    fi:
    
    #Local procedure
    #Mex of legal moves, according to sq
    sqmex:=proc(sq, pos) local i:
        return mex({seq(sq[i+1], i in LegalMoves(S, pos, false))}, false):
    end:
    
    #max of S
    maxs:=max(S):
    
    #Need to rename n so we can modify it
    nn:=n:
    
    #w will be the Nim sequence of S
    w:=[]:
    
    while true do
        while nops(w) < nn do
            w:=[op(w), sqmex(w, nops(w))]:
        od:
        #w is now the first nn terms of the Nim sequence of S
        for i from nn-1 by -1 to 2*maxs do
            #Find a potential period (increase in length to guarantee minimal period)
            v:=w[(i+1)..nops(w)]:
            #Check if v is a period
            reps:=ceil(2*maxs/nops(v))+1:
            x:=[]:
            for j from 1 to reps do
                x:=[op(x), op(v)]:
            od:
            #Does the proposed period repeat enough times?
            if w[nops(w)-nops(x)+1..nops(w)] = x then
                ok:=true:
                #The period repeats enough times! But, is is plausible?
                for j from maxs to nops(x)-1 do
                    if x[j+1] <> sqmex(x, j) then
                        #The period is not plausible
                        ok:=false:
                        break:
                    fi:
                od:
                if ok then
                    #The period is plausible!  Therefore, it is a period
                    u:=w[1..nops(w)-nops(v)]:
                    #Make the prefix minimal
                    while nops(u) > 0 and u[nops(u)] = v[nops(v)] do
                        v:=[v[nops(v)], op(1..nops(v)-1, v)]:
                        u:=u[1..nops(u)-1]:
                    od:
                    #The prefix and period are of minimal length
                    return u, v:
                fi:
            fi:
        od:
        #Double n and try again
        nn:=2*nn:
    od:
end:

##Digital Representations
#Given a nonnegative integer n and a representing sequence A,
#find the A-representation of n
#A is a list that starts with 1 and is sorted in increasing order
#return value has position i being the A[i] digit (so it's flipped
#from the usual convention)
#return value has length nops(A) (so may have leading zeroes)
#if check is set to false, skips the error checking phase
register(__doc, "DigitalRepresentation(n, A, [check])",
    Input::"n: a nonnegative integer",
    Input::rsq,
    Input::checkinput,
    Output::"The A-representation of n (returned as a list of ",
        "nonnegative integers whose ith entry is the A[i] digit)",
    Note::"The return value has length nops(A), so it may have ",
        "leading zeroes.",
    Note::checknote,
    Example::["12, [1,2,3,5,8]", "returns [1,0,1,0,1]"]
):
DigitalRepresentation:=proc(n, A, check:=true) local rep, m, i:
    if check then
        #Make sure n is a nonnegative integer
        if not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n < 0 then
            printf("%s\n", "ERROR: n is not a nonnegative integer"):
            return FAIL:
        fi:
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        fi:
    fi:
    
    #Build the representation (greedily)
    rep:=[0$nops(A)]:
    m:=n:
    for i from nops(A) by -1 to 1 do
        rep[i]:=rep[i] + floor(m/A[i]):
        m:=m mod A[i]:
    od:
    return rep:
end:

##Evaluate Digital Representation
#Given a representing sequence A and an A-representation R
#(a list of nonnegative integers of length at most nops(A), with
#our reversal convention)
#find the value that R represents (note: R may not be THE
#A-representation of that number)
#A is a list that starts with 1 and is sorted in increasing order
#if check is set to false, skips the error checking phase
register(__doc, "DigitalRepresentationValue(R, A, [check])",
    Input::"R: a list of nonnegative integers",
    Input::rsq,
    Input::checkinput,
    Output::"The number that R is an A-representation for",
    Note::"R[i] is the A[i] digit in the representation.",
    Note::"R must not be longer than A.",
    Note::"R may not be THE A-representation of the number.",
    Note::checknote,
    Example::["[1,0,1,0,1], [1,2,3,5,8]", "returns 12"]
):
DigitalRepresentationValue:=proc(R, A, check:=true) local i:
    if check then
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        fi:
        #Make sure R is a list of nonnegative integers
        if not ValidateIntegerList(R, 0) then
            return FAIL:
        fi:
        #Make sure R is not longer than A
        if nops(A) < nops(R) then
            printf("%s\n", "ERROR: R is longer than A"):
            return FAIL:
        fi:
    fi:
    
    return add(A[i]*R[i], i=1..nops(R)):
end:

##Index
#Given a nonnegative integer n and a representing sequence A,
#find the first index of n with repsect to A
#A is a list that starts with 1 and is sorted in increasing order
#if check is set to false, skips the error checking phase
register(__doc, "Index(n, A, [check])",
    Input::"n: a nonnegative integer",
    Input::rsq,
    Input::checkinput,
    Output::"The index of n with respect to the representing ",
        "sequence A (The integer j such that A[j+1]<=n<A[j+2])",
    Note::"This is Definition 12 in the paper.",
    Note::checknote,
    Example::["7, [1,2,5,13,34]", "returns 2"]
):
Index:=proc(n, A, check:=true)
    if check then
        #Make sure n is a nonnegative integer
        if not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n < 0 then
            printf("%s\n", "ERROR: n is not a nonnegative integer"):
            return FAIL:
        fi:
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif nops(A) < 2 then
            printf("%s\n", "ERROR: A does not have length at least 2"):
            return FAIL:
        fi:
    fi:
    return ListTools[BinaryPlace](A, n+1) - 1:
end:

##Representation Words
#Given a nonnegative integer n and a representing sequence A,
#find the first n+1 symbols in the representation word of A
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "RepresentationWord(n, A, [check])",
    Input::"n: a nonnegative integer",
    Input::rsq,
    Input::checkinput,
    Output::"The first n+1 symbols in the representation word ",
        "of the representing sequence A",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["7, [1,2,5,13,34]", "returns [0,1,0,1,2,0,1,0]"]
):
RepresentationWord:=proc(n, A, check:=true)
local w, i, dr, drnext:
    if check then
        #Make sure n is a nonnegative integer
        if not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n < 0 then
            printf("%s\n", "ERROR: n is not a nonnegative integer"):
            return FAIL:
        fi:
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif nops(A) < 2 then
            printf("%s\n", "ERROR: A does not have length at least 2"):
            return FAIL:
        fi:
    fi:
    
    #Build the word
    w:=[0]:
    drnext:=DigitalRepresentation(1, A, false):
    for i from 1 to n do
        dr:=drnext:
        drnext:=DigitalRepresentation(i+1, A, false):
        if drnext[1] = 0 and drnext[2] = 0 then
            #i is 2-volatile
            w:=[op(w), A[2]]:
        else
            #i is not 2-volatile
            w:=[op(w), dr[1]]:
        fi:
    od:
    return w:
end:

##Indexing into Representation Words
#Given a nonnegative integer i and a representing sequence A,
#find the ith symbol in the representation word of A
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "RepresentationWordIndex(i, A, [check])",
    Input::"i: a nonnegative integer",
    Input::rsq,
    Input::checkinput,
    Output::"The ith symbol (starting from 0) in the ",
        "representation word of the representing sequence A",
    Note::"This uses Theorem 3 in the paper.",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["7, [1,2,5,13,34]", "returns 0"]
):
RepresentationWordIndex:=proc(i, A, check:=true) local j:
    if check then
        #Make sure i is a nonnegative integer
        if not type(i, integer) then
            printf("%s\n", "ERROR: i is not an integer"):
            return FAIL:
        elif i < 0 then
            printf("%s\n", "ERROR: i is not a nonnegative integer"):
            return FAIL:
        fi:
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif nops(A) < 2 then
            printf("%s\n", "ERROR: A does not have length at least 2"):
            return FAIL:
        fi:
    fi:
    
    #Apply the theorem to find the element quickly
    if i < A[2] then
        return i:
    else
        j:=Index(i, A, false):
        if nops(A) >= j+2 and i = A[j+2] - 1 then
            return A[2]:
        else
            return RepresentationWordIndex(i-A[j+1], A, false):
        fi:
    fi:
end:

##T
#Given a representing sequence A,
#return the subtraction set T(A)
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "TSet(A, [check])",
    Input::rsq,
    Input::checkinput,
    Output::"The subtraction set T(A) ({A[i]-1|i>=3}U[A[2]-1])",
    Note::"This is the definition of T in Section 4.2 in the ",
        "paper.",
    Note::"This uses Theorem 3 in the paper.",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["[1,2,5,13,34]", "returns {1,4,12,33}"]
):
TSet:=proc(A, check:=true) local i:
    if check then
        #Make sure A is a representing sequence
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        fi:
    fi:
    
    return {seq(A[i]-1, i=3..nops(A))} union
        {seq(i, i=1..A[2]-1)}:
end:

##Greedy Algorithm
#Given a subtraction set S, integer start > max(S),
#and integer k>=2
#Verify that S has empty prefix and maximum Nim value at most k,
#and then find an element i>=start such that S union {i} is a
#subtraction set with empty prefix, maximum Nim value at most k,
#and not the same Nim sequence as S
#In that case, return S union {i}.
#(Run forever if no such i exists)
#if check is set to false, skips the error checking phase
register(__doc, "ExtendSet(S, start, k, [check])",
    Input::"S: a finite set of positive integers",
    Input::"start: an integer greater than max(S)",
    Input::"k: an integer greater than or equal to 2",
    Input::checkinput,
    Output::"S union {i}, where i is the smallest integer ",
        "greater than or equal to start such that S union {i} ",
        "is a subtraction set with empty prefix, maximum Nim ",
        "value at most k, and not the same Nim sequence as S ",
        "(if no such i exists, runs forever)",
    Note::"This is Algorithm 1 in the paper.",
    Note::"The subtraction set S must have empty prefix.",
    Note::"The subtraction set S must have maximum Nim value at ",
        "most k.",
    Note::checknote,
    Example::["{1,4,12}, 24, 2", "returns {1,4,12,28}"]
):
ExtendSet:=proc(S, start, k, check:=true)
local maxS, prefS, perS, i, T, prefT, perT:
    if check then
        if not ValidateIntegerSet(S, 1) then
            return FAIL:
        elif not type(k, integer) then
            printf("%s\n", "ERROR: k is not an integer"):
            return FAIL:
        elif k < 2 then
            printf("%s\n", "ERROR: k is not at least 2"):
            return FAIL:
        elif not type(start, integer) then
            printf("%s\n", "ERROR: start is not an integer"):
            return FAIL:
        fi:
    fi:
    
    #Get important parameters of S
    maxS:=max(S):
    if start <= maxS then
        printf("%s\n", "ERROR: start is not greater than max(S)"):
        return FAIL:
    fi:
    prefS, perS:=GetPeriodAndPrefix(S, 50, false):
    if nops(prefS) > 0 then
        printf("%s\n", "ERROR: pref(S) is not empty"):
        return FAIL:
    fi:
    
    #Try to find i
    i:=start:
    while true do
        T:=S union {i}:
        prefT, perT:=GetPeriodAndPrefix(T, 50, false):
        if nops(prefT) = 0 and perT <> perS and
                max(perT) <= k then
            return T:
        fi:
        i:=i+1:
    od:
end:

##Greedy Algorithm with Representations
#Given a representing sequence A, and a positive integer start
#such that the representation word of A is the Nim sequence of
#TSet(A) and such that start > A[-1],
#Find some j>=start such that, if B=[op(A), j], then the
#representation word of B is the Nim sequence of TSet(B), and it
#does not equal the representation word of A
#In that case, return B.
#(Run forever if no such j exists)
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "ExtendRepSeq(A, start, [check])",
    Input::rsq,
    Input::"start: an integer greater than the last entry in A",
    Input::checkinput,
    Output::"[op(A), j], where j is the smallest integer ",
        "greater than or equal to start such that the ",
        "representation word of [op(A), j] is the Nim sequence ",
        "of TSet([op(A), j]), and it does not equal the ",
        "representation word of A (if no such j exists, runs ",
        "forever)",
    Note::"This is Algorithm 2 in the paper.",
    Note::"The representation word of A must be the Nim ",
        "sequence of TSet(A).",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["[1,2,5,13], 27", "returns [1,2,5,13,29]"]
):
ExtendRepSeq:=proc(A, start, check:=true)
local AS, prefA, perA, rwA, j, B, BS, prefB, perB, rwB:
    if check then
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif not type(start, integer) then
            printf("%s\n", "ERROR: start is not an integer"):
            return FAIL:
        elif start <= A[-1] then
            printf("%s\n", "ERROR: start is not greater than A[-1]"):
            return FAIL:
        fi:
    fi:
    
    #Get important parameters of A
    AS:=TSet(A, false):
    prefA, perA:=GetPeriodAndPrefix(AS, 50, false):
    if nops(prefA) > 0 then
        printf("%s\n", "ERROR: the representation word of A is not the Nim sequence of TSet(A)"):
        return FAIL:
    fi:
    rwA:=RepresentationWord(2*nops(perA)-1, A, false):
    if rwA <> [op(perA), op(perA)] then
        printf("%s\n", "ERROR: the representation word of A is not the Nim sequence of TSet(A)"):
        return FAIL:
    fi:
    
    #Try to find j
    j:=start:
    while true do
        B:=[op(A), j]:
        BS:=TSet(B, false):
        prefB, perB:=GetPeriodAndPrefix(BS, 50, false):
        if nops(prefB) = 0 and perB <> perA then
            rwB:=RepresentationWord(2*nops(perB)-1, B, false):
            if rwB = [op(perB), op(perB)] then
                return B:
            fi:
        fi:
        j:=j+1:
    od:
end:

##Converting between Zeckendorf and Odd-Index-Fibonacci
#Given an odd-index-fibonacci representation R
#that ends (begins in our list convention) in 0
#but not a two-block,
#use the algorithm of the paper to convert it to a Zeckendorf
#representation for the same integer, where the Zeckendorf
#representation ends in an odd number of zeroes
#R has position i being the F(2i+1) digit (so it's flipped
#from the usual convention) (i going from 0 here)
#return value has position i being the F(i+2) digit
#if check is set to false, skips the error checking phase
register(__doc, "OddIndexFibToZeck(R, [check])",
    Input::"R: a list of zeroes, ones, and twos with D[1]=0 in ",
        "which every two is immediately preceded by some number ",
        "of ones preceded immediately by a zero",
    Input::checkinput,
    Output::"The Zeckendorf representation of the same integer ",
        "that D is an odd-index Fibonacci representation for",
    Note::"This is Algorithm 4 in the paper.",
    Note::"The returned list begins with an odd number of ",
        "zeroes.",
    Note::checknote,
    Example::["[0,2,0,1,0,1,2]", "returns [0,2,0,0,0,1,0,1,0,0,1,0,1]"]
):
OddIndexFibToZeck:=proc(R, check:=true) local i, E, onepair:
    if check then
        if not ValidateOddIndexFib(R) then
            return FAIL:
        elif R[1] <> 0 then
            printf("%s\n", "ERROR: R[1] is nonzero"):
            return FAIL:
        fi:
        for i from 2 to nops(R) do
            if D[i] = 2 then
                printf("%s%d%s\n", "ERROR: R ends in a two-block (2 in position ", i, ")"):
                return FAIL:
            elif R[i] = 0 then
                break:
            fi:
        od:
    fi:
    
    #Special annoying case
    if R = [0] then
        return [0]:
    fi:
    
    #Build E
    E:=ListTools[Interleave](R, [0$(nops(R)-1)]):
    E:=[E[1], op(3..nops(E), E)]:
    
    #From now on: add(E[i+1]*F(i+2), i=0..nops(E)-1) = n
    #From now on: E has an odd number of zeroes in its lowest indices
    
    #Remove twos from E
    for i from nops(E) by -1 to 3 do
        if E[i] = 2 then
            E[i]:=0:
            if i = nops(E) then
                E:=[op(E), 0]:
            fi:
            E[i+1]:=E[i+1]+1:
            E[i-2]:=E[i-2]+1:
        fi:
    od:
    
    #From now on: E contains only zeroes and ones
    
    #Remove pairs of consecutive ones from E
    onepair:=true:
    while onepair do
        onepair:=false:
        for i from nops(E) by -1 to 2 do
            if E[i] = 1 and E[i-1] = 1 then
                onepair:=true:
                E[i]:=0:
                E[i-1]:=0:
                if i = nops(E) then
                    E:=[op(E), 0]:
                fi:
                E[i+1]:=E[i+1]+1:
            fi:
        od:
    od:
    
    #E is now a valid Zeckendorf representation
    return E:
end:

##Promotions
#Given a representing sequence A, and a positive integer j,
#return the j-promotion of A.
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "Promotion(A, [j, [check]])",
    Input::rsq,
    Input::"j (optional): a positive integer (defaults to 1)",
    Input::checkinput,
    Output::"The j-promotion of the representing sequence A",
    Note::"This is Definition 18 in the paper.",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["[1,2,3,5,8,13]", "returns [1,3,4,7,11,18]"],
    Example::["[1,2,4,8,16,32], 3", "returns [1,2,4,12,24,48]"]
):
Promotion:=proc(A, j:=1, check:=true) local B, i, D, l:
    if check then
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif not type(j, integer) then
            printf("%s\n", "ERROR: j is not an integer"):
            return FAIL:
        elif j < 1 then
            printf("%s\n", "ERROR: j is not a positive integer"):
            return FAIL:
        fi:
    fi:
    
    #Construct the j-promotion
    B:=[]:
    for i from 1 to nops(A) do
        if i <= j then
            B:=[op(B), A[i]]:
        else
            D:=DigitalRepresentation(A[i]-1, A, false):
            if D[j] = 0 then
                B:=[op(B), 1 + add(D[l]*B[l], l=1..i-1)]:
            else
                B:=[op(B), 1 + add(D[l]*B[l], l=1..j-1) +
                    (D[j] + 1)*B[j] + add(D[l]*B[l], l=j+1..i-1)]:
            fi:
        fi:
    od:
    return B:
end:

##Promotion Functions
#Given a nonnegative integer n, a representing sequence A,
#and a positive integer j,
#return the j-promotion function of A applied to n.
#A is a list that starts with 1 and is sorted in increasing order
#Also, A must have length at least 2
#if check is set to false, skips the error checking phase
register(__doc, "PromotionFunction(n, A, [j, [check]])",
    Input::"n: a nonnegative integer",
    Input::rsq,
    Input::"j (optional): a positive integer (defaults to 1)",
    Input::checkinput,
    Output::"The j-promotion function of the representing ",
        "sequence A applied to n",
    Note::"This is Definition 19 in the paper.",
    Note::"A must have length at least 2.",
    Note::checknote,
    Example::["4, [1,2,3,5,8,13]", "returns 6"],
    Example::["19, [1,2,4,8,16,32], 3", "returns 27"]
):
PromotionFunction:=proc(n, A, j:=1, check:=true) local B, i, D, l:
    if check then
        if not ValidateRepresentingSequence(A) then
            return FAIL:
        elif not type(j, integer) then
            printf("%s\n", "ERROR: j is not an integer"):
            return FAIL:
        elif j < 1 then
            printf("%s\n", "ERROR: j is not a positive integer"):
            return FAIL:
        elif not type(n, integer) then
            printf("%s\n", "ERROR: n is not an integer"):
            return FAIL:
        elif n < 0 then
            printf("%s\n", "ERROR: n is not a nonnegative integer"):
            return FAIL:
        fi:
    fi:
    
    #Calculate the promotion function
    if n < A[j] then
        return n:
    fi:
    B:=Promotion(A, j, false):
    D:=DigitalRepresentation(n, A, false):
    if D[j] = 0 then
        return add(D[i]*B[i], i=1..nops(D)):
    else
        return add(D[i]*B[i], i=1..j-1) + (D[j] + 1)*B[j] +
            add(D[i]*B[i], i=j+1..nops(D)):
    fi:
end:

##Help Procedure##
Help:=getHelp(__doc):