#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 1
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

Help := proc(): print(`findUPi(L, i), findUP(L), fS(S,n)`): end:

#############
# Problem 3 #
#############

findUPi := proc(L, i) local M:
    if nops(L) < 3*i then:
        return FAIL;
    else:
        M := L[-i..-1]:
        if M = L[-2*i..-i-1] and M = L[-3*i..-2*i-1] then:
            return M:
        else:
            return FAIL:
        fi:
    fi:
end:

#############
# Problem 4 #
#############

findUP := proc(L) local i, M:
    for i from floor(nops(L)/3) by -1 to 1 do:
        M := findUPi(L, i):
        if M <> FAIL then:
            return M:
        fi:
    od:
    return FAIL:
end:


# From class:


#fS(S,n): inputs a set of pos. integers S and
#an integer n and outputs
#0 (1) if in a game of removing a member of S pennies
#is a losing (winning position)
fS:=proc(S,n) local i: option remember:
    if n<=0 then
        0:
    elif {seq(fS(S, n-i),i in S)}={1} then
        0:
    else
        1:
    fi:
end:


#############
# Problem 5 #
#############

# Human methods suffice to prove that the winning positions eventually
# become periodic for every subtraction game with finite subtraction
# set. This is because such a subtraction game can be modeled by a
# finite state machine with 2^max(S) states and constant input. Of
# course, this also tells us that the maximum period for such a game
# is 2^max(S).

# This value is rarely obtained, of course. Examples seemed to be all
# over the place and it was hard to figure out exactly what predicted
# long periods. I think it might be helpful to find a way to visualize
# the data, but I can't think of one.