R J Cano on Mon, 15 May 2017 05:28:42 +0200


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

Re: About isperm()


Dear friends,

isperm() was designed to answer the question: "Which is? (if it
exists, otherwise return zero) the least base B smaller than n where n
is represented by a permutation without repetitions for all the first
m non negative integers (where m <= B)".

And for such reason isperm(3)=isperm(4)=0, due 3 = 11[2], and 4 =
11[3] = 100[2], and there are no more smaller bases. Besides these
exceptions, isperm() matches with OEIS A211187;

After additional contemplation and by including (or more precisely, by
having them also into account) some observations made this morning by
Bill, finally this version (possibly the fastest implementation) is
ready.

I share the code here just in case if it were of interest for someone else.

Anecdotically (this would be the third time it happens to me), if we
forget to declare explicitly types inside the my(), either the code
won't compile, or if additionally "Vecsmall" were totally absent, then
at some point execution crashes claiming "Bug in GP, Bus error". Of
course, such message escapes from my current understanding, although I
am sure that such behavior is provoked by the code we are trying and
not due something actually bad with GP (a valuable lesson in my case,
hehe).

Cheers,

Remy.

P.S.: This one shown below (Gives 10 thousand terms in just 41 seconds
when running on Linux at an AMD64 E-300 APU [1.30Ghz] after a GP2C
compilation, GP 2.9.2);

isperm(N)={
  my(c:small,x:vec,y:vecsmall,z:vecsmall);
  for(B=2, max(2, N-1),
    y=Vecsmall(digits(N,B));
    x=vector(#y,i,i);
    for(i=1,#y,if(!y[i],y[i]=x[#x];break));
    z=Vecsmall(0,#y);
    c=0;
    for(i=1,#y,
      c+=vecsearch(x,y[i])&&if(!z[y[i]],z[y[i]]=1;1,break)
    );
    if(c==#y,return(B))
  );
  return(0)
}