cp's OEIS Frontend

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.

%I A360744 #58 May 26 2023 11:30:27
%S A360744 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 A360744 21,22,22,22,23,23,23,23,24,24,26,27,28,29,29,29,29,29,29,29,29,29,32,
%U A360744 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 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.
%C A360744 a(10)=7 is the earliest term whose solution cannot be represented by a single path in which each index is visited once.
%H A360744 Neal Gersh Tolunsky, <a href="/A360744/b360744.txt">Table of n, a(n) for n = 1..5000</a>
%e A360744 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 A360744 1, 1, 2, 3, 4, 5, 5, 6
%e A360744 1<-------3------->5
%e A360744 1, 1, 2, 3, 4, 5, 5, 6
%e A360744 1->1<-------------5
%e A360744 1, 1, 2, 3, 4, 5, 5, 6
%e A360744    1->2
%e A360744 1, 1, 2, 3, 4, 5, 5, 6
%e A360744       2---->4
%e A360744 From the last iteration we can visit no new terms. We reached 6 terms, so a(9)=6:
%e A360744 1, 1, 2, 3, 4, 5, 5, 6
%e A360744 1  1  2  3  4     5
%o A360744 (Python)
%o A360744 def A(lastn,mode=0):
%o A360744   a,n,t=[1],0,1
%o A360744   while n<lastn:
%o A360744     p,v=0,1
%o A360744     while p<=n:
%o A360744       d,g,r,rr=[[p]],0,0,[p]
%o A360744       while len(d)>0:
%o A360744         if not d[-1][-1] in rr:rr.append(d[-1][-1])
%o A360744         if d[-1][-1]-a[d[-1][-1]]>=0:
%o A360744           if d[-1].count(d[-1][-1]-a[d[-1][-1]])<t:g=1
%o A360744         if d[-1][-1]+a[d[-1][-1]]<=n:
%o A360744           if d[-1].count(d[-1][-1]+a[d[-1][-1]])<t:
%o A360744             if g>0: d.append(d[-1][:])
%o A360744             d[-1].append(d[-1][-1]+a[d[-1][-1]])
%o A360744             r=1
%o A360744         if g>0:
%o A360744           if r>0: d[-2].append(d[-2][-1]-a[d[-2][-1]])
%o A360744           else: d[-1].append(d[-1][-1]-a[d[-1][-1]])
%o A360744           r=1
%o A360744         if r==0:d.pop()
%o A360744         r,g=0,0
%o A360744       if v<len(rr):v=len(rr)
%o A360744       p+=1
%o A360744     a.append(v)
%o A360744     n+=1
%o A360744     print(n+1,a[n])
%o A360744     if mode>0: print(a)
%o A360744   return a ## _S. Brunner_, Feb 19 2023
%Y A360744 Cf. A360745, A360746, A360593, A361383, A359005, A358838, A359008, A362248.
%K A360744 nonn
%O A360744 1,3
%A A360744 _Neal Gersh Tolunsky_, Feb 18 2023