A360595 -id:A360595 - 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

A360593 Each term a(i) can reach a(i+a(i)) and a(i-a(i)) if these terms exist. a(n) is the greatest number of terms among a(1..n-1) that can be reached by starting at a(n-1) and visiting no term more than once; a(0)=0. See example.

Original entry on oeis.org

0, 1, 2, 2, 4, 2, 6, 2, 7, 5, 6, 6, 9, 10, 10, 6, 8, 7, 9, 8, 11, 8, 12, 14, 12, 14, 19, 16, 19, 14, 14, 16, 14, 21, 14, 16, 21, 14, 14, 16, 14, 18, 14, 16, 21, 21, 19, 21, 22, 22, 21, 23, 24, 24, 29, 29, 22, 26, 24, 28, 24, 26, 31, 24, 31, 34, 24, 30, 34, 29, 39

Offset: 0

S. Brunner, Feb 13 2023

nonn

For clarification:
The terms of the sequence so far are written as a one-dimensional grid, and from every term a(i) you can jump back or forth a(i) terms, without i getting < 0 or > n, as these terms don't exist. Then search for the longest possible chain of jumps you can do starting at a(n) and visiting no term more than once. The number of targets visited by this chain is the next term of the sequence.
A chain of jumps C always starts at n, with C1 = a(n-1). Then the first jump always has to go back C1 terms, so C2 = a(n-1-C1) = a(n-1-a(n-1)), and then it continues with jumping back or forth C2 terms, whichever produces the longest chain of jumps:
C3 = a(n-1-C1-C2) or a(n-1-C1+C2),
C4 = a(n-1-C1{-/+}C2{-/+}C3), etc.
The first numbers which appear to be missing from this sequence are:
3, 13, 15, 17, 20, 25, 27,  32,  33, 36, 43, 44, 48,  50, 51,  62, 63,  69, 70, 71, 75, 77, 78, 80, etc.

			This example shows the longest chain of jumps starting with a(7)=2:
0, 1, 2, 2, 4, 2, 6, 2
   1<----2<----2<----2
    ->2---->4
0<----------
It visited the 7 terms 2,2,2,1,2,4,0. So a(8)=7.

S. Brunner, Table of n, a(n) for n = 0..217

Cf. A360594, A360595, A360744, A360745, A360746.

def A(lastn,times=1,mode=0):
  a,n=[0],0
  while n0:
      if len(d[-1])>v: v,o=len(d[-1]),d[-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(v)
    n+=1
    if mode==0: print(n,a[n])
    if mode>0:
      u,q=0,[]
      while u

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)

A360594 a(n) is the maximum number of locations 0..n-1 which can be visited in a single path starting from i=n-1, where jumps from location i to i +- a(i) are permitted (within 0..n-1) and each location can be visited up to 2 times.

Original entry on oeis.org

0, 2, 1, 2, 4, 3, 8, 1, 2, 2, 4, 2, 8, 5, 4, 6, 13, 14, 14, 13, 13, 16, 22, 3, 17, 16, 20, 13, 13, 24, 22, 15, 24, 15, 14, 17, 14, 4, 15, 18, 23, 26, 28, 13, 16, 30, 28, 14, 15, 17, 16, 19, 16, 33, 18, 33, 32, 35, 39, 38, 40, 38, 39, 39, 36, 39, 38, 39, 41, 52

Offset: 0

S. Brunner, Feb 13 2023

nonn

When a location is visited more than once, each such visit counts in a(n).

			For n=0 there are no locations 0..n-1, so the sole possible path is empty which is a(0) = 0 locations.
For n=1, the sole possible path is location 0 twice, 0 -> 0, which is 2 locations a(1) = 2.
For n=12, a path of a(12) = 8 locations visited starting from n-1 = 11 is:
  11 -> 9 -> 11 -> 9 -> 7 -> 8 -> 10 -> 6
Locations 11 and 9 are visited twice each and the others once.
  i    = 0  1  2  3  4  5  6  7  8  9 10 11
  a(i) = 0, 2, 1, 2, 4, 3, 8, 1, 2, 2, 4, 2
                                    2<----2
                                     ---->2
                              1<----2<----
                               ->2---->4
                           8<----------

Cf. A360593, A360595.

def A(lastn,times=2,mode=0):
  a,n=[0],0
  while n0:
      if len(d[-1])>v: v,o=len(d[-1]),d[-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(v)
    n+=1
    if mode==0: print(n,a[n])
    if mode>0:
      u,q=0,[]
      while u

A361383 a(n) is the number of locations 1..n-1 which can be reached starting from location i=a(n-1), 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, 3, 4, 5, 4, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 15, 16, 15, 16, 15, 18, 17, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 22, 24, 22, 24, 23, 24, 26, 26, 26, 26, 26, 26, 26, 26, 26, 29, 32, 33, 35, 32, 35, 32, 35, 32, 35, 32, 35, 32, 36, 35, 37

Offset: 1

Neal Gersh Tolunsky, Mar 09 2023

nonn

For clarification: We start at the term with index a(n-1). From each term at index i, we can jump to up to two locations, which are a(i) terms away in either direction. We continue this process from the terms we have reached until we have visited all possible terms.

			We find a(8)=4 by first looking at the previous term in the sequence so far (1,1,2,3,3,4,5), which is a(7)=5. This tells us to start at location i=5. Permitted steps can reach 4 locations as follows:
  1, 1, 2, 3, 3, 4, 5
     1<-------3
  1, 1, 2, 3, 3, 4, 5
  1<-1->2
Steps from each of these locations cannot reach anything new, so a(8)=4. The reachable terms are:
  1, 1, 2, 3, 3, 4, 5
  1  1  2     3

Samuel Harkness, Table of n, a(n) for n = 1..10000

Cf. A360744, A360745, A360746, A360593, A360594, A360595, A358838.

More terms from Samuel Harkness, Mar 10 2023

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

A360593 Each term a(i) can reach a(i+a(i)) and a(i-a(i)) if these terms exist. a(n) is the greatest number of terms among a(1..n-1) that can be reached by starting at a(n-1) and visiting no term more than once; a(0)=0. See example.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

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

A360594 a(n) is the maximum number of locations 0..n-1 which can be visited in a single path starting from i=n-1, where jumps from location i to i +- a(i) are permitted (within 0..n-1) and each location can be visited up to 2 times.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A361383 a(n) is the number of locations 1..n-1 which can be reached starting from location i=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

Comments

Examples

Links

Crossrefs

Extensions