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.
0, 1, 3, 11, 23, 7, 15, 59, 39, 79, 95, 123, 175, 199, 219, 287, 347, 367, 423, 507, 575, 583, 735, 815, 923, 975, 999, 231, 383, 463, 615, 879, 935, 1019, 1087, 1231, 1435, 1647, 1703, 1787, 1823, 1855, 2031, 2203, 2239, 2351, 2587, 2591, 2907, 2975, 3119
Offset: 0
Examples
Triangle begins:
0;
1;
3;
11, 23;
7, 15, 59;
39, 79, 95, 123, 175, 199, 219;
...
From _Mike Winkler_, Sep 12 2017: (Start)
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.
3 (mod 2^4) -- 11 (mod 2^5) -- 59 (mod 2^7) -- 123 (mod 2^8) --
| |
| 219 (mod 2^8) --
|
|
23 (mod 2^5) --- 7 (mod 2^7) -- 199 (mod 2^8) --
| |
| 39 (mod 2^8) --
|
|
15 (mod 2^7) --- 79 (mod 2^8) --
|
175 (mod 2^8) --
|
95 (mod 2^8) --
(End)
Links
- Michael De Vlieger, Table of n, a(n) for n = 0..12448 (rows n = 0..13, flattened)
- Michael De Vlieger, Mathematica program that memoizes A060445.
- Lynn E. Garner, On the Collatz 3n + 1 Algorithm, Proc. Amer. Math. Soc., Vol. 82(1981), 19-22.
- Ruud H.G. van Tol, Perl code
- Mike Winkler, On a stopping time algorithm of the 3n + 1 function
- Mike Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], 2014.
- Mike Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.
- Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.
Programs
-
Mathematica
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}]]] -
PARI
/* algorithm for generating the parity vectors of the Theorem, the tree structure is given by the three STEP's */ {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 -
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
-
PARI
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
Comments