A394051 Hofstadter Q-sequence perturbed by (-1)^n.

1, 1, 1, 3, 3, 3, 5, 5, 5, 7, 5, 9, 7, 9, 7, 11, 9, 11, 11, 11, 13, 11, 15, 13, 15, 13, 17, 13, 19, 15, 19, 17, 19, 17, 21, 19, 21, 21, 21, 23, 21, 25, 21, 27, 23, 27, 23, 29, 23, 31, 23, 33, 25, 33, 25, 35, 27, 35, 29, 35, 29, 37, 29, 39, 31, 39, 31, 41, 33, 41, 35, 41, 37, 41

Offset

1,4

Comments

All terms are odd.

Numerical evidence suggests that a(n) ~ n/2.

The sequence does not terminate for all n <= 3*10^10 (verified computationally).

The differences a(n+1)-a(n) exhibit a dyadic, self-similar pattern on a logarithmic scale.

Links

Marco Mantovanelli, Table of n, a(n) for n = 1..2000

Benoit Cloitre, On a perturbed Hofstadter Q-recursion, arXiv:2604.06237 [math.NT], 2026.

Marco Mantovanelli, Dyadic Self-Similarity in a Perturbed Hofstadter Q-Recursion, arXiv:2603.16111 [math.CO], 2026.

Marco Mantovanelli, Preprint: Dyadic Self-Similarity in a Perturbed Hofstadter Q-Recursion.

Marco Mantovanelli, Certified Finite-State Induction for a Perturbed Hofstadter Recursion, arXiv:2603.29622 [math.CO], 2026. See p. 3.

Formula

a(1)=a(2)=1; for n > 2: a(n) = a(n-a(n-1)) + a(n-a(n-2)) + (-1)^n.

a(n)/n = 1/2 + O(1/sqrt(log(n))). - Benoit Cloitre, Apr 03 2026

More precisely it can be proved that limsup_{n->oo} sqrt(log_2(n)) * |a(n)/n - 1/2| = 1/(3*sqrt(2*Pi)). - Benoit Cloitre, Apr 08 2026

Mathematica

Q[1] = 1; Q[2] = 1;
Q[n_Integer?Positive] := Q[n] = Q[n - Q[n - 1]] + Q[n - Q[n - 2]] + (-1)^n;
Table[Q[n], {n, 1, 350}]

Crossrefs

Cf. A005185.

Sequence in context: A001650 A130175 A200266 * A101290 A080605 A130823

Adjacent sequences: A394048 A394049 A394050 * A394052 A394053 A394054

Keyword

nonn,look

Author

Marco Mantovanelli, Mar 08 2026

Status

approved