Collatz partitions

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

My "Collatz sieve" formula:

   2^p2 * i + c2 -> 3^p3 * i + c3 (i >= 0)

- - - - -

`c2` = 0, represents all evens:
  2^(1) * i + (0) -> 3^(0) * i + (0)
or as a vector: [p2,c2,p3,c3] = [1,0,0,0]

Each odd `c2` represents a "partition",
identified by its smallest element (`c2`).

Each partition has a single offset (2^`p2`)
to generate the next elements.

partition_c2(n == 0) = `c2`
partition_c2(n >  0) = partition_c2(n-1) + 2^`p2(c2)`

- - - - -

For any odd `c2`:
- each `p2` is the minimal power-of-2
where 2^`p2` > 3^`p3`: floor(1+p3*log(3)/log(2))
- so each `p3` is the maximal power-of-3
where 3^`p3` < 2^`p2`: floor(p2*log(2)/log(3))


? [ [3^p3, (my(p2=floor(1+p3*log(3)/log(2)))*0+ 2^p2)] | p3 <- [0..5] ]
[[1, 2], [3, 4], [9, 16], [27, 32], [81, 128], [243, 256]]

? [ [2^p2, (my(p3=floor(p2*log(2)/log(3)))*0+ 3^p3)] | p2 <- [0..5] ]
[[1, 1], [2, 1], [4, 3], [8, 3], [16, 9], [32, 27]]

(so that [8, 3] will never be involved)

- - - - -

My next aim is (still) to show how to efficiently
limit the search space
when going back from c3 to c2.

There is an optimal (first-lower) c3 for every c2,
but there are 1-or-more c2 (partitions) for each c3.

--
Greetings, Ruud

- - - - -

/*
How to (optimally) go from c2 to c3:
1. c3 is the first-lower (odd or even) value
   in the trajectory of c2;
2. p3 is the number of triplings involved;
3. p2 is the number of halvings involved
   (for odd c2: the first power-of-2 greater than p3);

This maps any value to a lower value, etc.
*/
c2_c3( c2= 0 )= {
  \\ evens: 2^(1)*x+(0) -> 3^(0)*x+(0)
  if( (c2 < 1), return([1,0,0,0]) );

  my( p2= valuation(c2,2) );
  c2/= 2^p2; \\oddify

  \\ 2^(2)*(x+i)+1 -> 3^(1)*(x+i)+1 (i >= 0)
  if
  ( (1 == (c2 % 4))
  , return([ 2, c2, 1, 3*(c2-1)/4 +1 ])
  );

  my( p3= 0, c3= c2 );
  while
  ( (c3 >= c2)
  , c3= (3 * c3 + 1) / 2;
    p2++;
    p3++;
    while
    ( !(c3 % 2)
    , c3/= 2;
      p2++;
      if( (c3 <= c2), break); \\dropper
    );
  );
  [ p2, c2, p3, c3 ];
}

/*
Map zero (which represents all evens)
and any odd > 0,
to its (unique, optimal) "Collatz sieve" formula:
*/
show_c2_c3( x= 0, N= 29 )= {
  if
  ( x && !(x%2)
  , error("x must be either 0, or an odd, so not (",x,")");
  );

  my( n0= if( x, (x-1)/2, 0 ) );

  for
  ( n= n0, n0 + N
  , my( [p2,c2,p3,c3]= c2_c3( if( n, (n-1)*2+1, 0 ) ) );
    if
    ( (c2 <= 2^p2)  \\hide duplicates
    , printf
      ( "%3s| (%5sx + %3s) -> (%4sx + %3s)  (%s, ...)\n"
      , n, Str("2^",p2), c2, Str("3^",p3), c3
      , strprintf
        ( "%3s, %3s+ 1*2^%2s, %3s+ 2*2^%2s"
        , c2, c2, p2, c2, p2
        );
      );
    );
  );
} \\ Example: show_c2_c3(0,91)

- - - - - --