i-Mark: A new subtraction division game

Given two finite sets of integers S⊆N∖{0}S⊆N∖{0} and D⊆N∖{0,1}D⊆N∖{0,1}, the impartial combinatorial game i-Mark(S,D)i-Mark(S,D) is played on a heap of tokens. From a heap of n   tokens, each player can move either to a heap of n−sn−s tokens for some s∈Ss∈S, s≤ns≤n, or to a heap of n/dn/d tokens for some d∈Dd∈D if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n   tokens to a heap of ⌊n/d⌋⌊n/d⌋ tokens for any d∈Dd∈D.Under normal convention, it is observed that the Sprague–Grundy sequence of the game i-Mark(S,D)i-Mark(S,D) is aperiodic for any sets S and D. However, we prove that in many cases this sequence is almost periodic and that the sequence of winning positions is periodic. Moreover, in all these cases, the Sprague–Grundy value of a heap of n   tokens can be computed in time O(log⁡n)O(log⁡n).We also prove that under misère convention the outcome sequence of these games is purely periodic.