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-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

-- Ruud