# restart; read `\G:/My Drive/Aek/SubtractTransferGame
# /Lengyel.txt`;

# First version: October 20, 2025

# Accompany paper:
# TWO DIMENSIONAL SUBTRACTION - TRANSFER GAMES
# by ALON DANAI, PAUL ELLIS, AND 
# THOTSAPORN AEK THANATIPANONDA.

#########################
# Section 1: 
# Functions for calculating Nim-values 
# and then finding periods
#
# Functions:
# Mex(S), STGame(Pos,Rule),
# 
# Per(A), PerX(A), SubPerX(A,p),
# PerY(A), SubPerY(A,q),
# 
##########################

# Input: The set of non-negative
# integers S
# Output: Mex function of S, i.e.
# the first non-negative integer
# missing from S
# Try: Mex({0,1,3,6,2,4,12});
Mex := proc(S) option remember;
local s;

s := 0;

while member(s,S) do 
	s := s+1;
od:

return(s);
end:

# Input: Starting postion "Pos" 
# i.e. list of [m,n] where m 
# and n are numbers of tokens,
# set of subtraction options "Rule".
# Output: Value of this subtraction-transfer game
# Try:
# Example of Larsson in his paper
# [seq([seq(STGame([n,m],{[-1,-3],[-2,-1]})
# ,n=0..20)],m=0..30)];
#
# S:={[-2,0],[0,-2],[-1,1]}:
# STGame([20,14],S);
# [seq(STGame([n,14],S),n=0..50)];
# [seq(STGame([20,n],S),n=0..50)];
# matrix([seq([seq(STGame([m,n],S),n=0..10)],m=0..5)]);
STGame := proc(Pos,Rule) option remember;
local a,S;

if {nops(Pos)} <> {seq(nops(Rule[i]),i=1..nops(Rule))} then
	ERROR("BadInput");
elif min(Pos)<0 then
	return({});
fi:

S := {seq(STGame(Pos+a,Rule),a in Rule)};
Mex(S);	

end:

#############################################

# Find the double period of 2D-List A
# Input: 2D-List of values of games
# Output: the list of pre-period length,
# length of row period, length of column period
#
# Try: 
# Per(Lengyel(2,2,20,20));
# [seq(Per(Lengyel(1,b,400,30)),b=1..5)];
# [seq(Per(LengStar(a,a,a,20,20)),a=1..5)];
# [seq(Per(LengStar(1,3,c,60+2*c*(c+1),12))
# ,c={1,3,5,7,9,11,13,15,17,19,21})];
Per := proc(A) option remember;
local M,N,B,st;

M := nops(A[1]);
N := nops(A);
B := A;
st := 1:

while PerX(B) = "No Period p" and st <= M/2 do
	st := st+1;
	B := [seq([seq(A[n][m],m=st..M)],n=1..N)];	
od:	

[st-1,PerX(B),PerY(A)];
end:

# Find the length of the row period
# Input: 2D-List of values of games
# Output: Length of row period
PerX := proc(A) option remember;
local p,M,N;

p := 1;
M := nops(A[1]);
N := nops(A);

while SubPerX(A,p) = false do
	if p >= floor(M/2) then
		return("No Period p");
	fi:	
	p :=p+1;
od:	

p;
end:

# Verify whether the row period is p
# Input: 2D-List of values of games and value p
# Output: true if length of row period is p
# and false otherwise.
# 
# Try:
# SubPerX(Lengyel(1,3,50,50),8);
SubPerX := proc(A,p) 
local k,s,t,M,S;

M := nops(A[1]);
for s from 1 to p do
for t from 1 to nops(A) do
	S := {seq(A[t][s+p*k],k=0..floor((M-s)/p))};
	if nops(S) > 1 then
		return(false);
	fi:	
od:
od:
true;
end:

# Find the length of column period
# Input: 2D-List of values of games
# Output: Length of column period
PerY := proc(A)
local q,M,N;

q := 1;
M := nops(A[1]);
N := nops(A);

while SubPerY(A,q) = false do
	if q = floor(N/2) then
		return([p,"No Period q"]);
	fi:	
	q :=q+1;
od:	
q;
end:


# Verify whether the column period is p
# Input: 2D-List of values of games and value q
# Output: true if length of column period is q
# and false otherwise.
# 
# Try:
# SubPerY(Lengyel(1,3,50,50),2);
SubPerY := proc(A,q)
local s,N,k;

N := nops(A);
for s from 1 to q do
	k := 1;
	while k <=floor((N-s)/q) and A[s] = A[s+q*k] do
		k := k+1;
	od:
	if k <= floor((N-s)/q) then
		return(false);
	fi:	
