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:30, Ruud H.G. van Tol wrote:
> 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) = [...]
> >
> > ? [ 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

show(n) = {
  my(f="%3s + i*2^%2s -> %3s + i*3^%2s");
  n>0 || return(strprintf(f, 2,1,1,0));
  my(p2=1+logint(n,2), p3=hammingweight(n), r=0);
  for(i=1,p2, if(bittest(n, p2-i), r=(3*r+1)/2, r/=2));
  my(v2=-numerator(r)/(3^p3)%(2^p2), v3=v2*(3^p3)/(2^p2)+r);
  strprintf(f, v2,p2,v3,p3);
}