A359005 -id:A359005 - cp's OEIS frontend

A360746 a(n) is the maximum number of locations 1..n-1 which can be reached starting from a(n-1), where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

1, 1, 2, 3, 4, 4, 5, 5, 5, 7, 8, 8, 8, 9, 9, 12, 10, 10, 12, 10, 12, 13, 13, 13, 16, 14, 14, 16, 17, 17, 17, 18, 18, 24, 25, 25, 25, 26, 27, 27, 27, 27, 28, 28, 30, 28, 33, 28, 29, 30, 30, 30, 33, 31, 31, 31, 32, 32, 33, 33, 31, 31, 32, 33, 33, 35, 33, 37

Offset: 1

Neal Gersh Tolunsky, Feb 18 2023

nonn

			a(7)=5 because we reach 5 terms starting from the most recent term a(6) (each line shows the next unvisited term(s) we can reach from the term(s) in the previous iteration):
1, 1, 2, 3, 4, 4
   1<----------4
1, 1, 2, 3, 4, 4
1<-1->2
1, 1, 2, 3, 4, 4
      2---->4
From the last iteration we can visit no new terms. We reached 5 terms, so a(7)=5:
1, 1, 2, 3, 4, 4
1  1  2     4  4

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program

Cf. A360744, A360745, A360593, A360594, A360595, A359005, A358838, A359008.

PARI
```
See Links section.
```

def A(lastn,mode=0):
  a,n,t=[1],0,1
  while n0:
      if not d[-1][-1] in rr:rr.append(d[-1][-1])
      if d[-1][-1]-a[d[-1][-1]]>=0:
        if d[-1].count(d[-1][-1]-a[d[-1][-1]])0: d.append(d[-1][:])
          d[-1].append(d[-1][-1]+a[d[-1][-1]])
          r=1
      if g>0:
        if r>0: d[-2].append(d[-2][-1]-a[d[-2][-1]])
        else: d[-1].append(d[-1][-1]-a[d[-1][-1]])
        r=1
      if r==0:d.pop()
      r,g=0,0
    a.append(len(rr))
    n+=1
    print(n+1,a[n])
    if mode>0: print(a)
  return a  # S. Brunner, Feb 26 2023

A360744 a(n) is the maximum number of locations 1..n-1 which can be reached starting from some location s, where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 9, 10, 10, 10, 11, 11, 13, 14, 14, 14, 15, 15, 15, 15, 21, 21, 21, 22, 22, 22, 23, 23, 23, 23, 24, 24, 26, 27, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 32, 32, 32, 32, 33, 33, 35, 35, 41, 42, 42, 42, 43, 43, 43, 44, 44, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 49, 49, 51, 51, 51

Offset: 1

Neal Gersh Tolunsky, Feb 18 2023

nonn

a(10)=7 is the earliest term whose solution cannot be represented by a single path in which each index is visited once.

			For a(9), we reach the greatest number of terms by starting at location s=4, which is a(4)=3. We visit 6 terms as follows (each line shows the next unvisited term(s) we can reach from the term(s) last visited):
1, 1, 2, 3, 4, 5, 5, 6
1<-------3------->5
1, 1, 2, 3, 4, 5, 5, 6
1->1<-------------5
1, 1, 2, 3, 4, 5, 5, 6
   1->2
1, 1, 2, 3, 4, 5, 5, 6
      2---->4
From the last iteration we can visit no new terms. We reached 6 terms, so a(9)=6:
1, 1, 2, 3, 4, 5, 5, 6
1  1  2  3  4     5

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..5000

Cf. A360745, A360746, A360593, A361383, A359005, A358838, A359008, A362248.

def A(lastn,mode=0):
  a,n,t=[1],0,1
  while n0:
        if not d[-1][-1] in rr:rr.append(d[-1][-1])
        if d[-1][-1]-a[d[-1][-1]]>=0:
          if d[-1].count(d[-1][-1]-a[d[-1][-1]])0: d.append(d[-1][:])
            d[-1].append(d[-1][-1]+a[d[-1][-1]])
            r=1
        if g>0:
          if r>0: d[-2].append(d[-2][-1]-a[d[-2][-1]])
          else: d[-1].append(d[-1][-1]-a[d[-1][-1]])
          r=1
        if r==0:d.pop()
        r,g=0,0
      if v0: print(a)
  return a ## S. Brunner, Feb 19 2023

