Collatz sieving

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

Collatz-afficionados will like this:

- - - - - - -

A060565m(n) = if(!n,return(1)); my(
x=2*n+1, x1=x
); while(
x1>=x, x1=(3*x1+1)/2; while(
!(x1%2), x1/=2; if(x1<=x, break)
)
); x1

A122458m(n) = if(!n,return(1)); my(
x=2*n+1, x1=x, c=0
); while(
x1>=x, c++; x1=(3*x1+1)/2; while(
!(x1%2), x1/=2; if(x1<=x, break)
)
); c

p2f(p2, w=9) = if(p2>w, Str("2^", p2), 2^p2)
p3f(p3, w=7) = if(p3>w, Str("3^", p3), 3^p3)

for(n=0, 21, my(
x=2*n+1, c=A060565m(n), p3=A122458m(n), p2=floor(1+p3*log(3)/log(2))
); printf(
"%3s| (%4sx +%3s) -> (%4sx +%3s) | %3s -> %3s\n",
n, p2f(p2), x, p3f(p3), c, x, c
)
)

--n|----p2-----x--------p3-----c--|---x------c-
  0| (   4x +  1) -> (   3x +  1) |   1 ->   1
  1| (  16x +  3) -> (   9x +  2) |   3 ->   2
  2| (   4x +  5) -> (   3x +  4) |   5 ->   4
  3| ( 128x +  7) -> (  81x +  5) |   7 ->   5
  4| (   4x +  9) -> (   3x +  7) |   9 ->   7
  5| (  32x + 11) -> (  27x + 10) |  11 ->  10
  6| (   4x + 13) -> (   3x + 10) |  13 ->  10
  7| ( 128x + 15) -> (  81x + 10) |  15 ->  10
  8| (   4x + 17) -> (   3x + 13) |  17 ->  13
  9| (  16x + 19) -> (   9x + 11) |  19 ->  11
 10| (   4x + 21) -> (   3x + 16) |  21 ->  16
 11| (  32x + 23) -> (  27x + 20) |  23 ->  20
 12| (   4x + 25) -> (   3x + 19) |  25 ->  19
 13| (2^59x + 27) -> (3^37x + 23) |  27 ->  23
 14| (   4x + 29) -> (   3x + 22) |  29 ->  22
 15| (2^56x + 31) -> (3^35x + 23) |  31 ->  23
 16| (   4x + 33) -> (   3x + 25) |  33 ->  25
 17| (  16x + 35) -> (   9x + 20) |  35 ->  20
 18| (   4x + 37) -> (   3x + 28) |  37 ->  28
 19| ( 256x + 39) -> ( 243x + 38) |  39 ->  38
 20| (   4x + 41) -> (   3x + 31) |  41 ->  31
 21| (  32x + 43) -> (  27x + 37) |  43 ->  37


Cross-check of 37:
x=8: ( 4x+ 5) = 37 -> ( 3x+ 4) = 28
x=7: ( 4x+ 9) = 37 -> ( 3x+ 7) = 28
x=6: ( 4x+13) = 37 -> ( 3x+10) = 28
:
x=0: ( 4x+37) = 37 -> ( 3x+28) = 28


Cross-check of 19:
x=1: (16x+ 3) = 19 -> ( 9x+ 2) = 11
x=0: (16x+19) = 19 -> ( 9x+11) = 11


Cross-check of 43:
x=1: (32x+11) = 43 -> (27x+10) = 37
x=0: (32x+43) = 43 -> (27x+37) = 37

- - - - - - -

-- Greetings, Ruud