login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177789 Irregular triangle 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. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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). The triangle means:

numbers 0 (mod 2) and >0 have dropping time 1

numbers 1 (mod 4) and >1 have dropping time 3

numbers 3 (mod 16) have dropping time 6

numbers 11, 23 (mod 32) have dropping time 8

numbers 7, 15, 59 (mod 128) have dropping time 11

numbers 39, 79, 95, 123, 175, 199, 219 (mod 256) have dropping time 13

The encoding (in the A176999 sequence fashion) of integers of equal dropping time, classified as planes of a Pascal trihedron, leads to two geographies, each one with specific properties and anticipations of integers of plane v+1 from plane v. (See also A100982.) - Hubert Schaetzel, Aug 24 2017

Theorem 1: a(n) can be evaluated using to 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 steps 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

LINKS

Table of n, a(n) for n=0..50.

Lynn E. Garner, On the Collatz 3n + 1 Algorithm, Proc. Amer. Math. Soc., Vol. 82(1981), 19-22.

H. Schaetzel, Collatz conjecture: Geography of the Pascal trihedron, 2017.

M. Winkler, On a stopping time algorithm of the 3n+ 1 function

M. Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences, 2014.

M. Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.

M. Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

EXAMPLE

Triangle begins:

   0;

   1;

   3;

  11,  23;

   7,  15,  59;

  39,  79,  95, 123, 175, 199, 219;

  ...

The beginning of the directed rooted tree produced by the algorithm of Theorem 1. The triangular form can be seen clearly. The way the tree structure is sorting a(n), respectively the residue classes, mirrors the explicit arithmetic rules mentioned in theorem 1.

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) --

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}]]]

PROG

(PARI) /* algorithm for generating the parity vectors of theorem 1, the tree structure ist 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

CROSSREFS

Cf. A060445 (dropping time of odd numbers), A100982.

Sequence in context: A121471 A178946 A087078 * A289526 A289765 A141226

Adjacent sequences:  A177786 A177787 A177788 * A177790 A177791 A177792

KEYWORD

nonn,tabf,changed

AUTHOR

T. D. Noe, May 13 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 17:29 EDT 2017. Contains 292432 sequences.