A360594 - OEIS

%I #32 Jan 12 2024 10:05:39

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

%T 13,24,22,15,24,15,14,17,14,4,15,18,23,26,28,13,16,30,28,14,15,17,16,

%U 19,16,33,18,33,32,35,39,38,40,38,39,39,36,39,38,39,41,52

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

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

%e For n=0 there are no locations 0..n-1, so the sole possible path is empty which is a(0) = 0 locations.

%e For n=1, the sole possible path is location 0 twice, 0 -> 0, which is 2 locations a(1) = 2.

%e For n=12, a path of a(12) = 8 locations visited starting from n-1 = 11 is:

%e   11 -> 9 -> 11 -> 9 -> 7 -> 8 -> 10 -> 6

%e Locations 11 and 9 are visited twice each and the others once.

%e   i    = 0  1  2  3  4  5  6  7  8  9 10 11

%e   a(i) = 0, 2, 1, 2, 4, 3, 8, 1, 2, 2, 4, 2

%e                                     2<----2

%e                                      ---->2

%e                               1<----2<----

%e                                ->2---->4

%e                            8<----------

%o (Python)

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

%o   a,n=[0],0

%o   while n<lastn:

%o     d,i,v,o,g,r=[[n]],0,1,[],0,0

%o     while len(d)>0:

%o       if len(d[-1])>v: v,o=len(d[-1]),d[-1][:]

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

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

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

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

%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     a.append(v)

%o     n+=1

%o     if mode==0: print(n,a[n])

%o     if mode>0:

%o       u,q=0,[]

%o       while u<len(o):

%o         q.append(a[o[u]])

%o         u+=1

%o       print(n,a[n],q,o)

%o   return a

%Y Cf. A360593, A360595.

%K nonn

%O 0,2

%A _S. Brunner_, Feb 13 2023