Is anything known about the size of the smallest number with stopping time $n$

Question

Last couple of days I've been thinking about the Collatz conjecture, and now I wonder if any relation is known between $n$ and the smallest number with stopping time $n$.

So for example, let's say I'm interested in numbers with stopping time $5$, then I would like to be able to say: A number with stopping time $5$ must be larger equal ....

Note that I'm not talking about the total stopping time. The stopping time is the number of times we apply the function before we reach a number smaller than the one we started with.

---

Edit: After finding the sequence I'm looking for in the OEIS (https://oeis.org/A122442) my attention has shifted to efficiently computing its terms. Now what I mean with efficiently is that I should be able to compute the first $1000$ terms in around a day (or less of course, but I'm doubtful that's possible). All ideas and input are appreciated.

Answer 1

It seems https://oeis.org/A122442 is the most complete source of information.

Answer 2

One thing which is quite obvious (I think) is, that for a stopping time $W=N+S$ the number of upwards-steps $N$ and the number of downward steps $S=N+B$ reflect (not too) roughly the number of involved powers of $3$ for the upwards, and the number of involved powers of $2$ for the downwards. So it must - for a stopping time of say $s$ from an initial number $a_0$ - hold that $a_0 \cdot {3^N \over 2^S} \approx a_s <= a_0$ . From this it is "obvious" that for any stopping time $W$ (if stopping occurs in finitely many steps at all) the number $W$ is roughly separable into $N + S$ or $2N+B$ where $S \approx N \cdot \log_2{(3)} $.