od:
true;
end:


#########################
# Section 2: 
# Verifying values that 
# mentioned in the paper
#
# Functions:
# Lengyel(b,x1,M,N),
# Alon(b,x1,y1,x2,y2,M,N),  
# TwoOptions(b,x1,y1,M,N),
#
# LengStar(a,b,c,M,N),
# GeneralGame(S,M,N) 
#
##########################

# Lengyel's style subtraction options:
# take b from pile1 or take x1 from pile2
# or transfer 1 token from pile1 to pile2.
# That is the set of substraction options is  
# S={[0,-b],[-x1,0],[-1,1]};
# 
# Input: positive integers b,x1,M,N
# Output: the nim-value of the subtraction-transfer game
# (of size M-by-N) with the options [0,-b],[-x1,0],[-1,1].
#
# Try:
# Thm1.3(a)
# A:=Lengyel(1,1,20,20):
# Per(A);
#
# Thm1.3(b)
# [seq(Per(Lengyel(2*b,2*b,20+4*b,20+4*b)),b=1..5)];
# Check the P-positions
# A:=Lengyel(6,6,10,10);
# B:=[seq([seq( (floor((x+y)/6)+x) mod 2,x=0..9)],y=0..9)];
# A-B;
#
# Thm1.3(c)
# A:=[seq(Per(Lengyel(1,x,20+2*x,20)),x=2..8)];
# B:=[seq([0,(x+1)*2,2],x=2..8)];
# A-B;
#
# Conjecture 1.4(a)
# A:=[seq(Per(Lengyel(b,b,20+4*b*(b+1),20+4*b))
# ,b in {3,5,7,9,11})];
# B:=[seq([0,2*b*(b+1),2*b],b in {3,5,7,9,11})];
# A-B;
#
# Conjecture 1.4(b)
# A:=[seq(Per(Lengyel(b,1,20+8*b,20+4*b)),b=2..10)];
# B:=[seq([0,4*b,2*b],b=2..10)];
# A-B;
#
# Theorem 1.5(b)
# A:=[seq(Per(Lengyel(b,5*b,20+4*b,20+4*b))
# ,b in {2,4,6,8,10,12,14,16})];
# B:=[seq([0,2*b,2*b],b in {2,4,6,8,10,12,14,16})];
# A-B;
#
# Theorem 1.5(c)
# A:=[seq(Per(Lengyel(b,2*b,20+4*b*(2*b+1),20+4*b)),b=1..6)];
# B:=[seq([0,2*b*(2*b+1),2*b],b=1..6)];
# A-B;
# A:=[seq(Per(Lengyel(b,3*b,20+4*b*(3*b+1),20+4*b))
# ,b in {1,3,5,7,9})];
# B:=[seq([0,2*b*(3*b+1),2*b],b in {1,3,5,7,9})];
# A-B;
#
# Figure 1 on page 2
# matrix(Lengyel(1,1,4,4));
#
# Figure 2 also on page 2
# matrix(Lengyel(2,3,16,4));
# 
# Lemma 2.1
# Lengyel(2,3,20,20);
#
# Figure 7 on page 8
# matrix(Lengyel(3,1,16,8));

Lengyel := proc(b,x1,M,N) option remember;
local S,m,n;

S := {[0,-b],[-x1,0],[-1,1]};
[seq([seq(STGame([m,n],S),m=0..M-1)],n=0..N-1)];
end:


# Definition 1.2: Lengyel transfer game,
# where the subtraction set is  
# S={[0,-b],[-x1,y1],[-x2,y2]};
# 
# Input: positive integers b,x1,y1,x2,y2,M,N
# Output: the nim-value of the subtraction-transfer game
# (of size M-by-N) with the options 
# [0,-b],[-x1,y1],[-x2,y2].
#
# Try:
# Lemma1.6
# A:=[seq(Per(Alon(b,3,3,2,1,30+4*b*(b+1),20+4*b)),b=1..10)];
# [seq( A[i][3],i=1..nops(A))]; 
#
# Conjecture1.7
# [seq(Per(Alon(b,3,3,2,1,30+4*b*(3+2),20+4*b))[2],b=1..12)];
# [seq(2*b*(3+2)/gcd(2*b,3+1),b=1..12)];
#
# Figure11 of Proposition 8.1 on page13
# matrix(Alon(1,3,0,2,1,10,2));
# matrix(Alon(1,3,0,4,1,10,2));
# seq(Per(Alon(1,2*a+1,0,2*a,1,8*a^2+4,4)),a=1..7);
#
Alon := proc(b,x1,y1,x2,y2,M,N) option remember;
local S,m,n;

