A356080 Variation on Recamán's sequence (A005132) that is intended to be a permutation of the nonnegative integers, essentially as envisaged by the original comments in A078943. See comments below for details.

0, 1, 3, 6, 2, 7, 13, 20, 28, 37, 27, 16, 4, 17, 31, 46, 30, 47, 29, 48, 68, 89, 111, 134, 158, 133, 159, 132, 160, 131, 101, 70, 38, 5, 39, 74, 110, 147, 109, 148, 108, 149, 107, 150, 106, 151, 105, 58, 10, 59, 9, 60, 8, 61, 115, 170, 226, 283, 341, 400, 460, 399, 337, 274, 210, 145, 79, 12, 80, 11

Offset: 1

Author

Peter Munn, Jul 25 2022

Keywords

• nonn

Comments

a(1) = 0; for n >= 1, a(n+1) = a(n)-n or a(n)+n; and no two terms are equal.

Subject to the pairwise constraints above, the sequence describes a path between (nodes labeled with) nonnegative integers that is extended in stages so that the extended path ends with the least missing number from the unextended path.

We denote the number at the end of the unextended path as k, the path from 0 to k as P_k and the least number absent from P_k as m_k. We call a path that starts at k an extension route if it extends P_k and satisfies the pairwise constraints. [clarification added, Peter Munn, Aug 07 2024]

An extension route R_k from P_k is suitable if (1) R_k ends in m_k and (2) R_k is the start of a "look-ahead" extension route (R_k + R') that ends in a record number (i.e., greater than the largest in P_k + R_k). If there is no suitable R_k the sequence finishes at k. Otherwise we denote the lexicographically earliest shortest such R_k as E_m_k, and extend P_k as P_m_k = P_k + E_m_k.

Note that any E_m_k ends in m_k (i.e., without any look-ahead R' being included) and so E_k ends in k and beware the sequence might end there. Nevertheless, once we determine that the sequence continues and includes m_k (perhaps because at least 1 suitable R_k has been found) 1 or more terms of E_m_k will be known, and this is the point in time we may include terms after k in the published sequence.

Conjecture (Peter Munn): the sequence is infinite and so a permutation of the nonnegative integers.

Examples

			a(2) = a(1) + 1 = 1, since a(1) - 1 = -1 is a negative integer.
We now find the lexicographically earliest shortest route to the least missing number, 2. Any extension route has a(3) = a(2) + 2 = 3 since a(2) - 2 = -1 is a negative integer. Any extension route has a(4) = a(3) + 3 = 6, since a(3) - 3 = 0 is already in the sequence. So a(3) = 3, a(4) = 6, a(5) = a(4) - 4 = 2 is the only way to reach 2 by a(5); no shorter route exists. Lastly, we must check an onward route exists to a new record term (greater than 6). This is provided by a(6) = a(5) + 5 = 7, so we have determined a(3) = 3, a(4) = 6, a(5) = 2.
		

Links

• Peter Munn, Table of n, a(n) for n = 1..424
• Peter Munn and Ali Sada, Selection of relevant SeqFan posts, July 2022.
• Peter Munn, Initial validation program (LibreOffice Basic)

Crossrefs

Cf. A005132, A078943.

Formula

|a(n) - a(n+1)| = n.

If a(n) = a(m) then n = m.