Collatz divide by -2 instead

I've been toying around with the Collatz conjecture for a while, and in an effort to extend it to the negative integers I tried diving by $-2$ instead of by $2$. The new iteratively applied function is then:

$f(n) = \left\{ \begin{array}{ll} -\frac{n}{2} & \text{if n is even} \\ 3n+1 & \text{if n is odd} \end{array} \right.$

A couple of examples:

$1 \to 4 \to -2 \to 1 \to \dots$

$2 \to -1 \to -2 \to 1 \to \dots$

$-6 \to 3 \to 10 \to -5 \to -14 \to 7 \to 22 \to -11 \to -32 \to 16 \to -8 \to 4 \to -2 \to 1 \to \dots$

I have tested this with a quick python script, and it seems to eventually reach $1$ for all n between $-10^9$ and $10^9$, not including $0$.

Is there a relation between this function and the Collatz conjecture? In particular, would this series convergence to $1$ follow from the Collatz conjecture being true?

Solution 1:

A note how to test existence of cycles

Consider the notation for one (compressed) step, where we can reduce the discussion to that of odd numbers only. Also, numbers divisible by 3 need not be considered btw, because they cannot be the result of one transformation from such an odd value $a$ to $b$. Moreover, different from the Collatz-problem we can have positive and/or negative values in the consideration.
The definition of the "one-step-transformation" is: $$ b= {3a + 1\over (-2)^A } \tag 1$$ where the exponent $A$ is such, that the result $b$ is an odd integer again.

1) one-step-cycle

If we have a one-step-cycle then this means $b=a$ and we can rearrange: $$ a= {3a + 1\over (-2)^A } \\ (-2)^A = {3a+1 \over a} $$ $$ (-2)^A = (3 + {1 \over a}) \tag 2 $$ Obviously the rhs can assume only two integer values, which are perfect powers of $2$ , namely $a=1 \implies 3+1/a=4 , A=2$ and $a=-1 \implies 3-1/a=2 , A=1$.
The first value $a=1$ gives a cycle, because $(-2)^2 = 3+1 $, but not the second one because $ (-2)^1 \ne 3-1 $

So we know: there exists exactly one one-step-cycle using $a=1$.

2) Two step cycle

Consider now a two step cycle. This means $$ b= {3a + 1\over (-2)^A } \qquad a = {3b + 1\over (-2)^B } \tag 3$$

To test, whether such a cycle can exist, we do the product of both lhs and rhs to arrive at formula $$ a \cdot b= {3a + 1\over (-2)^A } \cdot {3b + 1\over (-2)^B } $$ where if we rearrange the denominators and the lhs: $$ (-2)^{A+B} = (3 + {1\over a} ) \cdot ( 3+ { 1\over b } ) \tag 4$$

Because $a=1$ already gives the one-step-cycle, we can assume, $a$ at least $\pm5$ and because $b \ne a$ it must be at least $b = \pm 7$ . We see, that on the rhs we can have at minimum $(3-1/5)(3-1/7) = 8 $ and as maximum $(3+1/5)(3+1/7) = 10 {2 \over 35} $
The only perfect power of 2 in this interval is $8$ so we must have $$ (-2)^S \overset?= 8 = (3-1/5)(3-1/7) $$ (Remark: I use always $S$ for the sum of all involved exponents, so in this case we have $S=A+B$)
The only solution allowing the equality in absolute values would be $S=3$ , but then $(-2)^3 = -8 \ne 8$ so this is no solution, and we know, that no 2-step-cycle exists

3) generalization

I leave the obvious generalization to you; with this method one can disprove a nice multitude of few-step-cycles with little effort; some of them because perfect powers of 2 are not near to products of $3 + 1/a$ - thus immediately requiring $a,b,c,...=1$ (but which means again the one-step-cycle) and for the disproof of others of them one must test sets of low bounded (absolute) values for $a,b,c,...$ and knowing $a,b,c,...$ must be low the search radius is not big.

4) Hypothese

In all my studies on generalizations of the Collatz-problem, I only found a) few cycles, b) short cycles, c) cycles on small elements $a,b,c,... $ and my handful of tests combined with your exhaustive search makes me much confident, that indeed no nontrivial cycle exists.

