A347839 -id:A347839 - cp's OEIS frontend

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

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

Offset: 1

Wolfdieter Lang, Sep 20 2021

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.

			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).
----------------------------------------------------------------------------

Paolo Xausa, Table of n, a(n) for n = 1..11325 (first 150 antidiagonals, flattened).
Immo O. Kerner, Elementarer Lösungsansatz zum Collatz-Ulam-Problem CUP oder das "3a + 1" Problem, Version Nov 26 2000.
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

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), ...
Column sequences of the array A, also of the triangle T (shifted): A047529, A347836, A347837, ...
Cf. A004770, A007494, A016777, A065883, A047395, A047529, A178415, A238475, A256598, A265667, A319451, A347839, A347840.

# 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;
# Peter Luschny, Oct 09 2021

A347834[k_, n_] := (4^n*(6*(Floor[k/3] + k) - 2) - 1)/3;
Table[A347834[k - n, n], {k, 10}, {n, 0, k - 1}] (* Paolo Xausa, Jun 26 2025 *)

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.
A(k, n) = [x^n] (1/(x - 1) - A047395(k)) / (4*x - 1). - Peter Luschny, Oct 09 2021

A347840 A surjective map of the positive numbers congruent to 5 modulo 8 (A004770) to the positive numbers congruent to 1, 3, or 7 modulo 8 (A047529).

Original entry on oeis.org

1, 3, 1, 7, 9, 11, 3, 15, 17, 19, 1, 23, 25, 27, 7, 31, 33, 35, 9, 39, 41, 43, 11, 47, 49, 51, 3, 55, 57, 59, 15, 63, 65, 67, 17, 71, 73, 75, 19, 79, 81, 83, 1, 87, 89, 91, 23, 95, 97, 99, 25, 103, 105, 107, 27, 111, 113, 115, 7, 119, 121

Offset: 1

Wolfdieter Lang, Oct 30 2021

This map is obtained from the array A(k, m) given in A347834. There all positive numbers congruent to 5 modulo 8 (A004770) appear uniquely in the columns for m >= 1, and the m = 0 column gives all numbers congruent to {1, 3, 7} (mod 8) (A047529). The surjective map is f: A004770 -> A047529, with b(n) = A004770(n) -> f(b(n)) = a(n).
See also the array A178415 which has permuted rows.
This maps all entries of each row k of the array A(k, m), given in A347834, with columns m >= 1 to the entry A(k, 0) = A047529(k), for k >= 1. The numbers b(n) appear once in the array A for columns m >= 1. Column A(k, 1) = A347836(k) gives the numbers congruent to {5, 32, 29} (mod 32), and each entry for columns m >= 2 is congruent to 21 (mod 32).
The surjective map of the numbers b(n) = 5 + 8*(n-1) = A004770(n), for n >= 1, to A047529 with element a(n), is computed by switching to the companion array A347839 of A347834, with the simple recurrence, removing all factors of 4, and then going back to array A347834. See the formula below. Thanks to Antti Karttunen for motivating me to simplify the prescription, and to add in A347834 the hint for the induction proof that all 5 (mod 8) numbers appear once in the columns n >= 1.
This map f is of interest in the context of the Collatz 3*n+1 conjecture. The (modified) rooted tree with only odd labeled nodes has for each row k of the array A(k, m) (A347834) the same precursor (or (modified) Collatz map given in A075677(n+1), for 2*n+1). Therefore, all nodes with labels b(n) == 5 (mod 8) can be represented by a(n). This leads to a further restricted Collatz tree with only node labels congruent to {1, 3, 7} (mod 8) (A047529).
An even further restricted Collatz tree has only node labels congruent to 1 (mod 8) (A017077), as any positive integer can be written as m*2^(v+1)+2^v-1 or (m,v) where v is the number of trailing 1-bits in binary, and for v > 1 the next odd Collatz successor of (m,v) is (3*m+1,v-1). - Ruud H.G. van Tol, Sep 13 2023

			The sequence a(n) begins: (b(n) = A004770(n))
