# 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?

• Perhaps this was a golden idea... In all other collatz-generalization were at most finitely many (actually a handful) cycles found, and all on small numbers only. I've also tried some of my cycle-detection/-rejection-formulae without finding a cycle. For me it is more than likely, that no other than the "trivial" cycle including 1 exists. – Gottfried Helms Feb 28 '17 at 13:02
• @Gottfried Thanks! Would you mind sharing your cycle-detection-formulae? I'll try a much larger and more optimised bruteforce later. – Todd Sewell Feb 28 '17 at 16:23

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$

update Some heuristical data.

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$

• Wow, quite an elaborate answer. You'll have to give me some time to work through it completely. One question, right after equation (4), why can't $a = \pm 3$ ? – Todd Sewell Feb 28 '17 at 20:56
• In a cycle, all elements $a,b,c,...$ is also results of a transformation. But a result of a $(3x+1)/2^X$-transformation cannot be divisible by $3$. So $a ,b,c,... \in \pm(6k \pm1)$ – Gottfried Helms Feb 28 '17 at 21:03