Remark The convergents of the continued fraction of $\log(3)/ \log(2)$ give values for $N$ (indicating the number of steps and exponent of power of 3 involved) and $S$ (indicating the sum of all exponents $A,B,C,...$ involved and indicating the exponent of the highest power of 2 involved where we shall have $2^S \gt 3^N \gt 2^{S-1}$ or $2^S \lt 3^N \lt 2^{S+1}$ depending on the signs of the $a,b,c,d,...$.
Having your exhaustive search assuring that all $a,b,c,...$ must be larger than $10^6$ My heuristic (using a rather simple procuedure in Pari/GP) show, that the method above allows to disprove all cycles of lengthes [updated] $N<2966$

I have a routine for finding the upper bound for $a_1$ in assumed cycles of length $N$. That means, the smallest element of a cycle must be smaller or equal than $a_1$. Assuming the next value $a_1'$ as smallest value of a cycle gives that in the required equation $(-2)^S \overset?= (3+1/a_1)(3+1/a_2)...(3+1/a_N)$ with N parentheses the rhs is already too small to match the lhs. Reworded it means: if we already know (from exhaustive search), that all numbers smaller or equal some upper bound $X$ go down to 1 (and are thus not part of a nontrivial cycle), then the cycle of length $N$ and its needed $a_1 \le X$ cannot exist. ($a_1'$ is the next possible number). The following q&d table uses actually $(2)^S$ instead of $(-2)^S$ but the logic is the same. Only that cycles of length $N \le 1000$ are documented, where $a_1 \gt 20000$ All other lengthes $N$ require far smaller minimal values $a_1$

                                  rhs is          rhs is
 diff(N)  N    a1        a1'      higher than S  lower than S    S 
 ----------------------------------------------------------------- 
         253  26735 -   26737 :  401.000000445 400.999999949     401
   53    306  99323 -   99325 :  485.000000022 484.999999978     485
  200    506  26363 -   26365 :  802.000000167 801.999999174     802
   53    559  44255 -   44257 :  886.000000272 885.999999876     886
   53    612  98867 -   98869 :  970.000000018 969.999999929     970
  147    759  25991 -   25993 :  1203.00000092 1202.99999943    1203
   53    812  36163 -   36167 :  1287.00000072 1286.99999988    1287
   53    865  54647 -   54649 :  1371.00000023 1370.99999983    1371 
   53    918  98411 -   98413 :  1455.00000005 1454.99999992    1455
   41    959  20593 -   20597 :  1520.00000163 1519.99999877    1520

Here the first rhs in the generalized formula $(4)$ (having $N$ parentheses) is computed based on $a_1$ and is larger or equal than $2^S$ and the next rhs is computed based on $a_1' \gt a_1$ and is too small to arrive at $2^S$.
Result: given $X=1 000 000$ we see, that all $a_1 \lt X$ and thus none of the cycles of the shown lengthes can exist.

[Appendix]
Here are the first few cycle-lengthes $N$ which allow the smallest element $a_1$ to be larger than $X=1\,000\,000$ , so that the displayed cycle-lengthes are not disproven using the upper bound by your exhaustive search only.

   N        a1          a1'         S       f(a1)        f(a1')     diff(N)
-----------------------------------------------------------------------------
  2966    1161955 -   1161959 :    4701  0.000000002 -0.000000001    2966
  3631   >1489099 -  >1489103 :    5755  0.000008467  0.000008465     665
  4296   >1487105 -  >1487107 :    6809  0.000286350  0.000286347     665
  4961   >1485109 -  >1485113 :    7863  0.000564521  0.000564518     665
  5267    1001761 -   1001765 :    8348  0.000000006 -0.000000002     306
  5626   >1483115 -  >1483117 :    8917  0.000842982  0.000842978     359
  5932    1157525 -   1157527 :    9402  0.000000002 -0.000000004     306
  ...       ...         ...        ...     ...         ...            ...

The term "f(a1)" means the following: Let $x = \log_2()$ of the product in the generalized rhs of equation (4) where the smallest/first element is $a_1$. Then "f(a1)" is the deviation of $x$ from $S$: $x-S$