A389192 Lexicographically earliest sequence, where a(n) - a(n-1) is unique, and a(a(n)) = n.

0, 1, 3, 2, 6, 9, 4, 11, 16, 5, 13, 7, 18, 10, 20, 26, 8, 22, 12, 28, 14, 32, 17, 30, 39, 35, 15, 38, 19, 44, 23, 43, 21, 33, 48, 25, 46, 63, 27, 24, 50, 41, 60, 31, 29, 53, 36, 58, 34, 65, 40, 67, 95, 45, 74, 104, 56, 88, 47, 80, 42, 76, 69, 37, 82, 49, 85, 51

Offset

0,3

Comments

Self-inverse permutation of nonnegative numbers since a(a(n)) = n. - Michael S. Branicky, Sep 30 2025

Links

Michael S. Branicky, Table of n, a(n) for n = 0..10000

Index entries for sequences that are permutations of the natural numbers

Example

a(0) = 0, because lexicographically earliest term and a(a(n)) = n.
a(1) = 1, a(1) cannot be 0, because a(a(1)) = 1, then a(0) = 1, which is already given as a(0) = 0.
a(2) = 3, can neither be 0 or 1, nor 2, because a(1)-a(0) = 1.
a(3) = 2, because a(a(3)) = 3 and a(a(2)) = 2.

Prog

(Python)
from itertools import count, islice
def agen(): # generator of terms
    a, diffs = {0:0}, set(); yield 0
    for n in count(1):
        if n in a:
            an = a[n]
        else:
            an = n
            while True:
                while an-a[n-1] in diffs or an in a:
                    an += 1
                b = {k: a[k] for k in {n-1, n+1, an-1, an+1} if k in a}
                b[n], b[an] = an, n
                newdiffs = [b[k+1]-b[k] for k in b if k+1 in b]
                s = set(newdiffs)
                if len(newdiffs) == len(s) and diffs & s == set():
                    break
                an += 1
            a[n], a[an] = an, n
            diffs |= s
        yield an
print(list(islice(agen(), 68))) # Michael S. Branicky, Sep 25 2025
(Python)
def okseq(lst): # test whether initial list of values verifies constraints
    b = {k: lst[k] for k in range(len(lst))}
    diffs = [b[k+1]-b[k] for k in b if k+1 in b]
    return len(diffs) == len(set(diffs)) and all(b[b[k]] == k for k in b if b[k] in b)
assert okseq(list(islice(agen(), 68))) # Michael S. Branicky, Sep 26 2025

Crossrefs

Cf. A092569.

Sequence in context: A318049 A352877 A210754 * A210738 A210601 A389133

Adjacent sequences: A389189 A389190 A389191 * A389193 A389194 A389195

Keyword

nonn

Author

Marc Morgenegg, Sep 25 2025

Extensions

a(18) onward from Michael S. Branicky, Sep 25 2025

Status

approved