cp's OEIS Frontend

A177789 Irregular triangle read by rows in which row n gives the congruences (mod 2^A020914(n)) satisfied by the numbers having dropping time A122437(n+1) in the Collatz (3x+1) iteration.

%I A177789 #124 Aug 20 2025 22:37:50
%S A177789 0,1,3,11,23,7,15,59,39,79,95,123,175,199,219,287,347,367,423,507,575,
%T A177789 583,735,815,923,975,999,231,383,463,615,879,935,1019,1087,1231,1435,
%U A177789 1647,1703,1787,1823,1855,2031,2203,2239,2351,2587,2591,2907,2975,3119
%N A177789 Irregular triangle read by rows in which row n gives the congruences (mod 2^A020914(n)) satisfied by the numbers having dropping time A122437(n+1) in the Collatz (3x+1) iteration.
%C A177789 The dropping time is the number of Collatz iterations required to reach a lower number than starting value. Garner mentions these congruences. The first term in row n is A122442(n+1) for n > 1. The length of row n is A100982(n).
%C A177789 The triangle means:
%C A177789   numbers 0 (mod 2) and > 0 have dropping time 1;
%C A177789   numbers 1 (mod 4) and > 1 have dropping time 3;
%C A177789   numbers 3 (mod 16) have dropping time 6;
%C A177789   numbers 11, 23 (mod 32) have dropping time 8;
%C A177789   numbers 7, 15, 59 (mod 128) have dropping time 11;
%C A177789   numbers 39, 79, 95, 123, 175, 199, 219 (mod 256) have dropping time 13.
%C A177789 Theorem: a(n) can be evaluated using a directed rooted tree produced by a precise algorithm. Each node of this tree is given by a unique Diophantine equation whose only positive solutions are the integers with a finite stopping time. The algorithm generates (in a three step loop) the parity vectors which define the Diophantine equations. The two directions of the construction principle gives the tree a triangular form which extends ever more downwards with each column. There exist explicit arithmetic relationships between the parent and child vertices. As a consequence, a(n) can be generated algorithmically. The algorithm also generates A100982. - _Mike Winkler_, Sep 12 2017
%H A177789 Michael De Vlieger, <a href="/A177789/b177789.txt">Table of n, a(n) for n = 0..12448</a> (rows n = 0..13, flattened)
%H A177789 Michael De Vlieger, <a href="/A177789/a177789_1.txt">Mathematica program that memoizes A060445</a>.
%H A177789 Lynn E. Garner, <a href="https://doi.org/10.1090/S0002-9939-1981-0603593-2">On the Collatz 3n + 1 Algorithm</a>, Proc. Amer. Math. Soc., Vol. 82(1981), 19-22.
%H A177789 Ruud H.G. van Tol, <a href="/A177789/a177789.txt">Perl code</a>
%H A177789 Mike Winkler, <a href="http://mikewinkler.co.nf/collatz_algorithm.pdf">On a stopping time algorithm of the 3n + 1 function</a>
%H A177789 Mike Winkler, <a href="http://arxiv.org/abs/1412.0519">On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence</a>, arXiv:1412.0519 [math.GM], 2014.
%H A177789 Mike Winkler, <a href="http://arxiv.org/abs/1504.00212">New results on the stopping time behaviour of the Collatz 3x + 1 function</a>, arXiv:1504.00212 [math.GM], 2015.
%H A177789 Mike Winkler, <a href="http://arxiv.org/abs/1709.03385">The algorithmic structure of the finite stopping time behavior of the 3x + 1 function</a>, arXiv:1709.03385 [math.GM], 2017.
%e A177789 Triangle begins:
%e A177789    0;
%e A177789    1;
%e A177789    3;
%e A177789   11,  23;
%e A177789    7,  15,  59;
%e A177789   39,  79,  95, 123, 175, 199, 219;
%e A177789   ...
%e A177789 From _Mike Winkler_, Sep 12 2017: (Start)
%e A177789 The beginning of the directed rooted tree produced by the algorithm of the Theorem. The triangular form can be seen clearly. The way the tree structure is sorting a(n), respectively the residue classes, mirrors the explicit arithmetic relationships mentioned in the Theorem.
%e A177789 3 (mod 2^4) -- 11 (mod 2^5) -- 59 (mod 2^7) -- 123 (mod 2^8) --
%e A177789                     |                                |
%e A177789                     |                          219 (mod 2^8) --
%e A177789                     |
%e A177789                     |
%e A177789                23 (mod 2^5) --- 7 (mod 2^7) -- 199 (mod 2^8) --
%e A177789                                     |                |
%e A177789                                     |           39 (mod 2^8) --
%e A177789                                     |
%e A177789                                     |
%e A177789                                15 (mod 2^7) --- 79 (mod 2^8) --
%e A177789                                                      |
%e A177789                                                175 (mod 2^8) --
%e A177789                                                      |
%e A177789                                                 95 (mod 2^8) --
%e A177789 (End)
%t A177789 DroppingTime[n_] := Module[{m=n, k=0}, If[n>1, While[m>=n, k++; If[EvenQ[m], m=m/2, m=3*m+1]]]; k]; dt=Floor[1+Range[0,20]*Log[2,6]]; e=Floor[1+Range[0,20]*Log[2,3]]; Join[{0,1}, Flatten[Table[Select[Range[3,2^e[[n]],2], DroppingTime[ # ]==dt[[n]] &], {n,2,8}]]]
%o A177789 (PARI) /* algorithm for generating the parity vectors of the Theorem, the tree structure is given by the three STEP's */
%o A177789 {k=3; Log32=log(3)/log(2); limit=14; /*or limit>14*/ T=matrix(limit,60000); xn=3; /*initial tuple for n=1*/ A=[]; for(i=1, 2, A=concat(A,i)); A[1]=1; A[2]=1; T[1,1]=A; for(n=2, limit, print("n="n); Sigma=floor(1+(n+1)*Log32); d=floor(n*Log32)-floor((n-1)*Log32); Kappa=floor(n*Log32); Kappa2=floor((n-1)*Log32);r=1; v=1; until(w==0, A=[]; for(i=1, Kappa2+1, A=concat(A,i)); A=T[n-1,v]; B=[]; for(i=1, Kappa+1, B=concat(B,i)); for(i=1, Kappa2+1, B[i]=A[i]); /* STEP 1 */ if(d==1, B[k]=1; T[n,r]=B; r++; v++); if(d==2, B[k]=0; B[k+1]=1; T[n,r]=B; r++; v++); /* STEP 2 */ if(B[Kappa]==0, for(j=1, Kappa-n, B[Kappa+1-j]=B[Kappa+2-j]; B[Kappa+2-j]=0; T[n,r]=B; r++; if(B[Kappa-j]==1, break(1)))); /* STEP 3 */ w=0; for(i=n+2, Kappa+1, w=w+B[i]));k=k+d; p=1; h2=3; for(i=1, r-1, h=0; B=T[n,i]; until(B[h]==0, h++); if(h>h2, p=1; h2++; print); print(T[n,i]"  "p"  "i); p++); print)} \\ _Mike Winkler_, Sep 12 2017
%o A177789 (PARI) row(n) = if (n < 2, [n], my(v = vector(2^(A020914(n)-1), k, 2*k-1)); apply(x->2*x-1, Vec(select(x->(x == 1+A122437(n+1)), apply(A074473, v), 1)))); \\ _Michel Marcus_, Aug 15 2025
%o A177789 (PARI)
%o A177789 row(n)={if(n<1, [0], my(r=[1], d=[2], km=2); for(i=1, n-1, my(temp1=[], temp2=[], c=if(3^(i+1)<2^(km+1),1,2)); for(j=1, #d, temp1=concat(temp1, vector(d[j]-1, m, 3*r[j]+2^(km-d[j]+m))); temp2=concat(temp2, vector(d[j]-1, m, d[j]-m+c))); km=km+c; r=temp1; d=temp2; ); vecsort(apply(x->((-x)*lift(Mod(1/3^n, 2^km)))%2^km, r)))} \\ _V. Barbera_, Aug 15 2025
%Y A177789 Cf. A060445 (dropping time of odd numbers), A100982.
%K A177789 nonn,tabf,changed
%O A177789 0,3
%A A177789 _T. D. Noe_, May 13 2010