|
| |
|
|
A347834
|
|
An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.
|
|
19
|
|
|
|
1, 3, 5, 7, 13, 21, 9, 29, 53, 85, 11, 37, 117, 213, 341, 15, 45, 149, 469, 853, 1365, 17, 61, 181, 597, 1877, 3413, 5461, 19, 69, 245, 725, 2389, 7509, 13653, 21845, 23, 77, 277, 981, 2901, 9557, 30037, 54613, 87381, 25, 93, 309, 1109, 3925, 11605, 38229, 120149, 218453, 349525
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For the definition of this array A see the formula section.
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.
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.
A proper sub-array is A238475(n, k) = A(1 + 3*(k-1), n-1), for k >= 1 and n >= 1.
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.
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.
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.
Except for the loop (1-cycle) for the root 1 there are no cycles in this directed tree CTodd.
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]
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]
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Array A:
A(k, 0) = A047529(k) (the positive odd numbers {1, 3, 7} (mod 8));
A(k, n) = ((3* A(k, 0) + 1)*4^n - 1)/3, for k >= 1 and n >= 0.
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).
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).
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.
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.
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)).
Triangle T:
T(k, n) = A(k - n, n), for k >= 1 and n = 0..k-1.
|
|
|
EXAMPLE
|
The array A(k, n) begins:
k\n 0 1 2 3 4 5 6 7 8 9 10 ...
-------------------------------------------------------------------------
1: 1 5 21 85 341 1365 5461 21845 87381 349525 1398101
2: 3 13 53 213 853 3413 13653 54613 218453 873813 3495253
3: 7 29 117 469 1877 7509 30037 120149 480597 1922389 7689557
4: 9 37 149 597 2389 9557 38229 152917 611669 2446677 9786709
5: 11 45 181 725 2901 11605 46421 185685 742741 2970965 11883861
6: 15 61 245 981 3925 15701 62805 251221 1004885 4019541 16078165
7: 17 69 277 1109 4437 17749 70997 283989 1135957 4543829 18175317
8: 19 77 309 1237 4949 19797 79189 316757 1267029 5068117 20272469
9: 23 93 373 1493 5973 23893 95573 382293 1529173 6116693 24466773
10: 25 101 405 1621 6485 25941 103765 415061 1660245 6640981 26563925
...
--------------------------------------------------------------------
The triangle T(k, n) begins:
k\n 0 1 2 3 4 5 6 7 8 9 ...
------------------------------------------------------------
1: 1
2: 3 5
3: 7 13 21
4: 9 29 53 85
5: 11 37 117 213 341
6: 15 45 149 469 853 1365
7: 17 61 181 597 1877 3413 5461
8: 19 69 245 725 2389 7509 13653 21845
9: 23 77 277 981 2901 9557 30037 54613 87381
10: 25 93 309 1109 3925 11605 38229 120149 218453 349525
...
-------------------------------------------------------------
Row index k of array A, for entries 5 (mod 8).
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).
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).
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).
----------------------------------------------------------------------------
|
|
|
MAPLE
|
# Seen as an array:
A := (n, k) -> ((3*(n + floor(n/3)) - 1)*4^(k+1) - 2)/6:
for n from 1 to 6 do seq(A(n, k), k = 0..9) od;
# Seen as a triangle:
T := (n, k) -> 2^(2*k + 1)*(floor((n - k)/3) - k + n - 1/3) - 1/3:
for n from 1 to 9 do seq(T(n, k), k = 0..n-1) od;
# Using row expansion:
gf_row := k -> (1 / (x - 1) - A047395(k)) / (4*x - 1):
for k from 1 to 10 do seq(coeff(series(gf_row(k), x, 11), x, n), n = 0..10) od;
|
|
|
CROSSREFS
|
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), ...
Cf. A004770, A007494, A016777, A065883, A047395, A047529, A178415, A238475, A256598, A265667, A319451, A347839, A347840.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