But whether there are any cases where no stopping occurs (or: no finite $W$ exists for some initial $a_0$) is not yet known.
So best we can hope for, is some guess for the stopping time in some "average case" - where we had to define what we mean with the "average case"... (and I think good examples for this can be found at T. Oliveiras' site)

---

An accidental addendum.
I looked at the periodicity with which the stopping-time lengthes occur when iterating from some $a_0$, explicitely: $a_0 \to a_1 \to a_2 \to \cdots a_{n-1} \to a_n$ where only $a_n \lt a_0$ when $a_0$ increases. Of course this should be cyclic with some power of 2. Here is a short table:

   a_0   l = stopping time
   --------------------------------
    0    1                                      
    2    1
    4    1
    .... 
    1    3                                                                        
    5    3
    9    3
    ....    
    3    6
   19    6
   35    6
   ....
   11    8   23    8
   43    8   55    8
   75    8   87    8
  ....
    7   11   15   11   59   11
  135   11  143   11  187   11
  263   11  271   11  315   11
  ....
   39   13   79   13   95   13  123   13  175   13  199   13  219   13
  295   13  335   13  351   13  379   13  431   13  455   13  475   13
  551   13  591   13  607   13  635   13  687   13  711   13  731   13
  .... 
  287   16  347   16  367   16
  423   16
  ....
  927   60
  671   63
  155   65
  447   65
  103   68
   91   73
   71   83
   47   88
   63   88
   31   91
   27   96
  703  132
  ... 

For the stopping times 1 to 13 it is relatively obvious, that they occur cyclically with $a_0 = r+ b\cdot2^A$ and some fixed $r$ and exponent $A$ and with variable $b=1,2,3,4,...$ .
These periodicities allow to reduce the effort of the naive search for stopping-times a bit; from the first block it appears that each second number, beginning at 0 has the same stopping time 1, so we need only check the odd numbers. The next block indicates, that all numbers $1,5,9, ... = 1+4b$ have the stopping time 3 and thus we need now only check $3,7,11,...$ and so on. But again we find periodicities and can omit a fraction of numbers from the naive search.

Surely, this cannot meaningfully extended to arbitrary stopping times (the pattern becomes complicated) but for small lengthes this can reduce the number of $a_0$ to be checked to $1/2, 1/4, 1/8,...$ as far as you desire and are willing to implement the table of rules.

Here is a small table of the periodicities of the stopping times. Stopping times equal and greater than 8 have multiple cycles but always with their typical period-length of $2^A$ . (I've no pattern for the r's so far):

 l    a_0  = r+2^A * k     (where l = stopping time)
 -------------------------------------
 1:   0 +  2*k
 3:   1 +  4*k

 6:   3 + 16*k
 8:  11 + 32*k   23 + 32*k

11:   7 +128*k   15+128*k   59+128*k
13:  39 +256*k   79+256*k   95+256*k   123+256*k  175+256*k 199+256*k 219+256*k

---

[update 2]
I implemented a Pari/GP-routine which reproduced the list for lae up to 130 in 8 secs, however, at the end there are holes. I tested up to $a=2^{21}$. Here is the list. Possibly the algorithm is a progress in efficiency (but should again be improvable). An improvement over the pure documentation of the stopping time is to show the number $N$ of involved powers of 3 (or $n=3n+1$ - steps), because one can see the missing stopping times by the occuring holes ($N$ must be consecutive)

   legend:
     st : stopping time                          
     a  : number for which stopping time st occurs first             
     b  : transformation of a after st steps (b \lt a)                   
     N  : number of steps involving n=3n+1                    
     S  : number of steps involving n=n/2                     



        a        b    N    S    st=N+S
       ------------------------------------ 
        2        1    0    1    1
        1        1    1    2    3
        3        2    2    4    6
       11       10    3    5    8
        7        5    4    7   11
       39       38    5    8   13
      287      205    6   10   16
      231      124    7   12   19
      191      154    8   13   21
      127       77    9   15   24
      359      325   10   16   26
      511      346   11   18   29
      239      122   12   20   32
      159      122   13   21   34
      639      365   14   23   37
      283      244   15   24   39
      991      637   16   26   42
      251      244   17   27   44
      167      122   18   29   47
      111       61   19   31   50
     1695     1378   20   32   52
     1307      797   21   34   55
      871      797   22   35   57
      927      637   23   37   60
      671      346   24   39   63
      155      122   25   40   65
      103       61   26   42   68
     1639     1424   27   43   70
       91       61   28   45   73
     3431     3349   29   46   75
     3399     2489   30   48   78
     2287     1256   31   50   81
       71       61   32   51   83
     6395     3949   33   53   86
       47       46   34   54   88
       31       23   35   56   91
     2047     1067   36   58   94
       27       23   37   59   96
     1819     1067   38   61   99
    17691    15548   39   62  101
     6887     4541   40   64  104
     4591     4541   41   65  106
    13439     9968   42   67  109
     6383     3551   43   69  112
     4255     3551   44   70  114
     7963     4984   45   72  117
     7527     7066   46   73  119
    12399     8729   47   75  122
     7279     3844   48   77  125
     1583     1256   49   78  127
     1055      628   50   80  130
      703      628   51   81  132
    15039    10049   52   83  135
   111259    55747   53   85  138
    41407    31123   54   86  140
    62079    34994   55   88  143
    77031    65134   56   89  145
    94959    60218   57   91  148
    34239    32572   58   92  150
   138751    98987   59   94  153
    99007    52975   60   96  156
   106239    85267   61   97  158
   187327   112760   62   99  161
    69375    62641   63  100  163
   226767   153563   64  102  166
   104303    52975   65  104  169
    10087     7688   66  105  171
   256511   146563   67  107  174
    67583    57925   68  108  176
    90111    57925   69  110  179
    45055    43444   70  111  181
   126575    91535   71  113  184
   299259   162307   72  115  187
    96383    78413   73  116  189
   336199   205133   74  118  192
    64255    58810   75  119  194
    84383    57925   76  121  197
    57115    29405   77  123  200
    56255    43444   78  124  202
    37503    21722   79  126  205
    60975    52975   80  127  207
    45127    29405   81  129  210
   393967   385043   82  130  212
   423679   310559   83  132  215
  1759951   967537   84  134  218
    35655    29405   85  135  220
   434223   268556   86  137  223
   495687   459857   87  138  225
   665215   462844   88  140  228
  1643759   857770   89  142  231
   528895   413995   90  143  233
   730559   428885   91  145  236
   437247   385043   92  146  238
   432923   428885   94  149  243
   565247   419981   95  151  246
   288615   160832   96  153  249
   376831   314986   97  154  251
   ??????   ??????   98             
   611455   574993   99  157  256
   608111   428885  100  159  259
  1585403   838607  101  161  262
   405407   321664  102  162  264
   270271   160832  103  164  267
   362343   323434  104  165  269
   401151   268556  105  167  272
  1563647   785096  106  169  275
  1042431   785096  107  170  277
   ??????   ??????  108  
   381727   323434  109  173  282
   667375   424094  110  175  285
   626331   597017  111  176  287
  1691807  1209463  112  178  290
  1564063   838607  113  180  293
  1541147  1239478  114  181  295
  1027431   619739  115  183  298
  1127871  1020485  116  184  300
  1991615  1351492  117  186  303
  1327743   675746  118  188  306
  ???????  ???????  119-133
  2091647  1365679  134  213  347
  1394431  1365679  135  214  349
  ???????  ???????  136-139
  1689023  1570192  140  222  362
  1126015   785096  141  224  365

(In the holes, $S$ and $st$ can uniquely be determined, but I'm too lazy at the moment)

This is the Pari/GP-code so far:

{stopval(a)=local(b=a,N,S,st); \\ produce vector for some a
                               \\ which shall be shown in the list
    for(k=1,2000,        \\ just some overostimated number
          if(b % 2 == 0
             , b = b/2;   S++;
             , b = 3*b+1; N++;
            );
          if(b<=a,break())
         );
    return([a,b,N,S,st=N+S]); }


{maxn = 2^21; n_list=vectorv(maxn,r,-1);
alist=matrix(2000,5);st_list=vectorv(1000); \\ just some overestimated sizes
alae=0;
for(n=1,maxn, 
      if(n_list[n]>-1,next());  \\ if n_list[n] was already marked do nothing
      tmp=stopval(n);        \\ get vector of stopping-time coefficients for current n
         curN=tmp[3];curS=tmp[4];S2=2^curS;    \\ extract relevant information
         forstep( j=n, maxn,S2, n_list[j]=curN);  \\ mark entries for higher n as done
      if ( st_list[1+curN] > 0, next()); \\ if that stopping time was already detected
                                \\ earlier do nothing
      alae++;alist[alae,]=tmp;  \\ otherwise put info into list
      st_list[1+curN] = n;
   );
alist=VE(alist,alae,5);   \\ cut away from alist the unused rows and columns
alistso=vecsort(alist~,[3,1])~;
print("ok");}
\\ the matrix "alistso" is the result which is printed above
\\ with maxn=2^20 this used 4 secs, with maxn=2^21 this used 8 secs, 
\\ and  maxn=2^22 used 16 secs