R J Cano on Fri, 21 Apr 2017 00:12:20 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: 4 Gigabytes of RAM are not enough!


Hi all!,

Here is a significant change that could be helpful anyway in the case of
A217626 and the (1 year ago, plus a new/recently) proposed conjectures.

Link:

https://oeis.org/w/images/9/97/RJCano_A217626_and_Patterns_Detection_gp.txt

Whit possible future updates, although anyway an snapshot of its current state
comes attached to this email.

Cheers,

Remy

2017-04-19 22:38 GMT-04:00, R J Cano <0xcc00ffffeeee@gmail.com>:
> Hi Bill!,
>
> Merci,
>
> about malining lists. Sure, no problem.
>
> Cheers,
>
> Remy
>
> 2017-04-19 14:13 GMT-05:00, Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr>:
>> On Wed, Apr 19, 2017 at 05:01:28AM -0400, R J Cano wrote:
>>>   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.
>>
>> The problem is that the output of Patterns is too large to fit
>> in the memory, this is not a problem with the algorithm:
>>
>> ? p=vecDiff(A217626_vec_1(6));
>> ? q=Patterns(p,1,5,1);
>> ? sizebyte(q)
>> %15 = 1998476512
>>
>> so q is almost 2GB. You need to find a more compact representation for
>> the output of Patterns if you want to go farther
>>
>> Cheers,
>> Bill.
>>
>> PS: please avoid crossposting between pari-dev and pari-users, a lot of
>> people are subscribed to both lists and so receive it twice.
>>
>
\\ (PARI/GP) By: R. J. Cano, on April 20th 2017;

/* GP vectors ("t_vec"'s) will be our representation for finite integer subsets (Our battle-horses!);
   for simplicity their transposes ("t_cols") are excluded from considerations. */

