

A358838


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


7



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


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:
backwardjumping from mu(n) to n, and
backwardjumping 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:
forwardjumping from lambda(n) to n.
.
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.


LINKS



EXAMPLE

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)


PROG

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


CROSSREFS

Always jumping forwards yields A006999.


KEYWORD

nonn


AUTHOR



STATUS

approved



