A famously chaotic and unpredictable number sequence has been proven to never 'crash,' solving a long-standing worry about its mathematical consistency.
April 1, 2026
Original Paper
A Finite-State Proof of the Well-Definedness of a Perturbed Hofstadter Sequence
arXiv · 2603.29622
The Takeaway
The Hofstadter Q-sequence is notorious for being so erratic that mathematicians couldn't prove it wouldn't eventually try to calculate a value that doesn't exist, causing the sequence to fail. Researchers have finally proven that a version of this sequence is safe and will run forever, using a clever method that treats infinite math like a finite computer program.
From the abstract
We prove that the perturbed Hofstadter-type sequence Q(1)=1, Q(2)=1, and Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))+(-1)^n is well-defined for all n>=1, in the sense that all recursive arguments remain positive. This contrasts with the classical Hofstadter Q-sequence, for which global well-definedness remains open.The proof reduces the infinite recursion to a finite combinatorial constraint system. We introduce a symbolic encoding of local configurations, compute the finite set of admissible contexts, and con