|
| |
|
|
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.
|
|
5
|
|
|
|
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.
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
|
|
|
LINKS
|
|
|
|
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 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)
|
|
|
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 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
