A359008 Jane Street's infinite sidewalk's greedy walk inverse mapping.

0, 1, 2, 5, 3, 6, 9, 4, 7, 15, 10, 29, 13, 8, 16, 27, 11, 30, 49, 14, 60, 25, 17, 28, 47, 12, 31, 58, 50, 23, 34, 61, 26, 45, 18, 64, 56, 48, 75, 21, 32, 59, 105, 51, 24, 70, 35, 62, 54, 81, 46, 73, 19, 65, 111, 57, 103, 214, 76, 22, 68, 33, 244, 87, 106, 52

Offset: 0

Author

Frederic Ruget, Dec 11 2022

Keywords

• nonn

Comments

For n a nonnegative integer, a(n) is the smallest nonnegative integer i such that A359005(i) == n.

In fact, if a(n) exists, it is actually the unique nonnegative integer i such that A359005(i) == n. ({A359005(n)} is demonstrably an injective mapping from the nonnegative integers onto themselves.)

It is conjectured that a(n) exists for all nonnegative n. This has been verified true with a computer for all n < 7884654. This would make {a(n)} a one-to-one mapping from the nonnegative integers onto themselves.

References

• Inverse mapping of A359005.

Links

• Neal Gersh Tolunsky, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A358838, A359005.

Programs

Python

def a(n: int) -> int:
    if n < 0: raise Exception("n must be a nonnegative integer")
    i = 0
    if n == 0: return i
    visited = {0}
    slab = 1
    while True:
        i += 1
        if slab == n: return i
        visited.add(slab)
        label = 1 + (slab >> 1)
        if not slab - label in visited:
            slab -= label  # jumping backwards
        else:
            slab += label  # jumping forwards
            if slab in visited: raise Exception(f"blocked at slab {slab}")