

A360745


a(n) is the maximum number of locations 1..n1 which can be reached starting from a(1)=1, where jumps from location i to i + a(i) are permitted (within 1..n1). See example.


9



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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).


LINKS



EXAMPLE

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


PROG

(Python)
def A(lastn, mode=0):
a, n, t=[1], 0, 1
while n<lastn:
d, g, r, rr=[[0]], 0, 0, [0]
while len(d)>0:
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]])<t:g=1
if d[1][1]+a[d[1][1]]<=n:
if d[1].count(d[1][1]+a[d[1][1]])<t:
if g>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)
(PARI) See links.


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



