4 Gigabytes of RAM are not enough!

[R J Cano <0xcc00ffffeeee@gmail.com>]

  Greetings,

  This time featuring a problem that seems to be a RAM-memory's pacman
monster...

  Briefly: If you are looking for arbitrary symmetric/antisymmetric
patterns inside the first N!-1 terms of oeis.org A217626, ...for N>6
the problem becomes (yet inclusive if having a very simple and
efficient script!) intractable due there is no enough RAM to complete
the corresponding report...

 Attached to this mail comes a PARI/GP script which can be used to
appreciate that issue.

The usage is simple, load it and set:

p=vecDiff(A217626_vec_1(7));

then run the following search&report:

q=Patterns(p,1,5,1);

Which tells Patterns( ) to search for any pattern of size 5, and
exclusively (e=1) size 5,

For example the pattern [1,9,2,9,1] or the first 3!-1 terms of A217626
should be present (7-3+1)! = 120 times; However: The execution crashes
before allowing us to verify that!!, giving up due lacking of stack.

Cheers,

Remy

P.S.: Of course, this is not the fault of PARI/GP at all!, ... I only
wish to call the attention of someone else with access to more
powerful computing resources than me in the hope he/she/they be able
of resuming the streak of discoveries on those sequences (A215940,
A217626, and its higher differences).

/* (PARI-GP) R. J. Cano, Apr 19 2017 */

A215940_vec_1(n,{B=10})={my(u=n!-1); my(x=numtoperm(n, 0), y, z=vector(u),i:small);i=0;for(j=0, u, y=numtoperm(n, j)-x; z[i++]=fromdigits(vector(#x-1, k, vecsum(y[1..k])), B)); z}
A217626_vec_1(n,{B=10})={my(u=n!-1); my(x=numtoperm(n, 0), y, z=vector(u),i:small);i=0;for(j=1, u, y=numtoperm(n, j)-x; z[i++]=fromdigits(vector(#x-1, k, vecsum(y[1..k])), B); x+=y); z}

\\ kth differences of a vector iff it has enough elements (at least k+1);
vecDiff(v,{k=1})={
  if((1+k<=#v)&&#v,
    if(!k,
      return(v)
    );
    if(1==k,
      return(vector(#v-1,j,v[j+1]-v[j]))
    );
    my( f=(-1)^(k%2) );
    my( w=f*vector(#v-k,j,sum(i=0,k,((-1)^(i%2))*binomial(k,i)*v[j+i])) );
    if(type(v)==type(w),
      w
    ,
      w~
    )
  ,
    []
  )
}

\\ A215940_vec_0(n,{B=10})=APLPsignature_vec(n,B,0);
\\ A217626_vec_0(n,{B=10})=APLPsignature_vec(n,B,1);
\\ "APLP" is the acronym für "(A)rithmetic (P)rogression (L)exicographical (P)ermutations signature";; "tilauksen" is the Finnish für "order" like in "second order ODE".

isSubseq(b,a)={if(#b<=#a,my(t:small,L:list);t=0;L=List();while(#b-1+t++<=#a,if(a[t..t+#b-1]==b,listput(L,t)));return(L),return([]))}

palindrome(n,{B=10},{e=0})={e=!!e;my(v=digits(n,B),t=(-1)^e);my(w=vector(2*(#v+e)-#v%2));for(j=1,#v,w[j]=v[j];w[1+#w-j]=t*v[j]);fromdigits(w,B)}
antipalindrome(n,{B=10})=palindrome(n,B,1);

Symmetry(s0,{r=0},{leastSize=1},{e=0},{xX=0})={
  if(s0==[],return(1));
  if(leastSize-1<#s0,
  if(!r, 
    my(c:small, t=(-1)^( (!vecsum(s0)) %2) );
    c=0;
    while(c++<=#s0\2,
      if(s0[c]!=t*s0[1+#s0-c],return(0))
    );
    return(t)
  ,
    my(a:list,w:small,t:small,q:small);
    a=List();    
    w=leastSize-1;
    while(w++<=#s0,
      t=0;
      while(#s0>=w-1+t++,
        q=Symmetry(s0[t..(t+w-1)],0,leastSize,0,0);
        if(q&&(!e||(e&&(w==leastSize))),listput(a,[q,w,t]);if(e&&xX,return(Vec(a))));
                                                           \\ # By expecting an empty result,
      )                                                    \\ # finishes as soon as a counter-example 
    );                                                     \\ # is found.
    /* * / return(Vec(a)) / * */
    /* */ return(a) /* */
  )
  ,
    return(0);  
  )
  
}

\\ Patterns() is a convenient and useful modification applied to Symmetry.

Patterns(s0,{r=0},{leastSize=2},{e=0},{xX=0})={if(leastSize-1<#s0,if(!r,my(t=(-1)^((!vecsum(s0))%2),lambda,c:small,lookup:small);lambda=[];c=0;while(c++<=#s0\2,if(s0[c]!=t*s0[1+#s0-c],return(0)));return(t),my(a:list,w:small,t:small,q:small);a=List();w=leastSize-1;while(w++<=#s0,t=0;while(#s0>=w-1+t++,lambda=s0[t..(t+w-1)];q=Patterns(lambda,0,leastSize,0,0);if(q&&(!e||(e&&(w==leastSize))),lookup=-1;for(k=1,#a,if(a[k][1]==lambda,lookup+=k+1;break));if(lookup==-1,listput(a,[lambda,List(t)]),listput(a[lookup][2],t));if(e&&xX,return(Vec(a))));));/* * /return(Vec(a))/ * *//* */return(a)/* */ ),return(0);)}

/*EOF*/