A395428 - OEIS

%I #18 May 03 2026 05:34:47

%S 5,21,3,85,13,17,341,53,35,11,1365,113,69,23,7,5461,213,75,45,15,9,

%T 21845,227,141,93,29,19,25,87381,453,151,181,61,37,49,33,349525,853,

%U 277,201,117,77,51,65,43,1398101,909,301,369,241,81,99,67,87,57,5592405,1813,565,373,245,149,101

%N 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.

%C 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.

%C 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.

%C 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.

%H M. F. Hasler, <a href="https://m-f-h.github.io/collatz/">Interactive "Reverse Collatz Tree" visualization</a>, GitHub page, April 2026.

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

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

%e The ("reverse") Collatz graph looks as follows (see link for nicer graphics):

%e 1 <- 2 <- 4 <- 8 <- 16 <- 32 <- 64 <- 128 <- ...

%e  `--------^          ^           ^--- 21 <- 42 <- 84 <- ...

%e                       `--- 5 <- 10 <- 20 <- 40 <- 80 <- ...

%e                                  ^           ^--- 13 <- 26 <- ...

%e                                   `--- 3 <- 6 <- ...

%e 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.

%e The array starts as follows:

%e   row number | odd integers that take n steps to reach 1

%e   -----------+------------------------------------------

%e      n = 1   |   5, 21, 85, 341, 1365, ... = A002450(2..)

%e      n = 2   |   3, 13, 53, 113, 213, 227, ... = A198584

%e      n = 3   |  17, 35, 69,  75, 141, 151, ... = A198587

%e      n = 4   |  11, 23, 45,  93, 181, 201, ... = A198588

%e      n = 5   |   7, 15, 29,  61, 117, 241, ... = A198589

%e      n = 6   |   9, 19, 37,  77,  81, 149, ... = A198590

%e      n = 7   |  25, 49, 51,  99, 101, 197, ... = A198591

%e      n = 8   |  33, 65, 67, 131, 133, 261, ... = A198592

%e      n = 9   |  43, 87, 89, 173, 177, 179, ... = A198593

%o (Python)

%o def A395428(n, k=0): # Return a(n) if k=0, else T(n,k). n=0 yields A075680(k).

%o     if k==0: d = round((n*2)**.5); n -= d*(d-1)//2; return A395428(n,d-n+1)

%o     if n<2: return 4**k*4//3 if n else R[k] if k in (R:=A395428.R) else 1 if(

%o        t:=k*3+1).bit_count()==1 else R.setdefault(k, A395428(0, t//(t&-t))+1)

%o     if len(r := A395428.row.setdefault(n, [])) < k: # row must be extended

%o         N = A395428.N; row = A395428.row

%o         while len(r) < k:

%o             while (N*3+1).bit_count()==1: N+=2

%o             row.setdefault(A395428(0, N), []).append(N); N+=2

%o         A395428.N = N

%o     return r[k-1]

%o A395428.R={}; A395428.row={}; A395428.N=3

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

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

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

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

%K nonn,tabl

%O 1,1

%A _M. F. Hasler_, Apr 22 2026