\\ Kevin Ryde, July 2023
\\
\\ This is some PARI/GP code to find terms of A364392, which is
\\
\\     a(n) = number of locations in the shortest path
\\        starting from i=n-1, never re-visiting locations,
\\        step from i to i+a(i) or i-a(n) within 1..n-1
\\        and continuing until no step is possible.
\\
\\ The sequence ends up as some initial exceptions and then
\\ periodic, so that function A364392(n) is as easy as a
\\ table lookup.

default(strictargs,1);
default(recover,0);


\\-----------------------------------------------------------------------------
\\ Finding Paths

\\ A364392_next_and_earliest() takes vector "a" where a[1..n]
\\ is terms A364392(1..n).  Must have n>=1.
\\ "a" can be longer than n elements but only 1..n are used.
\\ The return value is a 2-element vector
\\     [ shortest, earliest ]
\\ where
\\     shortest = next term, A364392(n+1).
\\     earliest = smallest location number i which occurred
\\                while searching.
\\
A364392_next_and_earliest(a,n) =
{
  \\ elems[] is a vector of 2-element vectors [i, seen]
  \\ each representing a path:
  \\     i = end-most location number of the path
  \\     seen = Set() (sorted vector) of location numbers
  \\       already visited, not including i itself.
  \\
  \\ elems[] is all possible paths of length #seen + 1
  \\ (all the same length).  If any is a dead-end then
  \\ this length is the return value.  Otherwise all paths
  \\ step to next i +/- a(i) (in new_elems).

  my(elems=[ [n,[]] ],  \\ starting at i=n
     earliest=n);
  while(1,
        my(new_elems=List([]));
        for(j=1,#elems,
           my(i,seen); [i,seen]=elems[j];
           seen=setunion(seen,[i]);
           earliest = min(earliest, i);

           my(num_to=0);
           forstep(s=-1,1,2,
              my(to = i + s*a[i]);
              if(1 <= to && to <= n && !setsearch(seen,to),
                 listput(new_elems, [to,seen]);
                 num_to++));

           if(num_to==0,  \\ nowhere to go, found shortest
              return([#seen,earliest])));

        elems=new_elems);
}

\\ Return a vector of the first len many terms of A364392
\\ by explicitly finding paths.
A364392_vector_by_paths(len) =
{
  my(a=vector(len,i,1));
  for(n=2,len,
     a[n] = A364392_next_and_earliest(a,n-1)[1]);
  a;
}


\\-----------------------------------------------------------------------------
\\ Sequence Terms by Table Lookup
\\
\\ The result of the paths searching is 1244 initial terms
\\ followed by a block of 4925 terms which repeat.
\\ See "Check Periodic" below verifying this.
\\
\\ The terms are created by paths searching.  An actual
\\ program could have them as an explicit table (length 6169).


\\ table[] is fixed part and one copy of periodic part
my(table = A364392_vector_by_paths(1244 + 4925)); \
A364392(n) =
{
  if(n > #table, n = (n - 1245)%4925 + 1245);
  table[n];
}

{
  print1("A364392 = ");
  for(n=1,20, print1(A364392(n),","));
  print("...");
}


\\-----------------------------------------------------------------------------
\\ Check Periodic
\\
\\ To verify that the sequence is indeed periodic, it's enough
\\ to check that at some point new copies of the periodic part
\\ look back no further than preceding copies.
\\ 
\\ The following check is that the earliest examined is at
\\ most the period length 4925 back, and so within the
\\ preceding periodic block.  Actually much less is examined,
\\ but this suffices to show periodic.

{
  print("check periodic");
  my(a = vector(1244 + 3*4925, n, A364392(n)),
     max_preceding=0);

  \\ start of second copy of periodic, through to end of a[]
  for(n = 1244 + 4925 + 1, #a-1,
     my(term,earliest);
     [term,earliest] = A364392_next_and_earliest(a,n);
     term == a[n+1] || error();   \\ next term
     earliest > n - 4925 || error();
     max_preceding = max(max_preceding, n - earliest + 1));

  \\ When searching, at most final 98 terms were examined,
  max_preceding == 98  || error();

  \\ A364392_next_and_earliest() doesn't attempt to be
  \\ minimal about how far back its "earliest" goes.
  \\ The largest i which is a dead-end would be the minimum
  \\ but 98 is already well below what's needed.
}

{
  \\ n=1244 is not in the periodic part
  A364392(1244) != A364392(1244 + 4925)  || error();

  \\ n=1245 onwards is the periodic part
  for(n=1245,20000,
     A364392(n) == A364392(n + 4925)  || error());
}


\\-----------------------------------------------------------------------------
\\ Linear Recurrence

\\ The generating function for a periodic sequence is
\\ (terms)/(1-x^len) in the usual way, and initial
\\ exceptions at the start.

\\ t_RFRAC generating function
gA364392 = sum(n=1,1244, A364392(n)*x^n) \
  + sum(n=1245,1244+4925, A364392(n)*x^n) / (1-x^4925);

print("check gA364392");
gA364392 + O(x^20000) == \
Ser(vector(20000,n,n--; if(n==0,0, A364392(n))))  || error();

\\ Nothing cancels between the gf numerator terms and the
\\ denominator 1-x^len.
denominator(gA364392) == 1 - x^4925  || error();

\\ So the shortest linear recurrence is just a(n) = a(n-4925),
\\ and recurrence order 4925.
{
  for(n=1244+4925+1,20000,
     A364392(n) == A364392(n - 4925)  || error());
}


\\-----------------------------------------------------------------------------
print("end");