/* A340389.gp - (c) July 2021 by M. F. Hasler
   Please see https://oeis.org/wiki/User:M._F._Hasler/A340389 for the latest version,
   this static file will certainly become obsolete, sooner or later.

Triangles of size n > 1 are constructed by combining "compatible" (*) triangles of size n-1
and stored in the list M340389[n] (*), except for n = 1 where the triangles are exactly the elements of A089237.
(* : see below for details)

=== PARI/GP ===
Here is a first, quite naïve and not very efficient implementation of the above idea to compute the sequence, 
by constructing the list of all triangles of size ''n'' in order of increasing value of the apex. 
It uses the functions A089237 and is_A089237, to be implemented sufficiently efficiently. (See end of file.)
 */

 M340389=[List()|i<-[1..9]]; /* The n-th element of this vector is a list of triangles of size n,
                                complete up to a given size of the apex.
                                However, for n = 1 we use A089237 instead of this list, so M340389[1] will remain empty. */
 /* Triangles are coded/stored as vectors T = [size, apex, left, right, members],
    where:
       size = n = the number of rows/columns of the triangle,
       apex = T[1,1] = the largest element of the triangle,
       left, right = indices of the left & right sub-triangle in the list of triangles of size n-1, 
                     with a minus sign when the respective triangle is flipped / reversed.
       members = the set of all elements of the triangle.
     We define four member functions for this structure: ( you may add: T.apex=T[2], T.size=T[1] ) */
 {[ T.flip=[T[3], T[4]]=[-T[4], -T[3]]; T, /* returns the reversed triangle: same apex, but left & right exchanged & flipped */
    T.left=if( T[3]>0, A340389(T[1]-1, T[3]), T[3]<0, A340389(T[1]-1, -T[3]).flip),  /* return the left sub-triangle */
    T.right=if(T[4]>0, A340389(T[1]-1, T[4]), T[4]<0, A340389(T[1]-1, -T[4]).flip),
    /* "Expand" a triangle to the full, explicit list (vector) of its rows:
        For "interactive" use; not required in the main program. */
    T.expand= if(T[1]>1,  my(L=T.left.expand                /* Recursively expand the left and right sub-triangle; */
                           , R=[r[#r]|r<-T.right.expand]);  /* keep only the last element of each row of the latter. */ 
                 [if(r>1, concat(L[r-1], R[r-1])   /* For rows 2..n, append that (rightmost) element to the "left side row". */
                        , [T[2]])                  /* while row 1 is made of only the apex */
                 | r<-[1..T[1]]]
              , [[T[2]]] /* For size n = 1, return a vector containing just one row which has the apex as only element. */
              )
 ]};
 A340389(n, r=0/*by default, return a(n) = apex of the first triangle of size n; for r>0 return the r-th triangle of size n*/)=
 {if(n>1, while( #M340389[n] < r+!r,
   /*populate list for size n*/ my(L=0/*limit*/, m=#M340389[n] /*minimum*/);
   m && m=M340389[n][m][2];
   for(b=2+(n<3), oo, my(T=A340389(n-1, b)); m && T[2]*2 <= m  && next;
    for(a=1+(n<3), b-1, my(S=A340389(n-1, a), A=S[2]+T[2], c); m && A <= m && next; 
      L && A>L && break(1+(a==1+(n<3)));
      /*S & T compatible?*/
      is_A089237(T[2]+S[2]) && #setintersect(T[5], S[5])==T[1]*(T[1]-1)/2
       && (c=if(S.right==T.left, [1, 1],
                S.right==T.right.flip, [1, -1],
                S.left==T.right, [-1, -1], 
                S.left.flip==T.left, [-1, 1]))
       && (L || L=A)
       && listput(M340389[n], [n, A, a*c[1], b*c[2], concat(setunion(T[5], S[5]), A)])
    ) /*for a*/
   )/*for b*/;
   listsort(~M340389[n]) /* end populate */ ) /* end while */;
   if(r, M340389[n][r], M340389[n][1][2])
  , /*now n=1*/
    r, [1, r=A089237(r), 0, 0, [r]]
  , 0 /*=a(1)*/ 
  ) /*end if n>1*/
 }
 /*  Uses functions A089237 and is_A089237. We suggest to fetch their latest version from OEIS,
  *  for convenience we provide here a copy of their current version: */
  A89237=List([0..5]); A089237(n)={while(#A89237<n, my(t=A89237[#A89237]);
                                                    until( isprime(t++)||issquare(t), ); listput(A89237, t)); A89237[n]}
  is_A089237(n)=isprime(n)||issquare(n)

/*** end of file ***/