login
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
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:
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.
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.
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.
Sequence in context: A246007 A256997 A335499 * A359008 A239970 A111202
KEYWORD
nonn
AUTHOR
Frederic Ruget, Dec 02 2022
STATUS
approved