login
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.
10

%I #58 May 26 2023 11:30:27

%S 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,

%T 21,22,22,22,23,23,23,23,24,24,26,27,28,29,29,29,29,29,29,29,29,29,32,

%U 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

%N 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.

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

%H Neal Gersh Tolunsky, <a href="/A360744/b360744.txt">Table of n, a(n) for n = 1..5000</a>

%e 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):

%e 1, 1, 2, 3, 4, 5, 5, 6

%e 1<-------3------->5

%e 1, 1, 2, 3, 4, 5, 5, 6

%e 1->1<-------------5

%e 1, 1, 2, 3, 4, 5, 5, 6

%e 1->2

%e 1, 1, 2, 3, 4, 5, 5, 6

%e 2---->4

%e From the last iteration we can visit no new terms. We reached 6 terms, so a(9)=6:

%e 1, 1, 2, 3, 4, 5, 5, 6

%e 1 1 2 3 4 5

%o (Python)

%o def A(lastn,mode=0):

%o a,n,t=[1],0,1

%o while n<lastn:

%o p,v=0,1

%o while p<=n:

%o d,g,r,rr=[[p]],0,0,[p]

%o while len(d)>0:

%o if not d[-1][-1] in rr:rr.append(d[-1][-1])

%o if d[-1][-1]-a[d[-1][-1]]>=0:

%o if d[-1].count(d[-1][-1]-a[d[-1][-1]])<t:g=1

%o if d[-1][-1]+a[d[-1][-1]]<=n:

%o if d[-1].count(d[-1][-1]+a[d[-1][-1]])<t:

%o if g>0: d.append(d[-1][:])

%o d[-1].append(d[-1][-1]+a[d[-1][-1]])

%o r=1

%o if g>0:

%o if r>0: d[-2].append(d[-2][-1]-a[d[-2][-1]])

%o else: d[-1].append(d[-1][-1]-a[d[-1][-1]])

%o r=1

%o if r==0:d.pop()

%o r,g=0,0

%o if v<len(rr):v=len(rr)

%o p+=1

%o a.append(v)

%o n+=1

%o print(n+1,a[n])

%o if mode>0: print(a)

%o return a ## _S. Brunner_, Feb 19 2023

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

%K nonn

%O 1,3

%A _Neal Gersh Tolunsky_, Feb 18 2023