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,3

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

Prog

(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}")

Crossrefs

Cf. A358838, A359005.

Sequence in context: A256997 A335499 A358838 * A239970 A111202 A194280

Adjacent sequences: A359005 A359006 A359007 * A359009 A359010 A359011

Keyword

nonn

Author

Frederic Ruget, Dec 11 2022

Status

approved