S := {[0,-b],[-x1,y1],[-x2,y2]};
[seq([seq(STGame([m,n],S),m=0..M-1)],n=0..N-1)];
end:

# Simplified Lengyel transfer game,
# where the subtraction set is only  
# S={[0,-b],[-x1,y1]}.
# This game was mentioned in 
# Theorem 2.8 and Corollary 2.9
# 
# Input: positive integers b,x1,y1,M,N
# Output: the nim-value of the subtraction-transfer game
# (of size M-by-N) with the options 
# [0,-b],[-x1,y1],[-x2,y2].
#
# Try:
# Figure3 on page 4
# matrix(TwoOptions(2,1,1,8,4));
# matrix(TwoOptions(3,1,1,6,6));
#
# Theorem 2.8
# Example1:
# seq(Per(TwoOptions(3,1,y,50,50))[2],y={3,9,15,21,27,33});
# A:=[seq(Per(TwoOptions(3,1,y,50,50))[2]
# ,y={1,2,4,5,6,7,8,10})];
# B:=[seq(2*3/gcd(2*3,y+3),y={1,2,4,5,6,7,8,10})];
# A-B;
# 
# Example2:
# seq(Per(TwoOptions(4,2,y,50,50))[2],y={4,12,20,28,36,44});
# A:=[seq(Per(TwoOptions(4,2,y,50,50))[2]
# ,y=({seq(i,i=1..20)} minus {4,12,20}))];
# B:=[seq(2*4*2/gcd(2*4,y+4)
# ,y=({seq(i,i=1..20)} minus {4,12,20}))];
# A-B;
TwoOptions := proc(b,x1,y1,M,N) option remember;
local S,m,n;

S := {[0,-b],[-x1,y1]};
[seq([seq(STGame([m,n],S),m=0..M-1)],n=0..N-1)];
end:

####################################################

# Section 9: Lengyel's other conjecture
# Conjecture 3 in the paper of Lengyel
# Lengyel conjectured that the period
# of the game LengStar(b,b,b) is 
# (p,q)=(b+2,2b) (with no pre-period)
# 
# Input: positive integers a,b,c,M,N
# Output: the nim-value of the subtraction-transfer game
# (of size M-by-N) with the options [-a,0],[0,-b],
# [-1,1],[-2,2],...,[-c,c].
#
# Try:
# Per(LengStar(2,2,2,20,20));
# seq(Per(LengStar(b,b,b,20+2*b,4*b)),b=2..10);
#
# Figure13 on page15
# b:=6:
# LengStar(b,b,b,b+2,2*b);
LengStar := proc(a,b,c,M,N) option remember;
local i,m,n,S;

S := {[-a,0],[0,-b],seq([-i,i],i=1..c)};
[seq([seq(STGame([m,n],S),m=0..M-1)],n=0..N-1)];
end:

# General subraction-transfer 
# set for discussion in section 10
# Input: Set of options S and positive integers M,N
# Ouput: the nim-value of the subtraction-transfer game
# (of size M-by-N) with the options in S.
# 
# Try:
# Figure14 on page15
# S := {[0,-3],[-2,0],[-1,3],[-2,2],[-4,1]};
# GeneralGame(S,29,6);
#
# Figure15
# S := {[0,-2],[-1,0],[-3,-2],[-2,2]};
# GeneralGame(S,10,10);
#
# The last discussion before Question 6
# S := {[0,-3],[-2,0],[-1,3],[-2,2],[-3,1],[-1,-2]};
# GeneralGame(S,29,6);
#
# Short example of no period, although S
# is not a subtraction-transfer set
# Per(GeneralGame({[-1,-1],[-2,2]},100,100));
GeneralGame := proc(S,M,N) option remember;
local i,m,n;

[seq([seq(STGame([m,n],S),m=0..M-1)],n=0..N-1)];
end:

#############################
# Section 3: 
# Some procedures to make it easier
# to numerically verify the Lemmas 
# and Theorems in the paper.
#
# Functions:
# Thm28(b,x1,y1),
# Lem37(b,x1,y1,x2,y2),
# Lem61(b,x1,y1,x2,y2),
# Conj83(b,x1,x2,y2),
#
##############################

