A358838 Minimum number of jumps needed to go from slab 0 to slab n in Jane Street's infinite sidewalk.

0, 1, 2, 5, 3, 6, 9, 4, 7, 10, 10, 5, 8, 8, 11, 11, 11, 6, 14, 9, 9, 12, 12, 12, 15, 12, 7, 18, 15, 10, 10, 10, 13, 13, 13, 13, 16, 16, 13, 16, 8, 19, 19, 16, 11, 11, 11, 11, 19, 14, 14, 14, 14, 14, 22, 17, 17, 17, 14, 17, 17, 9, 20, 20, 20, 17, 17, 12, 12, 12

Offset: 0

Author

Frederic Ruget, Dec 02 2022

Keywords

• nonn

Comments

Slabs on the sidewalk are numbered n = 0, 1, 2,... and each has a label L(n) = 1, 1, 2, 2, 3, 3,...

At a given slab, a jump can be taken forward or backward by L(n) places (but not back before slab 0).

.

For every n >= 0,

let L(n) = 1 + floor(n/2) -- the label on slab n,

let forward(n) = n + L(n) -- jumping forward,

if n > 0, let backward(n) = n - L(n) -- jumping backward,

let lambda(n) = floor((2/3)*n),

let mu(n) = 1 + 2*n,

let nu(n) = 2 + 2*n.

Observe that given n >= 0, there are exactly two ways of landing onto slab n with a direct jump backwards:

backward-jumping from mu(n) to n, and

backward-jumping from nu(n) to n.

If n is a multiple of 3, there is no other ways of jumping onto slab n. But if n is not a multiple of 3, there is one additional way:

forward-jumping from lambda(n) to n.

(Note that L is A008619, forward(n) == A006999(n+1), lambda is A004523, mu is A005408, nu is A299174.)

.

Every slab n > 0 is reachable from slab 0, since there always exists some slab s < n which reaches n by one or more jumps:

if n != 0 (mod 3), then s = lambda(n) = floor((2/3)*n) takes one forward jump to n,

if n == 0 (mod 3) but n != 0 (mod 9), then s = lambda o lambda o mu(n) = floor((8/9)*n) takes two forward jumps and one backward jump to n,

if n == 0 (mod 9), then s = lambda o lambda o nu(n) = floor((8/9)*n + 6/9) takes two forward jumps and one backward jump to n.

This demonstrates that the sequence never stops.

This also gives the following bounds:

a(n) <= 1 + (4/3)*n,

a(n) <= 6*log(n)/log(9/8).

.

The sequence is a surjective mapping N -> N, since given any n >= 0:

a(forward^n(0)) == n.

Examples

			For n=0, a(0) = 0 since it takes zero jump to go from slab 0 to slab 0.
For n=3, a(3) = 5 jumps is the minimum needed to go from slab 0 to slab 3:
.
        1st   2nd      3rd           4th
        jump  jump     jump          jump
        ->-   ->-   ---->----   ------->-------
       /   \ /   \ /         \ /               \
n     0     1     2     3     4     5     6     7     8  ...
L(n)  1     1     2     2     3     3     4     4     5  ...
                         \                     /
                          ----------<----------
                                 5th jump (backwards)
		

Links

• Neal Gersh Tolunsky, Table of n, a(n) for n = 0..10000
• Atlantis, Infinite sidewalk blog post.
• Jane Street, Numberphile webpage.

Crossrefs

Cf. A359005, A359008.

Always jumping forwards yields A006999.

In the COMMENTS section, L is A008619, forward(n) == A006999(n+1), lambda is A004523, mu is A005408, nu is A299174.

For related sequences, see A360744-A360746 and A360593-A360595.

Programs

Python

def a(n: int) -> int:
    import itertools
    if n < 0: raise Exception("n must be a nonnegative integer")
    if n == 0: return 0
    if n == 1: return 1
    visited = {0, 1}  # the slabs we have visited so far
    rings = [{0}, {1}]  # the slabs ordered by depth (min length of path from 0)
    for depth in itertools.count(2):
        new_ring = set()
        for slab in rings[depth - 1]:
            label = (slab >> 1) + 1
            for next_slab in {slab - label, slab + label}:
                if not next_slab in visited:
                    if next_slab == n: return depth
                    visited.add(next_slab)
                    new_ring.add(next_slab)
        rings.append(new_ring)