Re: [Collatz] how to best derive x and T^n(x) from a parity vector

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

On 2024-02-14 17:16, Ruud H.G. van Tol wrote:
> On 2024-02-12 11:26, Bill Allombert wrote:
> > On Sun, Feb 11, 2024 at 09:05:58PM +0100, Ruud H.G. van Tol wrote:
> > > [...] So we can try (43, 47, 51, 55, 59, ...) and find that x = 59 
> > > works:
> > > (81 * 59 + 85) / 128 = 38
> > So you want to solve
> > 3^4 * x + 85 = 0 [mod 2^7] ?
> >
> > You can do
> > ? -Mod(85,2^7)/3^4
> > %1 = Mod(59,128)
> >
> > Or even
> >
> > ? -85/81%128
> > %2 = 59
>
> Thanks, that made me do:
>
> ? ok(n) = {
>   my(b=binary(n), x=1); for(i=1, #b, if(b[i], x*=3/2, x/=2); x<1 && 
> i<#b && return(0)); x<=1;
> }
>
> ? show(n) = {
>   my(b=binary(n), x=1, k=0, t=0, f="%3s + i*2^%2s -> %3s + i*3^%2s");
>   n>0 || return(strprintf(f,2,1,1,0));
>   for(i=1, #b, if(b[i], x*=3/2;k=(3*k+1)/2;t++, x/=2;k/=2));
>   my(v2=-numerator(k)/3^t%2^#b, v3=v2*3^t/2^#b+k);
>   strprintf(f, v2, #b, v3, t);
> }
>
> ? [ print(show(n)) |n<-[0..2^7], ok(n) ];
>
>    2 + i*2^ 1 ->    1 + i*3^ 0
>    1 + i*2^ 2 ->    1 + i*3^ 1
>    3 + i*2^ 4 ->    2 + i*3^ 2
>   11 + i*2^ 5 ->   10 + i*3^ 3
>   23 + i*2^ 5 ->   20 + i*3^ 3
>   59 + i*2^ 7 ->   38 + i*3^ 4
>    7 + i*2^ 7 ->    5 + i*3^ 4
>   15 + i*2^ 7 ->   10 + i*3^ 4

Cleaner show:

? show(n) = {
  my(b=binary(n), k=0, f="%3s + i*2^%2s -> %3s + i*3^%2s");
  n>0 || return(strprintf(f, 2,1,1,0));
  for(i=1, #b, if(b[i], k=(3*k+1)/2, k/=2));
  my(t=hammingweight(n), v2=-numerator(k)/(3^t)%(2^#b), 
v3=v2*(3^t)/(2^#b)+k);
  strprintf(f, v2,#b,v3,t);
}