Attempting to restate the question of whether the collatz conjecture has a nontrivial cycle as a combinatorics problem

Question

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.

Answer 1

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)