cp's OEIS Frontend

A347834 An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.

%I A347834 #62 Jun 26 2025 07:40:30
%S A347834 1,3,5,7,13,21,9,29,53,85,11,37,117,213,341,15,45,149,469,853,1365,17,
%T A347834 61,181,597,1877,3413,5461,19,69,245,725,2389,7509,13653,21845,23,77,
%U A347834 277,981,2901,9557,30037,54613,87381,25,93,309,1109,3925,11605,38229,120149,218453,349525
%N A347834 An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.
%C A347834 For the definition of this array A see the formula section.
%C A347834 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 A347834 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 A347834 A proper sub-array is A238475(n, k) = A(1 + 3*(k-1), n-1), for k >= 1 and n >= 1.
%C A347834 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 A347834 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 A347834 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 A347834 Except for the loop (1-cycle) for the root 1 there are no cycles in this directed tree CTodd.
%C A347834 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 A347834 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 A347834 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 A347834 Paolo Xausa, <a href="/A347834/b347834.txt">Table of n, a(n) for n = 1..11325</a> (first 150 antidiagonals, flattened).
%H A347834 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 A347834 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>
%H A347834 Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%H A347834 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A347834 Array A:
%F A347834 A(k, 0) = A047529(k) (the positive odd numbers {1, 3, 7} (mod 8));
%F A347834 A(k, n) = ((3* A(k, 0) + 1)*4^n - 1)/3, for k >= 1 and n >= 0.
%F A347834 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 A347834 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 A347834 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 A347834 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 A347834   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 A347834 Triangle T:
%F A347834 T(k, n) = A(k - n, n), for k >= 1 and n = 0..k-1.
%F A347834 A(k, n) = [x^n] (1/(x - 1) - A047395(k)) / (4*x - 1). - _Peter Luschny_, Oct 09 2021
%e A347834 The array A(k, n) begins:
%e A347834 k\n  0   1   2    3    4     5      6      7       8       9       10 ...
%e A347834 -------------------------------------------------------------------------
%e A347834 1:   1   5  21   85  341  1365   5461  21845   87381  349525  1398101
%e A347834 2:   3  13  53  213  853  3413  13653  54613  218453  873813  3495253
%e A347834 3:   7  29 117  469 1877  7509  30037 120149  480597 1922389  7689557
%e A347834 4:   9  37 149  597 2389  9557  38229 152917  611669 2446677  9786709
%e A347834 5:  11  45 181  725 2901 11605  46421 185685  742741 2970965 11883861
%e A347834 6:  15  61 245  981 3925 15701  62805 251221 1004885 4019541 16078165
%e A347834 7:  17  69 277 1109 4437 17749  70997 283989 1135957 4543829 18175317
%e A347834 8:  19  77 309 1237 4949 19797  79189 316757 1267029 5068117 20272469
%e A347834 9:  23  93 373 1493 5973 23893  95573 382293 1529173 6116693 24466773
%e A347834 10: 25 101 405 1621 6485 25941 103765 415061 1660245 6640981 26563925
%e A347834 ...
%e A347834 --------------------------------------------------------------------
%e A347834 The triangle T(k, n) begins:
%e A347834 k\n  0  1   2    3    4     5     6      7      8      9 ...
%e A347834 ------------------------------------------------------------
%e A347834 1:   1
%e A347834 2:   3  5
%e A347834 3:   7 13  21
%e A347834 4:   9 29  53   85
%e A347834 5:  11 37 117  213  341
%e A347834 6:  15 45 149  469 853   1365
%e A347834 7:  17 61 181  597 1877  3413  5461
%e A347834 8:  19 69 245  725 2389  7509 13653  21845
%e A347834 9:  23 77 277  981 2901  9557 30037  54613  87381
%e A347834 10: 25 93 309 1109 3925 11605 38229 120149 218453 349525
%e A347834 ...
%e A347834 -------------------------------------------------------------
%e A347834 Row index k of array A, for entries 5 (mod 8).
%e A347834 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 A347834 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 A347834 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 A347834 ----------------------------------------------------------------------------
%p A347834 # Seen as an array:
%p A347834 A := (n, k) -> ((3*(n + floor(n/3)) - 1)*4^(k+1) - 2)/6:
%p A347834 for n from 1 to 6 do seq(A(n, k), k = 0..9) od;
%p A347834 # Seen as a triangle:
%p A347834 T := (n, k) -> 2^(2*k + 1)*(floor((n - k)/3) - k + n - 1/3) - 1/3:
%p A347834 for n from 1 to 9 do seq(T(n, k), k = 0..n-1) od;
%p A347834 # Using row expansion:
%p A347834 gf_row := k -> (1 / (x - 1) - A047395(k)) / (4*x - 1):
%p A347834 for k from 1 to 10 do seq(coeff(series(gf_row(k), x, 11), x, n), n = 0..10) od;
%p A347834 # _Peter Luschny_, Oct 09 2021
%t A347834 A347834[k_, n_] := (4^n*(6*(Floor[k/3] + k) - 2) - 1)/3;
%t A347834 Table[A347834[k - n, n], {k, 10}, {n, 0, k - 1}] (* _Paolo Xausa_, Jun 26 2025 *)
%Y A347834 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 A347834 Column sequences of the array A, also of the triangle T (shifted): A047529, A347836, A347837, ...
%Y A347834 Cf. A004770, A007494, A016777, A065883, A047395, A047529, A178415, A238475, A256598, A265667, A319451, A347839, A347840.
%K A347834 nonn,tabl,easy
%O A347834 1,2
%A A347834 _Wolfdieter Lang_, Sep 20 2021