R J Cano on Sun, 14 May 2017 15:06:55 +0200


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

About isperm()


Greetings!,

Dear Bill,

I found out this one, based only on Mersenne numbers: Those 2^x-1;

isperm(N)={
  my(x, y, z, t, t0);
  for(B=2, max(2, N-1),
    y=digits(N, B);
    x*=0;
    for(i=1, #y,
      t=1<<y[i];
      if(bitand(x, t),
        x*=0;
       break,
       x+=t)
    );
    if(x,
      t0=!(x%2);
      x++;
      x+=t0);
      t=ispower(x, , &z);
      if(t&&z==2,
        return(B)
    )
  );
  return(0)
}

It replies the question: What is the least base in which N is
expressed as a permutation for the first non negative integers,
entering all of them. It does match excepting for 3 N in {0,3,4} with
the definition www.oeis.org/A211187;

Cheers,

Remy.

P.S.:  I took into account some subtle details, regarding C/C++
instructions optimization, in order to take them in advantage when
compiling code with GP2C; For example, at the second program t0 might
be omitted by using something like: x+=1+!(x%2); instead of the
separated sequence of operators. There is none effect at first glance,
but when using both versions for generating for example 10 thousand
terms... this one is faster. Indeed with the aid of GP2C and compared
against Mathematica code, the time is reduced to a half.
isperm(N)={
  my(x, y, z, t, t0); 
  for(B=2, max(2, N-1), 
    y=digits(N, B);
    x*=0;
    for(i=1, #y,
      t=1<<y[i];
      if(bitand(x, t),
        x*=0;
       break,
       x+=t)
    );
    if(x,
      t0=!(x%2);
      x++;
      x+=t0);
      t=ispower(x, , &z);
      if(t&&z==2,
        return(B)
    )
  );
  return(0)
}