| 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