|
%I #53 Oct 13 2023 06:49:32
%S 1,3,5,7,13,21,9,29,53,85,11,37,117,213,341,15,45,149,469,853,1365,17,
%T 61,181,597,1877,3413,5461,19,69,245,725,2389,7509,13653,21845,23,77,
%U 277,981,2901,9557,30037,54613,87381,25,93,309,1109,3925,11605,38229,120149,218453,349525
%N An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.
%C For the definition of this array A see the formula section.
%C The rows of A appear in a draft by Immmo O. Kerner in eqs. (1) and (2) as so-called horizontal sequences (horizontale Folgen). Thanks to Dr. A. Eckert for sending me this paper.
%C This array with entry A(k, n) becomes equal to the array T with T(n, k) given in A178415 by using a permutation of the rows, and changing the offset: A(k, n) = T(pe(k), n+1), with pe(3*(L+1)) = 4*(L+1), pe(1+3*L) = 1 + 2*L, pe(2+3*L) = 2*(1 + 2*L), for L >= 0. This permutation appears in A265667.
%C A proper sub-array is A238475(n, k) = A(1 + 3*(k-1), n-1), for k >= 1 and n >= 1.
%C In the directed Collatz tree with nodes labeled with only positive odd numbers (see A256598 for the paths), here called CTodd, the level L = 0 (on the top) has the node with label 1 as root. Because 1 -> 1 there is an arrow (a 1-cycle or loop) at the root. The level L = 1 consists of the nodes with labels A(1, n), for n >= 1, and each node is connected to 1 by a downwards directed arrow. The next levels for L >= 2 are obtained using the successor rule (used also by Kerner): S(u) = (4*u - 1)/3 if u == 1 (mod 3), (2*u - 1)/3 if u == 5 (mod 3), and there is no successor S(u) = empty if u = 3 (mod 6), that is, this node is a leaf.
%C However, each node with label u on level L >= 1, except a leaf, has as successors at level L + 1 not only the node with S(u) but all the nodes with labels A(S(u), n), for n >= 0.
%C In this way each node (also the root) of this CTodd has in-degree 1 and infinite out-degree (for L >= 2 there are infinitely many infinite outgoing arrows). All nodes with label A(k, n) with n >= 1, have the same precursor as the node A(k,0) in this tree for each k >= 1.
%C Except for the loop (1-cycle) for the root 1 there are no cycles in this directed tree CTodd.
%C That each number N = 5 + 8*K, for K >= 0 appears in array A for some column n >= 1 uniquely can be proved, using the fact of strictly increasing rows and columns, by showing that the columns n = 1, 2, ..., c contain all positive integers congruent to 5 modulo 8 except those of the positive congruence class A(1, c+1) modulo 2^(2*c+3) by induction on c. [added Dec 05 2021]
%C Row index k for numbers congruent to 5 modulo 8: Each number N = 5 + 8*K, for K >= 0, from A004770 is a member of row k of the array A starting with element A(k, 0) = (2*A065883(2 + 3*N) - 1)/3. For this surjective map see A347840. [simplified Dec 05 2021]
%C The Collatz conjecture can be reduced to the conjecture that in this rooted and directed tree CTodd each positive odd number appears as a label once, that is, all entries of the array A appear.
%H Immo O. Kerner, <a href="https://web.archive.org/web/20070712034904/www.inf.hs-zigr.de/~wagenkn/CUP3AP1-neu.pdf">Elementarer Lösungsansatz zum Collatz-Ulam-Problem CUP oder das "3a + 1" Problem</a>, Version Nov 26 2000.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F Array A:
%F A(k, 0) = A047529(k) (the positive odd numbers {1, 3, 7} (mod 8));
%F A(k, n) = ((3* A(k, 0) + 1)*4^n - 1)/3, for k >= 1 and n >= 0.
%F Recurrence for rows k >= 1: A(k, n) = 4*A(k, n-1) + 1, for n >= 1, with A(k, 0) = 2*(k + floor(k/3)) - 1 = A047529(k).
%F Explicit form: A(k, n) = ((3*(k + floor(k/3)) - 1)*4^(n+1) - 2)/6, k >= 1, n >= 0. Here 3*(k + floor(k/3)) = A319451(k).
%F Hence A(k, n) = 5 + 8*(2*A(k, n-2)), for n >= 1, with A(k, 0) = 2*(k + floor(k/3)) - 1 = A047529(k), and 2*A(k, -1) = (A(k, 1) - 5)/8 = k - 1 + floor(k/3) (equals index n of A(k, 1) in the sequence (A004770(n+1))_{n >= 0}). A(k, -1) is half-integer if k = A007494(m) = m + ceiling(m/2), for m >= 1, and A(k, -1) = 2*K if k = 1 + 3*K = A016777(K), for K >= 0.
%F O.g.f.: expansion in z gives o.g.f.s for rows k, also for k = 0: -A007583; expansion in x gives o.g.f.s for columns n.
%F G(z, x) = (2*(-1 + 3*z + 3*z^2 + 7*z^3)*(1-x) - (1-4*x)*(1-z^3)) / (3*(1-x)*(1-4*x)*(1-z)*(1-z^3)).
%F Triangle T:
%F T(k, n) = A(k - n, n), for k >= 1 and n = 0..k-1.
%F A(k, n) = [x^n] (1/(x - 1) - A047395(k)) / (4*x - 1). - _Peter Luschny_, Oct 09 2021
%e The array A(k, n) begins:
%e k\n 0 1 2 3 4 5 6 7 8 9 10 ...
%e -------------------------------------------------------------------------
%e 1: 1 5 21 85 341 1365 5461 21845 87381 349525 1398101
%e 2: 3 13 53 213 853 3413 13653 54613 218453 873813 3495253
%e 3: 7 29 117 469 1877 7509 30037 120149 480597 1922389 7689557
%e 4: 9 37 149 597 2389 9557 38229 152917 611669 2446677 9786709
%e 5: 11 45 181 725 2901 11605 46421 185685 742741 2970965 11883861
%e 6: 15 61 245 981 3925 15701 62805 251221 1004885 4019541 16078165
%e 7: 17 69 277 1109 4437 17749 70997 283989 1135957 4543829 18175317
%e 8: 19 77 309 1237 4949 19797 79189 316757 1267029 5068117 20272469
%e 9: 23 93 373 1493 5973 23893 95573 382293 1529173 6116693 24466773
%e 10: 25 101 405 1621 6485 25941 103765 415061 1660245 6640981 26563925
%e ...
%e --------------------------------------------------------------------
%e The triangle T(k, n) begins:
%e k\n 0 1 2 3 4 5 6 7 8 9 ...
%e ------------------------------------------------------------
%e 1: 1
%e 2: 3 5
%e 3: 7 13 21
%e 4: 9 29 53 85
%e 5: 11 37 117 213 341
%e 6: 15 45 149 469 853 1365
%e 7: 17 61 181 597 1877 3413 5461
%e 8: 19 69 245 725 2389 7509 13653 21845
%e 9: 23 77 277 981 2901 9557 30037 54613 87381
%e 10: 25 93 309 1109 3925 11605 38229 120149 218453 349525
%e ...
%e -------------------------------------------------------------
%e Row index k of array A, for entries 5 (mod 8).
%e 213 = 5 + 8*26. K = 28 is even, (3*231+1)/16 = 40, A065883(40) = 10, hence A(k, 0) = N' = (10-1)/3 = 3, and k = 2. Moreover, n = log_4((3*213 + 1)/(3*A(2,0) + 1)) = log_4(64) = 3. 213 = A(2, 3).
%e 85 = 5 + 8*10. K = 10 is even, (3*85 + 1)/16 = 16, A065883(16) = 1, N' = (1-1)/3 = 0 is even, hence A(k, 0) = 4*0 + 1 = 1, k = 1. 85 = A(1, 3).
%e 61 = 5 + 8*7, K = 7 is odd, k = (7+1)/2 + ceiling((7+1)/4) = 6, and n = log_4((3*61 + 1)/(3*A(6,0) + 1)) = 1. 61 = A(6, 1).
%e ----------------------------------------------------------------------------
%p # Seen as an array:
%p A := (n, k) -> ((3*(n + floor(n/3)) - 1)*4^(k+1) - 2)/6:
%p for n from 1 to 6 do seq(A(n, k), k = 0..9) od;
%p # Seen as a triangle:
%p T := (n, k) -> 2^(2*k + 1)*(floor((n - k)/3) - k + n - 1/3) - 1/3:
%p for n from 1 to 9 do seq(T(n, k), k = 0..n-1) od;
%p # Using row expansion:
%p gf_row := k -> (1 / (x - 1) - A047395(k)) / (4*x - 1):
%p for k from 1 to 10 do seq(coeff(series(gf_row(k), x, 11), x, n), n = 0..10) od;
%p # _Peter Luschny_, Oct 09 2021
%Y Row sequences of the array A, also diagonal sequences of the triangle T: -A007583 (k=0), A002450(n+1), A072197, A072261(n+1), A206374(n+1), A072262(n+1), A072262(n+1), A072201(n+1), A330246(n+1), ...
%Y Column sequences of the array A, also of the triangle T (shifted): A047529, A347836, A347837, ...
%Y Cf. A004770, A007494, A016777, A065883, A047395, A047529, A178415, A238475, A256598, A265667, A319451, A347839, A347840.
%K nonn,tabl,easy
%O 1,2
%A _Wolfdieter Lang_, Sep 20 2021
|
