A395428 Square matrix where the n-th row lists the odd numbers which take n steps to reach 1 under the reduced Collatz map R: x -> A000265(3x+1), read by falling antidiagonals.

5, 21, 3, 85, 13, 17, 341, 53, 35, 11, 1365, 113, 69, 23, 7, 5461, 213, 75, 45, 15, 9, 21845, 227, 141, 93, 29, 19, 25, 87381, 453, 151, 181, 61, 37, 49, 33, 349525, 853, 277, 201, 117, 77, 51, 65, 43, 1398101, 909, 301, 369, 241, 81, 99, 67, 87, 57, 5592405, 1813, 565, 373, 245, 149, 101

Offset

1,1

Comments

We consider the reduced Collatz map R: x -> A000265(3x+1) = (3x+1)/2^A007814(3x+1), the odd part of 3x+1; i.e., all factors of 2 are immediately divided out. The map R is only defined on the odd integers, it can be expressed as A075677 o A110654 = A139391 restricted to the odd numbers A005408.

This partitions the odd integers into "convergence classes", corresponding to the number of steps A006667(x) = A075680((x-1)/2) needed to reach 1 under iterations of R.

The number 1 itself would be in class / row 0, but since this would be the only row with only one element, we omit it in this table.

Links

Table of n, a(n) for n=1..62.

M. F. Hasler, Interactive "Reverse Collatz Tree" visualization, GitHub page, April 2026.

Formula

T(n,k) is the k-th odd integer m for which A006667(m) = n.

T(n,k) = A005408(j-1) = 2j-1, where j is the index of the k-th occurrence of n in A075680.

Example

The ("reverse") Collatz graph looks as follows (see link for nicer graphics):
1 <- 2 <- 4 <- 8 <- 16 <- 32 <- 64 <- 128 <- ...
 `--------^          ^           ^--- 21 <- 42 <- 84 <- ...
                      `--- 5 <- 10 <- 20 <- 40 <- 80 <- ...
                                 ^           ^--- 13 <- 26 <- ...
                                  `--- 3 <- 6 <- ...
so the numbers 5, 21, 85, ... (cf. A002450) take one step under R = A075677 (which "collapses" the divisions by 2) to reach 1, the numbers 3, 13, 53, ... (cf. A198584) take two steps, etc.
The array starts as follows:
  row number | odd integers that take n steps to reach 1
  -----------+------------------------------------------
     n = 1   |   5, 21, 85, 341, 1365, ... = A002450(2..)
     n = 2   |   3, 13, 53, 113, 213, 227, ... = A198584
     n = 3   |  17, 35, 69,  75, 141, 151, ... = A198587
     n = 4   |  11, 23, 45,  93, 181, 201, ... = A198588
     n = 5   |   7, 15, 29,  61, 117, 241, ... = A198589
     n = 6   |   9, 19, 37,  77,  81, 149, ... = A198590
     n = 7   |  25, 49, 51,  99, 101, 197, ... = A198591
     n = 8   |  33, 65, 67, 131, 133, 261, ... = A198592
     n = 9   |  43, 87, 89, 173, 177, 179, ... = A198593

Prog

(Python)
def A395428(n, k=0): # Return a(n) if k=0, else T(n, k). n=0 yields A075680(k).
    if k==0: d = round((n*2)**.5); n -= d*(d-1)//2; return A395428(n, d-n+1)
    if n<2: return 4**k*4//3 if n else R[k] if k in (R:=A395428.R) else 1 if(
       t:=k*3+1).bit_count()==1 else R.setdefault(k, A395428(0, t//(t&-t))+1)
    if len(r := A395428.row.setdefault(n, [])) < k: # row must be extended
        N = A395428.N; row = A395428.row
        while len(r) < k:
            while (N*3+1).bit_count()==1: N+=2
            row.setdefault(A395428(0, N), []).append(N); N+=2
        A395428.N = N
    return r[k-1]
A395428.R={}; A395428.row={}; A395428.N=3

Crossrefs

Cf. A007814 (2-valuation), A002450 ((4^n-1)/3 ~ row 1), A198584 - A198593 (rows 2 through 9).

Cf. A006370 (Collatz 3x+1 map), A014682 (Collatz with (3x+1)/2), A075677 (reduced Collatz map for odd integers), A139391 (next odd term under iterated 3x+1 or (3x+1)/2 map).

Cf. A006667 (number of 3x+1 steps to reach 1), A075680 (bisection, for odd n).

Cf. A000265 (odd part), A007814 (2-valuation), A005408 (odd numbers), A110654 (round(n/2), gives the index of any odd n in A005408).

Sequence in context: A156824 A053002 A053003 * A373163 A346035 A167202

Adjacent sequences: A395425 A395426 A395427 * A395429 A395430 A395431

Keyword

nonn,tabl

Author

M. F. Hasler, Apr 22 2026

Status

approved