# Please do not post 
# Daniela Elizondo
# Assignment 26
# May 1, 2022

read "C26.txt":


##### Problem 3 #####
# SGwyt(a,b): the Sprague-Grundy value of the position [a,b] in Wythoff's game
# whose rules are the same as 2-pile Nim, except that one can also remove the SAME number of pennies from both piles.

SGwyt := proc(a,b) local i,c, C:
option remember:
C := {seq([a-i,b], i=1..a), seq([a,b-i], i=1..b), seq([a-i,b-i], i=1..min(a,b))}:
mex({seq(SGwyt(c[1], c[2]),c in C)}):
end:

##### Problem 4 #####
# FindUP(L): inputs a list L and outputs a pair of lists L1,L2 such that (conjecturally)

FindUP := proc(L) local n, L1, L2, i:
n := nops(L):
L1 := []:
L2 := FindPer(L):

for i from 1 to n while L2 = FAIL do:
    L1 := [op(L1), L[i]]:
    L2 := FindPer([op(i+1..n, L)]):
od:

(L1, L2):
end:

##### Problem 5 #####
#By using FindUP(L) and SGwyt(a,b), find(if possible) conjectured ultimate periodic descriptions of
# [seq(SGwyt(i,b)-b,b=0..infinity)]
# for i=0,1,2,3 (the further the better!) 

# I ran the following
#for i from 0 to 10 do:
#    print(FindUP([seq(SGwyt(i,b)-b,b=0..1000)]));
#od:

# Output
# i=0: [], [0]

# i=1: [], [1, 1, -2]

# i=2: [], [2, -1, -1]

# i=3: [3, 3, 3, 3, -2, -5, -5, 2], [2, 3, -2, -4, 3, -2]

# i=4: [4, 4, 1, -1, 3, 1, 3, -7, -7], [-1, 3, 1, -1, 3, 1, -5, 3, 1, -1, -5, 1]

# i= 5: [5, 2, 2, -3, 2, 3, 4, -6, -6, -2, 2, 3, -3, 2, 3, -2, 2, -6, -2, 
#  2, 3, -2, 2, 3, -2, 2, -6], [-2, 2, 3, -2, 2, 3, -2, 2, -6, -2, 
#  2, 3, -2, 2, 3, -2, 2, 3, -7, 2, 3, -2, 2, -7]

# i=6: [6, 6, 6, -2, 5, 5, -3, -3, -3, 4, -10, -9, 4, 4, 4, -3, 4, -3, 
#  -3, -8, 4, 4, 4, 4, -3, 4, 4, -8, 4, 2, -8, -8, 4, 4, 4, -7, -3
#  ], [4, 4, 4, 4, 4, -8, -8, 4, 4, 4, -8, -8]

# i=7: [7, 7, 4, 6, -4, -4, -2, -2, -5, 5, 5, 2, 5, -11, -4, 4, 5, -5, 
#  4, -3, 5, -10, -4, 5, 5, 5, 5, -3, 5, -9, -4, -4, 5, -10, 5, 5, 
#  5, -3, 5, -3, -8, 5, -4, 4, 5, -10, -4, 4, -3, 5, 5, -3, -8, 5, 
#  -4, -3, 5, 5, 5, 5, -3, 5, -9, -3, -8, 2, 4, 4, 5, -10, 5, 5, 
#  -3, -8, 5, -3, -8, 5, -4, 4, 5, -3, 5, 5, -3, 5, -9, -3, -8, 2, 
#  -4, 3], [5, 5, 5, 5, -3, -8, 5, -3, -8, 5, 5, 5, 5, -10, -4, 4, 
#  -3, 5, -9, -1, -8, 2, 4, -3]