Symmetry(s0)={
  my(c:small, t=(-1)^!vecsum(s0));
  c=0;
  while(c++<=#s0\2,
    if(s0[c]!=t*s0[1+#s0-c],return(0))
  );
  return(t)
}

firstDiffs(w)=vector(-1+#w,k,w[k+1]-w[k]);

DetectIsBinA(B,A,{S=0},{useList=0})={
  /* Note: By returning -1 we mean error, either something was not yet implemented or invalid input operands A, a/o B were used. */
  if((type(A)!=type([]))||(type(B)!=type([])),return(-1));
  if(A==B,return(if(useList,List(1),B!=[]))); /* Due the subtlety of the empty sets: Are they in themselves? */
  my(widthB:small,widthA:small,distro:list);
  widthB=#B;
  widthA=#A;
  if(widthB>widthA,return(if(useList,List(),0)));
  /* */ S=Symmetry(B); /* */
  /* * / if(Symmetry(B)!=S,return(-1)); / * */
  if(useList,
    distro=List();
  );
  my(total:small,k:small,t:small,pass:small,half_widthB:small,yy:small);
  total=0;
  k=0;
  half_widthB=widthB\2;  
  widthB--;
  t=S/(abs(S)+!S); /* +!S prevents division by zero. */
  while(widthA>=widthB+k++,
    pass=1; 
    if(S,
      yy=0;
      for(y=k,k+half_widthB,
        if((A[y]!=B[yy++])||(A[y]!=t*A[2*k+widthB-y]),pass=0;break)
      )
    ,
      pass=A[k..k+widthB]==B;
    );
    total+=pass;
    if(pass&&useList,
      listput(distro,k)
    )
  );
  return(if(useList,distro,total))
}

A217626_firstTerms(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}

test_ifOK_conjectures_1_and_4_at_A217626(maxCase=10)={
  maxCase=min(10,maxCase); \\ Due space-complexity unsolved problems, this choice is currently restricted.
  maxCase=max(3,maxCase);  \\ For soundness since conjecture states 2<=m<n
  print("Note, for soundness and due technical limitations, the correction 3<=n<=10 is applied if required.");
  print("Assuming n="maxCase";");
  print("Processing. Please wait...");
  main_data=A217626_firstTerms(maxCase);
  my(OK=1,mfac:small);
  for(i=2,-1+maxCase,
    mfac=i!;
    stage_data=A217626_firstTerms(i);
    stage_distro=DetectIsBinA(stage_data,main_data,,1);
    if(#stage_distro!=(maxCase-i+1)!,print("\n\n*** Fatal: Conjecture 1 @ A217626 faied!!!, for m="i"; ***\n\n");return(0));
    stage_diffs=firstDiffs(Vec(stage_distro));
    OK=Symmetry(stage_diffs);
    /* print1(OK", "); */
    if(!OK,print("\n\n*** Fatal: The statement about a symmetric pattern of distribution at conjecture 1 fails for m="i"; ***\n\n");return(0));
    for(k=1,#stage_diffs,if(stage_diffs[k]%mfac,print("\n\n*** Error: Sorry!, Conjecture 4 fails for m="i"; ***\n\n");return(0)))
  );
  if(OK,print("Done. Conjectures are partially true up to: 2<=m<n (with n="maxCase")"));
  return(1)
}

\\  ...  
\\  ...   ----------------------------------------------- [ Examples (Sample execution's output dump) - Start ] ------------------------------------------
\\  ...  
\\  ...  Type ? for help, \q to quit.
\\  ...  Type ?15 for how to get moral (and possibly technical) support.
\\  ...  
\\  ...  parisizemax = 4294967296, primelimit = 1000000
\\  ...  (14:35) gp >  Some examples
\\  ...  (14:35) gp > DetectIsBinA([-9,0,9],[9,2,9,9,2,9,9,0,-9,9,2,9],-1)
\\  ...  %1 = 0
\\  ...  (14:35) gp > DetectIsBinA([9,0,-9],[9,2,9,9,2,9,9,0,-9,9,2,9],-1)
\\  ...  %2 = 1
\\  ...  (14:35) gp > DetectIsBinA([9,2,9],[9,2,9,9,2,9,9,0,-9,9,2,9],1)
\\  ...  %3 = 3
\\  ...  (14:36) gp > DetectIsBinA([9,2,9],[9,2,9,9,2,9,9,0,-9,9,2,9],0)
\\  ...  %4 = -1
\\  ...  (14:36) gp >  The idea is to force users to take into account the optimizations!
\\  ...  (14:36) gp > Pi_trunc_int_27=digits(floor(Pi*10^27));
\\  ...  time = 1 ms.
\\  ...  (14:37) gp > #Pi_trunc_int_27 
\\  ...  %6 = 28
\\  ...  (14:37) gp > Pi_trunc_int_27 
\\  ...  %7 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3]
\\  ...  (14:37) gp > DetectIsBinA([2,6],Pi_trunc_int_27)
\\  ...  %8 = 2
\\  ...  (14:39) gp > DetectIsBinA([2,6],Pi_trunc_int_27,0)
\\  ...  %9 = 2
\\  ...  (14:39) gp > DetectIsBinA([9,7,9],Pi_trunc_int_27,0)
\\  ...  %10 = -1
\\  ...  (14:39) gp > DetectIsBinA([9,7,9],Pi_trunc_int_27,1)
\\  ...  %11 = 1
\\  ...  (14:39) gp >  Although if using inside: S=Symmetry(B) it becomes is more friendly...
\\  ...  (14:44) gp > 
\\  ...  (14:44) gp > distro=List(); \\ redundant.
\\  ...  
\\  ...  (15:15) gp > p=A217626_firstTerms(10);
\\  ...  time = 31,324 ms.
\\  ...  (15:16) gp > count=DetectIsBinA(q,p,,0);
\\  ...  (15:16) gp > count 
\\  ...  %3 = -1
\\  ...  (15:16) gp > q=A217626_firstTerms(4);
\\  ...  (15:17) gp > count=DetectIsBinA(q,p,,0);
\\  ...  time = 479 ms.
\\  ...  (15:17) gp > count \\ Expected result: (10-4+1)! = 7! = 5040 according conjecture  
\\  ...  %6 = 5040
\\  ...  (15:17) gp > distro=DetectIsBinA(q,p,,1);
\\  ...  time = 488 ms.
\\  ...  (15:17) gp > #distro 
\\  ...  %8 = 5040
\\  ...  (15:17) gp > type(distro)
\\  ...  %9 = "t_LIST"
\\  ...  (15:17) gp > 
\\  ...  
\\  ...  (15:18) gp > distro_vec=Vec(distro);
\\  ...  time = 1 ms.
\\  ...  (15:19) gp > distro_vec1stDiffs=vector(-1+#distro_vec,k,distro_vec[k+1]-distro_vec[k]);
\\  ...  time = 6 ms.
\\  ...  (15:20) gp > Symmetry(distro_vec)
\\  ...  %13 = 0
\\  ...  (15:20) gp > Symmetry(distro_vec1stDiffs)
\\  ...  time = 1 ms.
\\  ...  %14 = 1
\\  ...  (15:20) gp > distro_vec1stDiffs[1..23]
\\  ...  %15 = [96, 24, 456, 24, 96, 24, 96, 24, 480, 120, 120, 1896, 120, 120, 480, 24, 96, 24, 96, 24, 456, 24, 96]
\\  ...  (15:21) gp > distro_vec1stDiffs[1..23]/24
\\  ...  %16 = [4, 1, 19, 1, 4, 1, 4, 1, 20, 5, 5, 79, 5, 5, 20, 1, 4, 1, 4, 1, 19, 1, 4]
\\  ...  (15:21) gp > trial_div24_distro_vec1stDiffs= distro_vec1stDiffs/24;
\\  ...  time = 2 ms.
\\  ...  (15:22) gp > prod(k=1,#trial_div24_distro_vec1stDiffs,denominator(trial_div24_distro_vec1stDiffs[k])==1)
\\  ...  time = 4 ms.
\\  ...  %18 = 1
\\  ...  (15:22) gp > V^oila!: This implies that: For 2<=m<n, If S is the "first differences" of a sequence giving
\\  ...  ..................... the starting position of each repetition for the first m!-1 terms  
\\  ...  ..................... inside the first n!-1 terms, then each element in S is 0 mod m!
\\  ...  ..................... ( Conjecture 4 @ A217626 )
\\  ...  ..................... ( This fact was suspected by the author, to be a general property approx. since Dec 27th 2016 )
\\  ...
\\  ...  A testing routine carefully written, confirms this and some other facts as far as they could be tried to check:
\\  ...
\\  ...  (17:23) gp > test_ifOK_conjectures_1_and_4_at_A217626(1)
\\  ...  Note, for soundness and due technical limitations, the correction 3<=n<=10 is applied if required.
\\  ...  Assuming n=3;
\\  ...  Processing. Please wait...
\\  ...  Done. Conjectures are partially true up to: 2<=m<n (with n=3)
\\  ...  time = 1 ms.
\\  ...  %1 = 1
\\  ...  (17:24) gp > test_ifOK_conjectures_1_and_4_at_A217626(30)
\\  ...  Note, for soundness and due technical limitations, the correction 3<=n<=10 is applied if required.
\\  ...  Assuming n=10;
\\  ...  Processing. Please wait...
\\  ...  Done. Conjectures are partially true up to: 2<=m<n (with n=10)
\\  ...  time = 38,085 ms.
\\  ...  %2 = 1
\\  ...  ----------------------------------------------- [ Examples (Sample execution's output dump) - End ] ------------------------------------------
\\  ...  
\\EOF