Re: About isperm()

[R J Cano <0xcc00ffffeeee@gmail.com>]

Merci.

Well, I also noticed that the max k possible is for #binary(N);

So we can be sure that what we are looking is between #binary(N)-1 >= k >= 2

Due N in base N is "10".

Yes it is a great deal regarding time reduction.

Great!, thanks Bill :-)

2017-05-14 8:38 GMT-05:00, 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.
>