#OK to post homework 
#Natalya Ter-Saakov, May 1, Assignment 26
read "C26.txt":

#Problem 2

#Problem 3

#SGwyt(a,b): finds 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,j,k,c,C:
option remember:
C:={seq([i,b], i=0..a-1), seq([a,j], j=0..b-1), seq([a-k,b-k], k=1..min(a,b))}:
mex({seq(SGwyt(op(c)), c in C)}):
end:


#Problem 4

#FindUP(L): inputs a list L and outputs a pair of lists L1,L2 such that (conjecturally) L=[op(L1),op(L2)^infinity]

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

#Problem 5

FindUP([seq(SGwyt(0,b)-b,b=0..100)])
#[],[0]

FindUP([seq(SGwyt(1,b)-b,b=0..100)])
#[], [1, 1, -2]

FindUP([seq(SGwyt(2,b)-b,b=0..100)])
#[], [2, -1, -1]

FindUP([seq(SGwyt(3,b)-b,b=0..100)])
#[3, 3, 3, 3, -2, -5, -5, 2], [2, 3, -2, -4, 3, -2]

FindUP([seq(SGwyt(4,b)-b,b=0..100)])
#[4, 4, 1, -1, 3, 1, 3, -7, -7], [-1, 3, 1, -1, 3, 1, -5, 3, 1, -1, -5, 1]

FindUP([seq(SGwyt(5,b)-b,b=0..100)])
#[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]

FindUP([seq(SGwyt(6,b)-b,b=0..500)])
#[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]

FindUP([seq(SGwyt(7,b)-b,b=0..1000)])
#[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]

FindUP([seq(SGwyt(8,b)-b,b=0..1000)])
#[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]

FindUP([seq(SGwyt(9,b)-b,b=0..1000)])
#[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]

FindUP([seq(SGwyt(10,b)-b,b=0..1000)])
#[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]