Re: Collatz sieving

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

On 2021-12-23 02:50, Ruud H.G. van Tol wrote:
> Collatz-afficionados will like this:

Variant, and now with statistics:

? run2(2^12+1)
- - - - -
#s      : 16389 (bits)
max(c2) : 8195
next(c2): 16437
sieved  : 97.76%
took    : 12.18s
- - - - -

-- Ruud


- - - - - - -
a2(n)= {
  if( n < 1, return([2,0,1,0]));  \\ (2*i+0) -> (1*i+0)

  my
  ( v2= 4
  , c2= 2 * n - 1
  , v3= v2
  , c3= c2
  );

  while
  ( 1
  , v3= 3 * v3 / 2;
    c3= (3 * c3 + 1) / 2;

    while
    ( !(v3%2) && !(c3%2)
    , v3/= 2;
      c3/= 2;
    );
    if( (v3 < v2), break ); \\ dropper

    if
    ( v3 % 2
    , v2*= 2;
      v3= v2;
      c3= c2;
    )
  );
  [v2,c2,v3,c3];
}

run2( N= 99, VERBOSE= 0 )= {
  my
  ( s=  binary(16^N)  \\ ok to enlarge
  , t0= getabstime()
  );

  for
  ( n= 0, N
  , my(v= a2(n)); 



    for
    ( i= 0, #s
    , my(k= v[2] + i*v[1] + 1);
      if(k > #s, break);  \\ dropper
      s[k]++;
    );

    if
    ( VERBOSE
    , printf
      ( "%3s| (%7sx +%3s) -> (%7sx +%3s)\n"
      , n,sf(v[1],2^10),v[2],sf(v[3],3^5),v[4]
      )
    )
  );

  my
  ( t1= getabstime()
  , r=  select(x->!s[x+1],[0..#s-1])
  );
  printf
  ( "- - - - -
#s      : %s (bits)
max(c2) : %s
next(c2): %s
sieved  : %.2f%%
took    : %.2fs
" , 2 * N + 1
  , 2 * r[1] - 1
  , 100 * (#s - #r) / #s
  , (t1 - t0) / 1000
  );
}
- - - - - - -