The Generalized Bergman Game

MaRDI QIDQ6376522zbMATH OpenFDO

Authors Irfan Durmić, Henry L. Fleischmann, Faye Jackson, Steven J. Miller, Ethan Pesikoff, Luke Reifenberg

Publication date 31 August 2021

Has companion code repository https://github.com/fayealephnil/public-bergman-code

Mathematics Subject Classification ID

Probabilistic theory: distribution modulo (1); metric theory of algorithms (11K99) Additive number theory; partitions (11P99)

Abstract: Every positive integer may be written uniquely as a base-$$ decomposition--that is a legal sum of powers of $$--where $$ is the dominating root of a non-increasing positive linear recurrence sequence. Guided by earlier work on a two-player game which produces the Zeckendorf Decomposition of an integer (see [Bai+19]), we define a broad class of two-player games played on an infinite tuple of non-negative integers which decompose a positive integer into its base-$$ expansion. We call this game the Generalized Bergman Game. We prove that the longest possible Generalized Bergman game on an initial state $S$ with $n$ summands terminates in $Theta(n^2)$ time, and we also prove that the shortest possible Generalized Bergman game on an initial state terminates between $Omega(n)$ and $O(n^2)$ time. We also show a linear bound on the maximum length of the tuple used throughout the game.

This page was built for publication: The Generalized Bergman Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376522)