# Presentation

Classification of Periodicity in Subtraction Game Sequences

SessionPoster Session

Author

Event Type

Posters

Receptions

Student Posters

VisDataAnalytics

Applications

Student Program

Facilitation

Workforce

TimeTuesday, July 246:30pm - 8:30pm

LocationKings Garden 3-4-5

DescriptionThe classic game of nim requires two players to take turns removing beans from one of several non empty pile. The game ends when there are no more beans to remove, and the last person to move is declared the winner. Given a certain starting set, it can be determined which player has the ability to win if they make all the correct subsequent moves. The subtraction game is a modified version of the classic game of Nim where the number of beans a player can remove from a pile is restricted by a subtraction set. We can determine winning positions of this game by using a recursive function to record a “nim sequence” that indicates a player’s ability to win the game given any initial conditions These sequences are known to be periodic, but the relationship between the subtraction set and the period length is currently unknown subtraction sets of cardinality four. A complete analysis has already been completed for the sets {1, b, c} and {a, b, c} such that a < b < c < 32. I am using the Sprague-Grundy function, the Knuth-Morris-Pratt compression algorithm, and the Purdue community clusters to compute the periodicity of the four variable case {a, b, c, d | a < b < c < 2024}. Thus far I have found that the periodicity is positively correlated with how big the elements in the subtraction set are. Also there are clear outliers in the set that are significantly their neighbors although I haven't yet determined the cause of the outliers.