16
$\begingroup$

It occurs to me that the question about whether non-trivial cycles exist for the collatz conjecture can be restated as these two questions (details on how this relates to the collatz conjecture can be found here):

  • Is there a general method for determining how many distinct values of $t_1, t_2, \dots, t_k$ exist for a given $k$ such that:

    • $t_k > t_{k-1} > \dots > t_2 > t_1 > 0$
    • $2\left(2^{t_k} - 3^k\right) < 3^{k-1} + \sum\limits_{i=1}^{k-1}3^{k-1-i}2^{t_i}$
    • $2^{t_k} - 3^k > 1$
  • Would it follow that as $k$ increases, the number of distinct values approaches infinity?

It seems to me that the conjecture is false if any nontrivial cycle occurs. A non-trivial cycle occurs if $2^{t_k}−3^k$ divides $3^{k−1}+\sum\limits_{i=1}^{𝑘−1}3^{h−1−i}2^{t_i}$ which would seem to me be a high probability if there are an infinite number of distinct values. Infinity does not mean this is necessary the case. More information is needed on the variability of the distinct values

Do my assumptions sound reasonable? Are there any well known papers that investigate the collatz conjecture from this viewpoint?


Update: By "non-trivial" cycles, I mean cycles that involve $2^{t_k} - 3^k > 1$ and include all cycles listed here as "trivial".

I have added a third bullet point above to clarify this point. Thanks to Rosie F for noticing that it was missing.

$\endgroup$
13
  • 2
    $\begingroup$ I voted to close because your questions are too unfocused. You ask four questions in one post, with very little explanation as to what motivates the one questions you choose to ask. $\endgroup$
    – amWhy
    May 26, 2022 at 16:46
  • 5
    $\begingroup$ It might help if you move your first comment into the question body as background/motivation. $\endgroup$
    – Alexander Gruber
    May 26, 2022 at 18:57
  • 2
    $\begingroup$ With no restrictions, the number of possible distinct values is ${t_k}\choose{k}$ (which is equivalent to the number of ways you can write the parity vector of your sequence). But this is too broad. For instance, there are a lot of negative values for $(2^{t_k}-3^k)$ (e.g.$t_k=k$) but they couldn't lead to a cycle. Also, in a cycle, different sums of $t_k$ are divisible by $(2^{t_k}-3^k)$ (since each element of the cycle give an integer value for that division), which means that a lot of combinations are in fact very dependent one to another, messing with your probabilities. $\endgroup$
    – Collag3n
    May 27, 2022 at 10:01
  • 4
    $\begingroup$ Note that if you limit your search to $n_{min}$ and $t_k=\lceil k \cdot log_2 3\rceil$ (which is generally used in collatz sieve optimization), the number of distinct values that can lead to an integer division can be found in oeis.org/A100982 $\endgroup$
    – Collag3n
    May 27, 2022 at 10:21
  • 2
    $\begingroup$ There are indeed non-trivial cycles (involving $-2$, $-5$ and $-17$ respectively) if the process is applied to all integers. Where do you restrict to the positive integers? It can't be $t_i>0$: you require the $t_i$ to be an ascending sequence, which shows that you do not use $t_i$ for the successive terms of a Collatz sequence. $\endgroup$
    – Rosie F
    May 29, 2022 at 9:54

1 Answer 1

2
$\begingroup$

Just to add some more combinatorical information.

Preamble: I'm used to use the following letters, which are different from yours, and I'm lazy to adapt this, please bare with me...

I use

  • $N$ for the (N)umber of odd-steps (you have $k$)
  • $S$ for the (S)um-of-exponents-at-$2$ (or numbers of even steps in the original Collatz-definition) (you have $t_k$)
  • $A,B,C,...$ or $A_k \mid _{k=1..N}$ for the single exponents,
  • with conditions $1 \le A_k \le A_\max$ and $S = \sum_{k=1}^{\small N} A_k$
  • where $A_\max = S- N+1$

I looked empirically for the number of possible sets of exponents $A_k$ with the restriction that $S=\lceil N \log_2(3) \rceil$ - that means the sets of orbit-candidates which must been tested for cyclicity.

Here, rotations of the exponents, for example $A,B,C,D$ and $B,C,D,A$, are taken as duplicate list entries of a cycle-candidate and are only inserted as one instance in the final list.

Here is the empirical list of sets of cycle-candidates for $N=2 .. 8$:

  N   S  minA  maxA      c         sets of exponents A_k for orbits to be tested
----------------------------------------------------------------------------------
[ 2,  4,    1,   3]  ---  2        [1, 3][ 2, 2]
[ 3,  5,    1,   3]  ---  2        [1, 1, 3][ 1, 2, 2]

