The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909215336955904 |
|---|---|
| author | Fox, Nathan |
| author_facet | Fox, Nathan |
| contents | In this paper, we study the three-term nested recurrence relation $B(n)=B(n-B(n-1))+B(n-B(n-2))+B(n-B(n-3))$ subject to initial conditions where the first $N$ terms are the integers $1$ through $N$. This recurrence is the three-term analog of Hofstadter's famous $Q$-recurrence $Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))$. Nested recurrences are highly sensitive to their initial conditions. Some initial conditions lead to finite sequences, others lead to predictable sequences, and yet others lead to sequences that appear to be chaotic and infinite. A corresponding study to this one was previously carried out on the $Q$-recurrence. As with that work, we consider two families of sequences, one where terms with nonpositive indices are undefined and a second where terms with nonpositive indices are defined to be zero. We find similar results here as with the $Q$-recurrence, as we can completely characterize the sequences for sufficiently large $N$. The results here are, in a sense, simpler, as our sequences are all finite for sufficiently large $N$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00904 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions Fox, Nathan Number Theory Combinatorics 11B37 In this paper, we study the three-term nested recurrence relation $B(n)=B(n-B(n-1))+B(n-B(n-2))+B(n-B(n-3))$ subject to initial conditions where the first $N$ terms are the integers $1$ through $N$. This recurrence is the three-term analog of Hofstadter's famous $Q$-recurrence $Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))$. Nested recurrences are highly sensitive to their initial conditions. Some initial conditions lead to finite sequences, others lead to predictable sequences, and yet others lead to sequences that appear to be chaotic and infinite. A corresponding study to this one was previously carried out on the $Q$-recurrence. As with that work, we consider two families of sequences, one where terms with nonpositive indices are undefined and a second where terms with nonpositive indices are defined to be zero. We find similar results here as with the $Q$-recurrence, as we can completely characterize the sequences for sufficiently large $N$. The results here are, in a sense, simpler, as our sequences are all finite for sufficiently large $N$. |
| title | The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions |
| topic | Number Theory Combinatorics 11B37 |
| url | https://arxiv.org/abs/2406.00904 |