#i=8: [8, 5, 5, 7, -3, -3, -1, -4, -4, 6, 6, 6, 6, -13, -5, -1, -4, 2, 
#  5, 5, 6, 6, 6, -12, -11, -4, -4, 5, -3, 5, 5, -11, -3, 5, -4, 
#  6, 6, -4, 6, 6, -3, -10, -6, -4, -4, -2, 5, 5, 5, 6, -4, -1, 
#  -3, -5, 5, 3, -9, 6, -4, -3, 5, 6, -5, -1, -3, -5, 5, 5, -4, 5, 
#  -4, -3, 5, 5, -5, 5, -3, 6, 6, -4, -4, -11, -3, 3, 5, 6, -5, 5, 
#  -3, 5, 5, -4, -4, -11, -4, 6, 6, 6, -5, -1, -3, -5], [6, -4, 
#  -4, 5, 5, -3, 4, 6, -5, 5, -3, 5, 5, 5, -9, -11, -4, 6, 6, 6, 
#  -5, -10, -3, -3]

# i=9: [9, 9, 9, 9, 4, 2, 7, 7, 7, 7, 7, -5, 7, -8, -13, -15, -14, -14, 
#  -14, 3, 7, 7, 7, -5, -4, 6, -3, 6, -7, -3, -6, 3, 6, 6, 6, -3, 
#  -11, -7, -3, 7, 7, 2, -5, 5, -3, 5, 6, -11, -4, -7, 3, -6, 5, 
#  2, -5, 5, -5, 7, 7, 2, -6, -3, -3, 5, 5, -3, 6, -11, -5, 6, -3, 
#  2, -6, -3, -3, 6, 6, -3, 7, -3, -3, 5, 6, -3, -6, 7, -3, 6, 6, 
#  6, -11, -7, -3, -6, -3, 2, -6, 7, 3, 6, 6, -3, 7, -7, 6, -6, 
#  -3, -5, 5, 7, -10, -4, 5, -5, 6, 3, -5, 6, -3, 2, -6, 7, -10, 
#  -4, 5, 2, 4], [-3, -6, -4, 6, -5, 5, 7, -3, 6, 6, -5, -5, 6, 
#  -6, -6, -3, 4, -6, 7, -3, 6, 6, 2, -6]

# i=10: [10, 10, 7, 5, 9, 7, -6, 8, 8, 8, 4, 7, -5, -7, -12, -12, -15, 
#  -13, -13, 4, 8, 5, 5, -3, -5, -3, 3, 4, 6, 4, 6, -6, -8, -12, 
#  7, 4, 4, -5, 7, -1, -5, 7, -12, 3, 6, 6, 7, -3, -6, -12, -3, 5, 
#  6, 6, 6, 6, -13, 8, 8, 3, -5, -12, -8, -11, 6, -8, 7, 7, 7, -2, 
#  -7, 6, -4, 6, 6, -11, -5, -8, 4, -7, 6, 6, 7, 7, 4, 8, -8, -11, 
#  -5, -8, 4, -6, 6, -2, 6, -3, -12, 5, -3, 5, 7, 7, 4, -6, -3, 6, 
#  6, 6, -12, -6, 5, 6, -13, -8, 7, -6, 6, 7, 7, -3, 7, -3, -8, 
#  -13, 6, 6, 7, -7, 6, 6, -11, 6, -4, 8, -8, 7, -13, -8, 6, -7, 
#  -4, -2, 6, -3, 5, 5, -8, -1, -5, 6, 4, -6, 6, 6, -7, 6, -5, 8, 
#  5, 7, 7, -8, 6, -7, -12, 6, 6, -3, 5, -12, -8, -11, 7, 7, -4, 
#  -6, 6, 6, 7, 7, -5, -3, -8, 7, 7, -8, 6, 7, -12, -2, 6, -3, 5, 
#  -12, 7, -11, 7, -8, 4, -6, 6, 6, -7, 6, -5, 8, -8, 7, 7, 7, 7, 
#  -7, -12, -2, 6, -3, 5, -12, -8, -11, 7, 7, -4, 3], [6, 6, -7, 
#  6, -5, 8, -8, 7, 7, -8, 6, 7, -12, -2, 6, -3, 5, -12, -8, -11, 
#  7, 7, 4, -6]