# Verify the claim in Theorem 2.8
# of the period of L(b;x1,y1) on 
# page 4. 
#
# Input: Positive integers b,x1,y1
# Output: The claimed Nim-value from the Theorem.
#
# Try:
# seq(seq(print(b,y1,[seq(Thm28(b,x1,y1)
# /Per(TwoOptions(b,x1,y1,10+4*b*x1,15+4*b))[2]
# ,x1=1..10)]),y1=1..b),b=1..9);
Thm28 := proc(b,x1,y1) option remember;

if (y1-b) mod (2*b) = 0 then
	1;	
else
	2*b*x1/gcd(2*b,b+y1);
fi:	
end:

# Verify the "not 2-columns" in Lemma 3.7
# on page 6. 
# Input: Positive integers b,x1,y1,x2,y2
# Output: true if the statement of "not 2-columns"
# is correct and false otherwise
#
# Try:
# [seq(Lem37(b,3,3,2,1),b=1..9)];
# [seq(Lem37(b,4,3,2,1),b=1..9)];
Lem37 := proc(b,x1,y1,x2,y2) option remember;
local s,i,j,col,row,A,S;

if x2 > x1 then
	ERROR("BadInput, x2>x1");
fi:

col := 30+4*b*(x1+x2)/gcd(2*b,y1+y2);
row := 2*b; 
A := Alon(b,x1,y1,x2,y2,col,row);
#print(A);
s := 0;

while s*(x1+x2)+x1 < col do
	for i from 0 to x1-1 do
		S := {seq( A[j][i+1+s*(x1+x2)],j=1..row)};
		if S subset {0,1} = false then
			print([seq( A[j][i+1+s*(x1+x2)],j=1..row)]);
			return(false);
		fi:
	od: 
s := s+1;
od:
true;
end:


# Lemma 6.1, Vector Elimination
# Input: Positive integers b,x1,y1,x2,y2
# Output: true if satisfies the condition
# and false otherwise
# Try:
# Lem61(3,1,5,2,1);
# Per(Alon(3,1,5,2,1,20,20));
# Per(TwoOptions(3,1,5,20,20));
Lem61 := proc(b,x1,y1,x2,y2) option remember;
local k;

if x1>x2 then
	return(Lem61(b,x2,y2,x1,y1));
fi:	

if type(x2/x1,integer) then
	k := x2/x1;
	if (k mod 2 =1 and y2-k*y1 mod 2*b =0)
	or (k mod 2 =0 and y2-k*y1-b mod 2*b =0) then
		return(true);
	fi:
fi:

return(false);
end:

# Conjecture8.3 of the period
# of the game L(b;x1,0,x2,y2).
# Input: Positive integers b,x1,x2,y2
# Output: the conjecture of the period
#
# Try:
# b:=6:
# seq(seq(print(y2,x1,[seq(Conj83(b,x1,x2,y2)
# /Per(Alon(b,x1,0,x2,y2,150+4*b*(x1+x2),15+4*b))[2]
# ,x2=1..10)]),x1=1..10),y2=1);

Conj83 := proc(b,x1,x2,y2) option remember;
local S,k;

S := 2*b*(x1+x2)/gcd(2*b,y2);

# Vector elimination	
if x2 mod x1 =0 and -y2 mod b = 0	
and x2/x1-y2/b mod 2 = 1 then
	#print("Vector1",[b,x1,x2,y2]);
	Thm28(b,x1,0);
elif x1 mod x2 =0 and (x1/x2*y2) mod b = 0	
and x1/x2*(1+y2/b) mod 2 = 1 then
	#print("Vector2",[b,x1,x2,y2]);
	Thm28(b,x2,y2);	
# y2-reduction Corollary2.3	 
elif y2 >= 2*b then
	Conj83(b,x1,x2,y2 mod 2*b);
# Stretching  Corollary2.7		
elif gcd(x1,x2) > 1 then
	k := gcd(x1,x2);
	k*Conj83(b,x1/k,x2/k,y2);
elif gcd(b,y2) > 1 then
	k := gcd(b,y2);  
	Conj83(b/k,x1,x2,y2/k);
	
# Main 1	
elif ([b,y2]=[1,1] or (b mod 2=1 and (y2=b-1 or y2=b+1)))
and [x1,x2]=[1,1]  then 
	2;
# Specific 1  Proposition8.1	
elif b=1 and y2=1 and x1 mod 2=1 and (x2=x1-1 or x2=x1+1) then
	2;	
# Specific 2  Proposition8.2			
elif b=2 and (y2=1 or y2=3) and [x1,x2]=[2,3]  then
	4;
# Specific 3 Proposition8.2		
elif b=3 and (y2=1 or y2=5) and [x1,x2]=[3,2]  then
	6;
else
	S;	
fi:	
end: