11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gottfried Helms Feb 28 '17 at 13:02
  • $\begingroup$ @Gottfried Thanks! Would you mind sharing your cycle-detection-formulae? I'll try a much larger and more optimised bruteforce later. $\endgroup$ – Todd Sewell Feb 28 '17 at 16:23
5
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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$ ? $\endgroup$ – Todd Sewell Feb 28 '17 at 20:56
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Gottfried Helms Feb 28 '17 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.