[ 4,  7,    1,   4]  ---  5        [1, 1, 1, 4][ 1, 1, 2, 3][ 1, 1, 3, 2][ 1, 2, 1, 3][1, 2, 2, 2]
[ 5,  8,    1,   4]  ---  7        [1, 1, 1, 1, 4][ 1, 1, 1, 2, 3][ 1, 1, 1, 3, 2][ 1, 1, 2, 1, 3][ 1, 1, 2, 2, 2][ 1, 1, 3, 1, 2][ 1, 2, 1, 2, 2]

[ 6, 10,    1,   5]  --- 22        ... ... ...

[ 7, 12,    1,   6]  --- 66
[ 8, 13,    1,   6]  --- 99

[ 9, 15,    1,   7]  --- 335
[10, 16,    1,   7]  --- 504
-----------------------------------------------------------
    for Collatz over the negative numbers, S=ceil(N*ld3)-1 (!!)
[ 1,  1,    1,   1]  --- 1   [1]                                            

[ 2,  3,    1,   2]  --- 1   [1, 2]                                         
[ 3,  4,    1,   2]  --- 1   [1, 1, 2]                                      

[ 4,  6,    1,   3]  --- 3   [1, 1, 1, 3; 1, 1, 2, 2; 1, 2, 1, 2]           
[ 5,  7,    1,   3]  --- 3   [1, 1, 1, 1, 3; 1, 1, 1, 2, 2; 1, 1, 2, 1, 2]  

[ 6,  9,    1,   4]  --- 10  [1, 1, 1, 1, 1, 4; 1, 1, 1, 1, 2, 3;  ... ]    

[ 7, 11,    1,   5]  --- 30  [1, 1, 1, 1, 1, 1, 5; 1, 1, 1, 1, 1, ... ]     
[ 8, 12,    1,   5]  --- 43  [1, 1, 1, 1, 1, 1, 1, 5; 1, 1, 1, 1, ... ] 
...
==================================================================
          c = # orbits-to-be-tested (cyclic/repetitions removed)

My q&d-routine to detect this is extremely time-consuming; but the results and very likely the continuation of this can be found in the OEIS, hidden in the following (infinite) rectangular array (headers-lines are mine, "maxA" is reference to mine, square brackets indicate my empirical numbers $c$ of-orbits-to-be-tested):

table starts:
N:1  2  3   4    5   6    7    8    9   10   11    12       maxA
-----------------------------------------------------------------
 [1,]1,  1,  1,  1,  1,   1,   1,   1,   1,   1,    1, ...    2
  1,[2,  2,] 3,  3,  4,   4,   5,   5,   6,   6,    7, ...    3
  1, 2,  4, [5,  7,]10,  12,  15,  19,  22,  26,   31, ...    4
  1, 3,  5, 10, 14,[22,] 30,  43,  55,  73,  91,  116, ...    5
  1, 3,  7, 14, 26, 42, [66,  99,]143, 201, 273,  364, ...    6
  1, 4, 10, 22, 42, 80, 132, 217,[335, 504,]728, 1038, ...    7


Update: The T()-formula in OEIS is extremely helpful!

Here is the list of systematic $c(N)$ (= for each $N$) with $N=1..29$: $$ [1, 2, 2, 5, 7, 22, 66, 99, 335, 504, 1768, 6310, 9690, 35530, 54484, 204347, 312455, 1193010, 4552275, 7056280, 27293640, 42181080, 165056400, 644637006, 1005633632, 3964522026, 6167026726, 24512635642, 38036848410,\ldots]$$
(Here the same for Collatz-over-the-negative-numbers, $S=\lceil N \log_2(3) \rceil -1$) $$ [1, 1, 1, 3, 3, 10, 30, 43, 143, 201, 728, 2652, 3876, 14550, 21318, 81719, 120175, 468754, 1820910, 2731365, 10752060, 16128424, 64188600, 254463276, 386782164, 1547128656, 2349343610, 9470798326, 14369476066,...]$$ $\phantom{aaaaaaaaaaaa}$ (Note that there are $3$ cycles in the negative numbers)
Your question

  • "Would it follow that as k increases, the number of distinct values approaches infinity?"

is surely to be answered as "yes"; the number of candidate-orbits (even if rotations are ignored) seem to be exponentially in $N$ (your $k$).

Appendix: The Pari/GP-routines I've used is:

T(n, k) = sumdiv(gcd(n, k), d, eulerphi(d)*binomial((n+k)\d, n\d))/(n+k)  
 \\ this formula has been taken from OEIS-entry

l2=log(2);l3=log(3);ld3=l3/l2; \\ define common constants

{c_list=List([1]);   \\ initialize a List "c_list" with first value 1
for(N=2,29 , 
    S=ceil(N*ld3); \\ value for S required to allow cyclic orbit at all
    maxA=S-N; 
    c=T(maxA,N);
    listput(c_list,c); \\ append c at "c_list"
   );}
print(c_list)
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .