Sprague-Grundy Functions for Certain Infinite Acyclic Graphs

We study the Sprague-Grundy functions of certain 2-player combinatorial games with the positive integers as the positions. One such game, called SAD (Subtract A Divisor), allows an integer to be reduced by a proper divisor. The game graph has the positive integers as vertices with a directed edge from q to \(q-d\) for each proper divisor \(d\mid q.\) This is an acyclic directed graph with only finitely many vertices reachable from each given one. It thus has, as is usual, a unique Sprague-Grundy function. It turns out that this function is the 2-adic valuation \(\nu \) . If we reverse the direction of the edges the vertices are still the positive integers with a directed edge from q to \(q+d\) for any divisor \(d\mid q\) including \(d=q\) . We consider the various Sprague-Grundy functions of this unbounded graph, one of which is \(\nu \) . If we restrict the graph to a finite interval [1, T],  there is again a unique Sprague-Grundy function, \(g_T\) . We investigate \(\lim _{T \rightarrow \infty }g_T\) and provide strong empirical evidence that the limit is \(\nu .\)