# Order and Chaos in Hofstadter's Q(n) Sequence

Source: [Order and Chaos in Hofstadter's Q(n) Sequence](<https://www.sota2.com/research/paper/68fa23ce2c2a37601939c614>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-24T07:44:58.578Z

Authors: K. Pinn

Published: 1998-03-10T14:19:16.000Z

## Abstract

A number of observations are made on Hofstadter's integer sequence defined by Q(n)= Q(n-Q(n-1))+Q(n-Q(n-2)), for n \> 2, and Q(1)=Q(2)=1. On short scales the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k-th generation has 2\*\*k members which have \`\`parents'' mostly in generation k-1, and a few from generation k-2. In this sense the series becomes Fibonacci type on a logarithmic scale. The mean square size of S(n)=Q(n)-n/2, averaged over generations is like 2\*\*(alpha\*k), with exponent alpha = 0.88(1). The probability distribution p^\*(x) of x = R(n)= S(n)/n\*\*alpha, n \>\> 1, is well defined and is strongly non-Gaussian. The probability distribution of x\_m = R(n)-R(n-m) is given by p\_m(x\_m)= lambda\_m \* p^\*(x\_m/lambda\_m). It is conjectured that lambda\_m goes to sqrt(2) for large m.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/chao-dyn/9803012>)

[PDF](<https://arxiv.org/pdf/chao-dyn/9803012.pdf>)