-------------------------------------------------------------------------
n:     1  2  3  4  5  6  7  8  9 10 11 12  13  14  15  16  17  18  19  20
b(n):  5 13 21 29 37 45 53 61 69 77 85 93 101 109 117 125 133 141 149 157
a(n):  1  3  1  7  9 11  3 15 17 19  1 23  25  27   7  31  35  35   9  39
-------------------------------------------------------------------------
n:     21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37 ...
b(n): 165 173 181 189 197 205 213 221 229 237 245 253 261 269 277 285 293 ...
a(n):  41  43  11  47  49  51   3  55  57  59  15  63  65  67  17  71  73 ...
-----------------------------------------------------------------------------
n = 6, b(6) = 45 = 13 + 32*1, case a), a(6) = 3 + 8*1 = 11.
n = 7, b(7) = 53 = 21 + 32*1, case b)1), first instance, L(7) = 0, a(7) = 3 + 8*0 = 3.
n = 31, b(31) = 245 = 117 + 128*1, case b)1), second instance, L(31) = 1, a(31) = 7 + 8*1 = 15.
n = 11, b(11) = 85 = 21 + 64*1, A065883(1 + 3*1) = 1, c(11) = 1, case b)2)i), a(11) = 85 = A347834(1, 3).
n = 19, b(19) = 149 = 21 + 64*2, A065883(1 + 3*2) = 7, c(19) = (7 - 1)/3 = 2, case b)2)ii), a(n) = 4*2 + 1 = 9.

Paolo Xausa, Table of n, a(n) for n = 1..10000

Cf. A004770, A047529, A075677, A178415, A347834, A347836, A349414.

A347840[n_] := NestWhile[Quotient[#, 4] &, 2*n - 1, Mod[#, 8] == 5 &];
Array[A347840, 100] (* Paolo Xausa, Jun 25 2025 *)

a(n) = n=2*n-1; while(5==n%8, n>>=2); n; \\ Ruud H.G. van Tol, Sep 13 2023

a(n) = (2*n-1)>>(valuation(3*n-1,2)\2*2); \\ Ruud H.G. van Tol, Sep 20 2023

a(n) = (2*A065883((3*b(n)+1)/2) - 1)/3, with b(n) = A004770(n), for n >= 1.

a(n) = A385109(8*(n-1)+5). - Ralf Stephan, Jun 18 2025

A347838 Positive numbers that are congruent to 2, 5, or 11 modulo 12.

Original entry on oeis.org

2, 5, 11, 14, 17, 23, 26, 29, 35, 38, 41, 47, 50, 53, 59, 62, 65, 71, 74, 77, 83, 86, 89, 95, 98, 101, 107, 110, 113, 119, 122, 125, 131, 134, 137, 143, 146, 149, 155, 158, 161, 167, 170, 173, 179, 182, 185, 191, 194, 197, 203, 206, 209, 215, 218, 221, 227, 230, 233, 239

Offset: 1

Wolfdieter Lang, Oct 21 2021

This sequence follows from the first column sequence of the array A347834, namely A047529 ({1,3,7} (mod 8)), as given in the formula below.

Together with A017617, the positive integers congruent to 8 modulo 12, one obtains A016789, the positive integers congruent to 2 modulo 3. See the array A347839.

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. A002264, A016921, A016789, A017617, A017653, A040117(k+1), A047261, A047529, A102283, A347834, A347839.

Map[(3 # + 1)/2 &, LinearRecurrence[{1, 0, 1, -1}, {1, 3, 7, 9}, 60]] (* Michael De Vlieger, Oct 21 2021 *)

a(n) = (3*A047529(n) + 1)/2.
Trisection: a(3*k+1) = 2 + 12*k, a(3*k+2) = 5 + 12*k, a(3*k+3) = 11 + 12*k, or with a(3*k) = -1 + 12*k for k >= 0.
O.g.f. with a(0) =-1: G(x) = (-1 + 3*x + 3*x^2 + 7*x^3)/((1 - x)*(1 - x^3)) = -6/(1-x) + 4/(1-x)^2 + (1 + x)/(1 + x + x^2). Note that (1 - x)*(1 - x^3) = (1-x)^2*(1 + x + x^2) =  1 - x - x^3 + x^4.
a(n) = a(n-1) + a(n-3) - a(n-4), for n >= 4, given a(n) for 0..3, with a(0) = -1.
a(n) = 2*b(n) + 3*b(n-1) + 6*b(n-2) + b(n-3), with b(n) = floor((n+2)/3) = A002264(n+2).
a(n) = -1 + 3*n + 3*floor(n/3) (from the partial fraction decomposition of G).
E.g.f.: 1 + 2*exp(x)*(2*x - 1) + exp(-x/2)*(3*cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2))/3. - Stefano Spezia, Dec 08 2021
Sum_{n>=1} (-1)^(n+1)/a(n) = ((sqrt(2)+1)*Pi + sqrt(3)*log(sqrt(3)+2) + sqrt(6)*log(5-2*sqrt(6)))/12. - Amiram Eldar, Dec 30 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A347840 A surjective map of the positive numbers congruent to 5 modulo 8 (A004770) to the positive numbers congruent to 1, 3, or 7 modulo 8 (A047529).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A347838 Positive numbers that are congruent to 2, 5, or 11 modulo 12.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula