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

A359005 Jane Street's infinite sidewalk's greedy walk.

Original entry on oeis.org

0, 1, 2, 4, 7, 3, 5, 8, 13, 6, 10, 16, 25, 12, 19, 9, 14, 22, 34, 52, 79, 39, 59, 29, 44, 21, 32, 15, 23, 11, 17, 26, 40, 61, 30, 46, 70, 106, 160, 241, 120, 181, 90, 136, 67, 33, 50, 24, 37, 18, 28, 43, 65, 98, 48, 73, 36, 55, 27, 41, 20, 31, 47, 71, 35, 53

Offset: 0

Frederic Ruget, Dec 10 2022

nonn

The Jane Street greedy walk is obtained by starting on slab 0 of Jane Street's infinite sidewalk (see A358838) and always jumping backwards preferably than forwards. Also, it is forbidden to visit a slab more than once.
The sequence is well defined. It demonstrably never ends and never repeats.
It is conjectured that the sequence actually visits all nonnegative integers. This is related to the conjecture that given any positive integer n, there exists a minimal Jane Street's path (i.e., with minimal number of jumps) going from slab 0 to slab n, and ending either in "forwards" or in "forwards-forwards-backwards". This would make the sequence a one-to-one mapping of the nonnegative numbers onto themselves. See also A359008.

			Let N denote the nonnegative integers.
Let forward and backward denote the forward-jumping and backward-jumping functions as defined in Jane Street's infinite sidewalk rules (see A358838):
  forward(n) = n + floor(n/2) + 1
  backward(n) = n - floor(n/2) - 1
Finally, let f denote the (demonstrably one-to-one) mapping of N x N to N:
  f(i, j) = forward^j(3*i)
The mapping f is illustrated by the following table, where the contents of each cell (i, j) is f(i, j):
.
   \j|
   i\|  0    1    2    3    4    5    6    7    8  ...
  ---+------------------------------------------------
   0 |  0    1    2    4    7   11   17   26   40  ...
   1 |  3    5    8   13   20   31   47   71  107  ...
   2 |  6   10   16   25   38   58   88  133  200  ...
   3 |  9   14   22   34   52   79  119  179  269  ...
   4 | 12   19   29   44   67  101  152  229  344  ...
   5 | 15   23   35   53   80  121  182  274  412  ...
   6 | 18   28   43   65   98  148  223  335  503  ...
   7 | 21   32   49   74  112  169  254  382  574  ...
   8 | 24   37   56   85  128  193  290  436  655  ...
   9 | 27   41   62   94  142  214  322  484  727  ...
  10 | 30   46   70  106  160  241  362  544  817  ...
  11 | 33   50   76  115  173  260  391  587  881  ...
  12 | 36   55   83  125  188  283  425  638  958  ...
  13 | 39   59   89  134  202  304  457  686 1030  ...
  ...| ...  ...  ... ...  ...  ...  ...  ...  ...  ...
(Note that the first row of the table corresponds to A006999.)
.
Equivalently, we can represent f(i, j) as a(n) for some n. This results in the following alternate illustrative table, where the contents of each cell (i, j) is still f(i, j), but represented as a(n):
.
 \j|
 i\| 0       1       2       3       4       5       6       7       8 ...
---+------------------------------------------------------------------------
 0 | a(0)    a(1)    a(2)    a(3)    a(4)    a(29)   a(30)   a(31)   a(32)
 1 | a(5)    a(6)    a(7)    a(8)    a(60)   a(61)   a(62)   a(63)   a(91)
 2 | a(9)    a(10)   a(11)   a(12)   a(75)   a(76)   a(77)   a(78)   a(412)
 3 | a(15)   a(16)   a(17)   a(18)   a(19)   a(20)   a(297)  a(298)  a(1109)
 4 | a(13)   a(14)   a(23)   a(24)   a(44)   a(99)   a(100)  a(258)  a(435)
 5 | a(27)   a(28)   a(64)   a(65)   a(66)   a(67)   a(206)  a(207)  a(208)
 6 | a(49)   a(50)   a(51)   a(52)   a(53)   a(284)  a(285)  a(286)  a(287)
 7 | a(25)   a(26)   a(81)   a(82)   a(83)   a(84)   a(418)  a(419)  a(420)
 8 | a(47)   a(48)   a(103)  a(104)  a(151)  a(152)  a(440)  a(441)  a(442)
 9 | a(58)   a(59)   a(244)  a(245)  a(246)  a(247)  a(248)  a(249)  a(250)
10 | a(34)   a(35)   a(36)   a(37)   a(38)   a(39)   a(958)  a(959)  a(960)
11 | a(45)   a(46)   a(212)  a(213)  a(520)  a(521)  a(522)  a(1455) a(1456)
12 | a(56)   a(57)   a(242)  a(243)  a(290)  a(291)  a(785)  a(786)  a(787)
13 | a(21)   a(22)   a(299)  a(300)  a(301)  a(302)  a(647)  a(648)  a(3437)
.. |
.
The later illustration helps visualize how {a(n)} works: going from a(n) to a(n+1) results in either
  - jumping forwards, thus moving one step to the right in the row of the table, or
  - jumping backwards, thus changing row.
This procedure (demonstrably) never creates a gap in the rows of the table.

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

A particular valid path on the Jane Street infinite sidewalk A358838.
Possibly the reverse mapping of sequence A359008.
Cf. A006999.

def a(n: int) -> int:
    if n < 0: raise Exception("n must be a nonnegative integer")
    if n == 0: return 0
    visited = {0}
    slab = 1
    for i in range(1, n):
        label = 1 + (slab >> 1)
        if not slab - label in visited:
            slab -= label  # moving backwards
        else:
            slab += label  # moving forwards
            if slab in visited: raise Exception(f"blocked at slab {slab}")
        visited.add(slab)
    return slab

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

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

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

A359005 Jane Street's infinite sidewalk's greedy walk.

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

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