read(`code_utilities.txt`): Help_infsubgames:=proc() print(` LegalMovesGSC(n,sq) , SGGSC(n,sq) , SGGSCseq(n,sq) `): print(` SGGSCvalseq(n,sq,s) , SGGSCfirstseq(n,sq) `): print(` pwrfn(p) , expfn(b) , expfnno1(b) `): end: ##WHEREVER I WRITE "SIMPLE CANONICAL", MENTALLY REPLACE IT WITH ##"SUBTRACTION" #Legal moves for a simple canonical game on n counters where the #number of counters that can be removed is given by the sequence sq #which can be finite or infinite, in which case it should be #specified by a monotone increasing function indexed from 1 #All entries in the sequence must be positive LegalMovesGSC:=proc(n,sq) local sqseq,i,j,ret: if type(sq,symbol) or type(sq,`@`) then sqseq:={}: i:=1: while true do j:=sq(i): if j>n then break: fi: sqseq:=sqseq union {j}: i:=i+1: od: else sqseq:=sq: fi: ret:={}: for i in sqseq do if n-i>=0 then ret:=ret union {n-i}: fi: od: return ret: end: #Sprague-Grundy function for a simple canonical game on n counters #(with same sequence properties as LegalMovesSeq) SGGSC:=proc(n,sq) local lmoves,i: option remember: if n=0 then return 0: fi: lmoves:=LegalMovesGSC(n,sq): return mex({seq(SGGSC(i,sq),i in lmoves)}): end: #Sprague-Grundy sequence for a simple canonical game class #(with same sequence properties as LegalMovesSeq) #Sequence goes from 0 to n SGGSCseq:=proc(n,sq) local i: option remember: return seq(SGGSC(i,sq),i=0..n): end: #Sequence for a simple canonical game class of game sizes #with Sprague-Grundy value s #(with same sequence properties as LegalMovesSeq) #Sequence is upper bounded by n SGGSCvalseq:=proc(n,sq,s) local i,sqsg,ret: option remember: sqsg:=SGGSCseq(n,sq): ret:=[]: for i from 1 to nops([sqsg]) do if sqsg[i]=s then ret:=[op(ret),i-1]: fi: od: return op(ret): end: #Sequence for a simple canonical game class of game sizes indexed #from 0 where the ith term is the smallest pile size with #Sprague-Grundy value i #Values are capped at n, -1 indicates value not found SGGSCfirstseq:=proc(n,sq) local i,s,sqsg,ret: sqsg:=SGGSCseq(n,sq): ret:=[]: s:={}: for i from 1 to nops([sqsg]) do if not(sqsg[i] in s) then while nops(ret) < sqsg[i] + 1 do ret:=[op(ret),-1]: od: ret[sqsg[i] + 1]:=i-1: s:=s union {sqsg[i]}: fi: od: return op(ret): end: ##TESTING PROCEDURES pwrfn:=proc(p) local f: f:=proc(n) return n^p: end: return f: end: expfn:=proc(b) local f: f:=proc(n) return b^(n-1): end: return f: end: expfnno1:=proc(b) local f: f:=proc(n) return b^n: end: return f: end: #####TESTING SEQUENCES #fibonacci(n): A014588 (SG function) #0, 4, 10, 14, 20, 24, 30, 36, 40, 46, 50, 56, 60, 66, 72, 76, 82, 86, 92, 96 (SG=0) #ithprime(i): A025043 (SG=0), A014589 (SG function), #0, 2, 4, 6, 8, 19, 21, 23, 43, 48, 67, 156 (firsts seq) #squares: A030193 (SG=0), A014586 (SG function) #0, 1, 4, 25, 28, 29, 75, 103, 200, 234, 315, 364, 479, 633, 802 (firsts seq) #factorials: A014587 (SG function) #0, 3, 7, 10, 14, 17, 21, 25, 28, 32, 35, 39, 42, 46, 50, 53, 57, 60, 64, 67 (SG=0) #cubes: 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1 (SG function) #0, 2, 4, 6, 9, 11, 13, 15, 18, 20, 22, 24, 34, 37, 39, 41, 43, 46, 48, 50, 52 (SG=0) #0, 1, 8, 27, 128, 378, 515, 892, 1991 (firsts seq) #n^n: 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 25, 28, 30, 33, 35, 38, 40, 43, 45, 48, 50 (SG=0) #0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0 (SG function) ##I GOOFED UP HERE, AND ALL THESE EXPONENTIAL RESULTS DO NOT ALLOW ##REMOVING A SINGLE COUNTER ##WHEN THAT IS ALLOWED, THE BLOCKS HAVE SIZE 1 IN THE INTEGRAL CASE #powers of 2: A131555 (SG function), A047225 (SG=0) #Note: this case is trivial, but not noted in OEIS #Other integer exponentials appear to be periodic as well #Block sizes are b #blocks alternate between 0 and 1 for odd b #period has b/2 blocks of 0, b/2 blocks of 1 (alternating) and a terminal block of 2s for even b #floor(e^n) excluding 1: A000149 (removable quantities) #0, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 1, 0, 0, 1 (SG function) #0, 1, 4, 5, 9, 10, 13, 14, 18, 19, 22, 23, 27, 28, 31, 32, 36, 37, 40, 41, 45 (SG=0) #0, 2, 8, 55, 61, 229, 1300, 3586 (firsts seq) #ceil(e^n) excluding 1: A001671 (removable quantities) #0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 1, 3, 2, 0 (SG function) #0, 1, 2, 6, 7, 11, 12, 13, 17, 18, 24, 29, 30, 31, 35, 36, 40, 41, 42, 46, 47 (SG=0) #0, 3, 8, 22, 159, 162, 3637 (firsts seq) #round(e^n) excluding 1: A000227 (removable quantities) #0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 3, 3, 2, 2, 0, 0 (SG function) #0, 1, 2, 6, 10, 11, 12, 16, 24, 25, 29, 33, 34, 35, 39, 43, 47, 48, 52, 58, 60 (SG=0) #0, 3, 7, 20, 69, 427,8200,9561 (firsts seq) #floor(e^n): A000149 (removable quantities) #0, 1, 2, 0, 1, 2, 0, 1, 2 [with some really weird behavior once ina while] (SG function) #0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 61, 64, 67 (SG=0) #0, 1, 2, 54, 55, 56, 474, 1414, 3478 (firsts seq) #ceil(e^n): A001671 (removable quantities) #0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1 (SG function) #0, 2, 4, 6, 11, 13, 15, 17, 22, 24, 26, 28, 33, 35, 37, 39, 44, 46, 48, 50, 62 (SG=0) #0, 1, 8, 9, 60, 61, 3152 (firsts seq) #round(e^n): A000227 (removable quantities) #0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 2, 3, 2, 3 (SG function) #0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 54 (SG=0) #0, 1, 20, 21, 1108, 1109, 1143 (firsts seq) #####INTERESTING SEQUENCES #3,25,27,85,244,730,2193: First value where SG function equals 3 in take n^th power game (n>=1) (Note: 3 is first interesting case. 0 is always 0, 1 is always 1, 2 is always 2^n) #0,16,0,4,1,1,6: Previous sequence minus 3^n #####NOTES: #Look at E26 in Guy's Unsolved Problems in Number Theory #Any sequence containing only odd numbers and containing 1 will have SG sequence 0,1,0,1,0,1,0,1,... (A000035) #I wish OEIS had a monotone tag #I would like to be able to go through OEIS and run these programs on sequences and see which are interesting #If the allowed move sequence is finite, SG fn is bounded above by its size minus 1 (easy) and is periodic (easy?) [find out what's known here]