login
Irregular triangle T read by rows: T(n, k) = (A324038(n, k) - 1)/2.
4

%I #15 Aug 10 2023 13:13:01

%S 0,2,1,10,6,42,8,26,56,170,5,34,17,106,37,226,113,682,3,22,138,11,70,

%T 426,150,906,75,454,2730,4,14,90,184,554,7,46,282,568,1706,200,602,

%U 1208,3626,100,302,1818,3640,10922,18,9,58,120,362,738,369,2218,30,186,376,1130,2274,1137,6826,133,802,401,2410,805,4834,2417,14506,402,201,1210,2424,7274,14562,7281,43690

%N Irregular triangle T read by rows: T(n, k) = (A324038(n, k) - 1)/2.

%C The length of row n is A324039, for n >= 0.

%C This is the incomplete binary tree corresponding to the modified Collatz map f (from the Vaillant and Delarue link) given in A324245.

%C The branches of this tree, called CfTree, give the iterations under the Vaillant and Delarue map f of the vertex labels of level n until label 0 on level n = 0 is reached.

%C The out-degree of a vertex label T(n, k), for n >= 1, is 1 if T(n, k) == 1 (mod 3) and 2 for all other labels. For level n = 0 with vertex label 0 this rule does not hold, it has out-degree 1, not 2.

%C The number of vertex labels on level n which are 1 (mod 3) is given in A324040.

%C The corresponding tree CfsTree with only odd vertex labels t(n, k) = 2*T(n,k) + 1 is given in A324038.

%C The Collatz conjecture is that all nonnegative integers appear in this CfTree. Because the sets of labels on the levels are pairwise disjoint, these numbers will then appear just once.

%C For this tree see Figure 2 in the Vaillant-Delarue link. It is also shown in the W. Lang link given in A324038.

%H Nicolas Vaillant and Philippe Delarue, <a href="https://web.archive.org/web/20220317020641/http://nini-software.fr/site/uploads/arithmetics/collatz/Intrinsic%203x+1%20V2.01.pdf">The hidden face of the 3x+1 problem. Part I: Intrinsic algorithm</a>, April 26 2019.

%F Recurrence for the set of vertex labels CfTree(n) = {T(n, k), k = 1..A324039(n)} on level (row) n:

%F This set is obtained, with the map f from A324245, from CfTree(0) = {0}, CfTree(1) = {2}, and for n >= 2 CfTree(n) = {m >= 0: f(m) = T(n-1, k), for k = 1.. A324039(n-1)}.

%F Explicit form for the successor of T(n, k) on row (level) n+1, for n >= 1:

%F a label with T(n, k) == 1 (mod 3) produces the label 2*(1 + 2*T(n, k)) on row n+1; label T(n, k) == 0 (mod 3) produces the two labels 4*T(n, k)/3 and 2*(1 + 2*T(n, k)); label T(n, k) == 2 (mod 3) produces the two labels (-1 + 2*T(n, k))/3 and 2*(1 + 2*T(n, k)).

%e The irregular triangle T begins (the brackets combine pairs coming from out-degree 2 vertices of the preceding level):

%e ----------------------------------------------------------

%e n\k 1 2 3 4 5 6 7 8 9 10 11 ...

%e 0: 0

%e 1: 2

%e 2: (1 10)

%e 3: 6 42

%e 4: (8 26) (56 170)

%e 5: (5 34) (17 106) (37 226) (113 682)

%e 6: (3 22) 138 (11 70) 426 150 906 (75 454) 2730

%e ...

%e Row n = 7: (4 14) 90 (184 554) (7 46) 282 (568 1706) (200 602) (1208 3626) (100 302) 1818 (3640 10922);

%e Row n = 8: 18 (9 58) (120 362) 738 (369 2218) 30 186 (376 1130) 2274 (1137 6826) (133 802) (401 2410) (805 4834) (2417 14506) 402 (201 1210) (2424 7274) 14562 (7281 43690).

%e ...

%e The successors of T(1,1) = 2 == 2 (mod 3) are (-1 + 2*2 )/3 = 1 and 2*(1 + 2*2) = 10. The successor of T(2, 1) = 1 == 1 (mod 3) is 2*(1 + 2*1) = 6. The successors of T(3, 1) = 6 == 0 (mod 3) are 4*6/3 = 8 and 2*(1 + 2*6) = 26.

%Y Cf. A248573 (Collatz-Terras tree), A324038 (CfsTree), A324039, A324040, A324245.

%K nonn,tabf,easy

%O 0,2

%A _Nicolas Vaillant_, Philippe Delarue, _Wolfdieter Lang_, May 09 2019