# OK to post homework
# Vikrant, May 01 2022, Assignment 26

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C26.txt"):

# ================================================================================
# 1. Project.
# ================================================================================

# Working on it.

# ================================================================================
# 2. Prove NimSum(a,b)=SGnim([a,b]).
# ================================================================================

#   SGnim([a,b]) 
# = mex({SGnim([i,b])|i=0..a-1} union {SGnim([a,i])|i=0..b-1})
# = mex({NimSum(i,b)|i=0..a-1} union {NimSum(a,i)|i=0..b-1}) by induction
# = mex(A union B).

# We claim that A={0,1,...,a}\{NimSum(a,b)} and B={0,1,...,b}\{NimSum(a,b)}.
# The following are basic properties of Xor (aka NimSum):
#   1. 0 <= Xor(a,b) <= a.
#   2. f(x) = Xor(x,b) is a bijection from N to N.
# From (1), A is a subset of {0,1,...,a} and, from (2), |A|=a.
# From (1), NimSum(a,b) is in {0,1,...,a} and, from (2), NimSum(a,b) is not in A.
# We therefore conclude that A={0,1,...,a}\{NimSum(a,b)}.
# A similar argument shows that B={0,1,...,b}\{NimSum(a,b)}.

# Thus,
#   mex(A union B)
# = mex({0,1,...,a}\{NimSum(a,b)} union {0,1,...,b}\{NimSum(a,b)})
# = NimSum(a,b).

# ================================================================================
# 3. Sprague-Grundy for Wythoff.
# ================================================================================

SGwyt:=
    proc(a,b)
        option remember:
        local i:
        mex({seq(SGwyt(a-i,b),i=1..a),seq(SGwyt(a,b-i),i=1..b),seq(SGwyt(a-i,b-i),i=1..min(a,b))}):
    end:

# ================================================================================
# 4. Eventual-period finding for lists.
# ================================================================================

FindUP:=
    proc(L)
        local i,L2:
        for i from 1 to nops(L) do
            L2:= FindPer([op(i..nops(L),L)]):
            if L2<>FAIL then
                return([op(1..i-1,L)],L2):
            fi:
        od:
        FAIL:
    end:

# ================================================================================
# 5. Conjecture eventual-period for Wythoff Sprague-Grundy numbers (fix left pile).
# ================================================================================

(*

n:= 10:
inf:= 1000:
for a from 0 to n do
    print(FindUP([seq(SGwyt(a,b)-b,b=0..inf)]));
od:

# a=0: [], [0]
# a=1: [], [1, 1, -2]
# a=2: [], [2, -1, -1]
# a=3: [3, 3, 3, 3, -2, -5, -5, 2], [2, 3, -2, -4, 3, -2]
# a=4: [4, 4, 1, -1, 3, 1, 3, -7, -7], [-1, 3, 1, -1, 3, 1, -5, 3, 1, -1, -5, 1]
# a=5: [...], [-2, 2, 3, -2, 2, 3, -2, 2, -6, -2, 2, 3, -2, 2, 3, -2, 2, 3, -7, 2, 3, -2, 2, -7]

*)

# ================================================================================
# 6. SGwyt(5,10^100)?
# ================================================================================

# (0) SGwyt(0,x)-x is certainly periodic and so, e.p. with period [0].
# (1) SGwyt(1,x)-x can be shown to be e.p. with period [1, 1, -2] using induction and (0) and SGwyt(1,x)<=x+2.
# (2) SGwyt(2,x)-x can be shown to be e.p. with period [2, -1, -1] using induction and (0) and (1) and SGwyt(2,x)<=x+4.
# (3) It's messy, but the same strategy ought to work?
# (4) It's messy, but the same strategy ought to work?
# (5) It's messy, but the same strategy ought to work?
# We leave (3), (4), (5) as conjectures because of laziness; one could probably write a program to do the proof for us.
# Conjecture: SGwyt(a,x) is eventually periodic for all a; there must be some nice way to show this rather than what's being done here.

# Suppose (5).
# The initial segment of SGwyt(5,x)-x has length 27.
# The period has length 24 and is P=[-2, 2, 3, -2, 2, 3, -2, 2, -6, -2, 2, 3, -2, 2, 3, -2, 2, 3, -7, 2, 3, -2, 2, -7].
# SGwyt(5,10^100)=10^100+2 since P[(10^100-26) mod 24]=2

# ================================================================================
# 7. <Skipped>
# ================================================================================

# Could not find a pattern, but SGwyt(10^100,2*10^100) seems harder than getting some sense of how the e.p. of SGwyt(a,x) changes as a changes since 2*10^100 probably falls in the initial segment of SGwyt(10^100,x), leaving us without any period to parlay.