A360745 a(n) is the maximum number of locations 1..n-1 which can be reached starting from a(1)=1, where jumps from location i to i +- a(i) are permitted (within 1..n-1). See example.

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 4, 4, 7, 7, 7, 8, 9, 9, 9, 9, 9, 9, 12, 12, 13, 13, 13, 13, 13, 14, 14, 17, 17, 17, 17, 17, 24, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 33, 33, 33, 34, 34, 37, 37, 37, 38, 38, 48, 48, 48, 48, 48, 49, 50, 51, 52, 53, 53, 53

Offset: 1

Neal Gersh Tolunsky, Feb 18 2023

nonn

a(n) is also the smallest number of terms you can reach from any starting term in the sequence so far. This is true because every term leads back to a(1)=1.
Note that each location can visit up to two terms (doesn't have to be a path), although in this case the example sections shows a path.
a(21)=13 is the earliest term whose solution cannot be represented by a single path in which each index is visited once (found by Kevin Ryde).

			a(13)=9 because we can reach 9 terms starting from a(1) as follows:
1, 1, 2, 3, 3, 4, 4, 4, 7, 7, 7, 8
1->1->2---->3------->4---------->8
1, 1, 2, 3, 3, 4, 4, 4, 7, 7, 7, 8
         3<----------------------8
1, 1, 2, 3, 3, 4, 4, 4, 7, 7, 7, 8
         3------->4---------->7
This is a total of 9 terms:
1, 1, 2, 3, 3, 4, 4, 4, 7, 7, 7, 8
1  1  2  3  3     4  4        7  8

Kevin Ryde, Table of n, a(n) for n = 1..10000
Kevin Ryde, PARI/GP Code
Neal Gersh Tolunsky, Graph of run lengths of a(n) for n = 1..50004

Cf. A360744, A360746, A361383, A360593, A359005, A358838, A359008.

PARI
```
\\ See links.
```

def A(lastn,mode=0):
  a,n,t=[1],0,1
  while n0:
      if not d[-1][-1] in rr:rr.append(d[-1][-1])
      if d[-1][-1]-a[d[-1][-1]]>=0:
        if d[-1].count(d[-1][-1]-a[d[-1][-1]])0: d.append(d[-1][:])
          d[-1].append(d[-1][-1]+a[d[-1][-1]])
          r=1
      if g>0:
        if r>0: d[-2].append(d[-2][-1]-a[d[-2][-1]])
        else: d[-1].append(d[-1][-1]-a[d[-1][-1]])
        r=1
      if r==0:d.pop()
      r,g=0,0
    a.append(len(rr))
    n+=1
    print(n+1,a[n])
    if mode>0: print(a)
  return a  # S. Brunner, Feb 19 2023

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

Original entry on oeis.org

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

Frederic Ruget, Dec 02 2022

nonn

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.

			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)

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

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.

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)

A359008 Jane Street's infinite sidewalk's greedy walk inverse mapping.

Original entry on oeis.org

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

Frederic Ruget, Dec 11 2022

nonn

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.

Inverse mapping of A359005.

Neal Gersh Tolunsky, Table of n, a(n) for n = 0..10000

Cf. A358838, A359005.

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

cp's OEIS Frontend

A360746 a(n) is the maximum number of locations 1..n-1 which can be reached starting from a(n-1), where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

A360744 a(n) is the maximum number of locations 1..n-1 which can be reached starting from some location s, where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A360745 a(n) is the maximum number of locations 1..n-1 which can be reached starting from a(1)=1, where jumps from location i to i +- a(i) are permitted (within 1..n-1). See example.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A359008 Jane Street's infinite sidewalk's greedy walk inverse mapping.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Python