Re: About isperm()

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, May 14, 2017 at 08:06:46AM -0500, R J Cano wrote:
> 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)
> }

You can improve performance a lot for large N by noting that there is an
inequality: if k is the number of digits then:

B^{k-1} <= sum_{i=0}^{k-1} (k-i)*B^i <= N <= sum_{i=0}^{k-1} (i+1)*B^i <= k*(B^k-1)/(B-1)
so
B^{k-1} <= N <= k*(B^k-1)/(B-1)

So for each k, by solving this for B, you get a small range of B to check.

For small k, you can also check all the possible permutation:
test(N,k)=for(i=0,k!-1,my(R=nfroots(,Pol(numtoperm(k,i))-N));if(#R,return(vecmin(R))))

Cheers,
Bill.