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
Neal Gersh Tolunsky, Table of n, a(n) for n = 0..10000
Atlantis, Infinite sidewalk blog post.
Jane Street, Numberphile webpage.
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
KEYWORD
nonn
AUTHOR
Frederic Ruget, Dec 02 2022
STATUS
approved