Ruud H.G. van Tol on Sun, 16 Jan 2022 09:39:04 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Collatz, first_non_higher



succ(c2) = {
  my
  ( c3= c2
  , p2= 0  \\halvings
  , p3= 0  \\triplings
  );
  if( !(c2%2), return( [1,0,0,0] ) );

  while
  ( c3 >= c2
  , c3 = ( 3 * c3 + 1 ) / 2;
    p2++;  \\halvings
    p3++;  \\triplings
    while
    ( c3 >= c2 && !(c3%2)
    , c3/= 2;
      p2++;  \\ halvings
      if( 1 == c3, break );
    );
    if( 1 == c3, break );
  );
  [ p2, c2, p3, c3];
}


- - - - - -

If `Collatz_successor(c2) = c3`,
and `p2` is the number of involved halvings,
and `p3` is the number of involved triplings,
then the tuple `[c2, p2, c3, p3]`
defines a "sieving formula":
`(c2 + 2^p2*i) -> (c3 + 3^p3*i) (for i ∈ ℕ)`.

- - - - - -

An interesting "optimal" case for Collatz
is to go from any odd number
to the first non-higher (odd or even) number:
`1->4->2->1 (p2=2, p3=1)`,
`3->10->5->16->8->4->2 (p2=4, p3=2)`,
etc.
See https://oeis.org/A177789 "dropping time".

Notice that `2^p2` then is
the first power of 2 above `3^p3`,
so `p2 = 1 + floor(p3*log(3)/log(2))`.
(warning: proving this to be,
without "using Collatz",
is very interesting)

Also notice that `2^p2 > c2`
(as otherwise it is a duplicate formula).
(easy)

- - - - - -

Initial examples (with `c2 = (n > 0) ? (2*n-1) : (0)`)

 n  c2  c3 p2 p3  formula                         examples
--  --  -- -- --  ------------------------------  ----------------------
 0   0   0  1  0  (   2*i +  0) -> (   1*i +  0)  0->0, 2->1, 4->2
 1   1   1  2  1  (   4*i +  1) -> (   3*i +  1)  1->1, 5->4, 9->7
 2   3   2  4  2  (  16*i +  3) -> (   9*i +  2)  3->2, 19->11, 35->20
 3   5   4  2  1  Skip, as (c2 > 2^p2), so see (c2 mod 2^p2).
 4   7   5  7  4  ( 128*i +  7) -> (  81*i +  5)  7->5, 135->86
...
12  23  20  5  3  (  32*i + 23) -> (  27*i + 20)  23->20, 55->47, 87->74
14  27  23 59 37  (2^59*i + 27) -> (3^37*i + 23)  27->23, ...

Notice that the even-to-odd step is covered by formula-0.

From 27 to 1:
(14: 27->23, 12: 23->20, 0: 20->5, 1: 5->4, 0: 4->2, 0: 2->1)

- - - - - -

Have fun with Collatz!

-- Greetings, Ruud

P.S. IMO, Collatz really needs no proof,
not more than Riemann does,
and rather is a nicely relationship to explore
between addition and multiplication,
much like exp/log.