A139391 Next odd term in Collatz trajectory with starting value n.

1, 1, 5, 1, 1, 3, 11, 1, 7, 5, 17, 3, 5, 7, 23, 1, 13, 9, 29, 5, 1, 11, 35, 3, 19, 13, 41, 7, 11, 15, 47, 1, 25, 17, 53, 9, 7, 19, 59, 5, 31, 21, 65, 11, 17, 23, 71, 3, 37, 25, 77, 13, 5, 27, 83, 7, 43, 29, 89, 15, 23, 31, 95, 1, 49, 33, 101, 17, 13, 35, 107, 9, 55, 37, 113, 19, 29

Offset: 1

Author

Reinhard Zumkeller, Apr 17 2008

Keywords

• nonn
• easy

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Friedrich L. Bauer, Der (ungerade) Collatz-Baum, Informatik Spektrum 31 (Springer, April 2008).
• Eric Weisstein's World of Mathematics, Collatz Problem.
• Wikipedia, Collatz conjecture.
• Index entries for sequences related to 3x+1 (or Collatz) problem.

Crossrefs

Cf. A000265, A006370, A014682, A016825, A160967, A350091.

Cf. A075677 (odd bisection).

Programs

Mathematica

a[n_]:=Select[NestWhileList[If[EvenQ[#],#/2,3#+1] &,n,#>1 &],OddQ]; Prepend[Table[If[EvenQ[n],a[n][[1]],a[n][[2]]],{n,2,77}],1] (* Jayanta Basu, May 27 2013 *)

PARI

a(n) = my(x = if(n%2, 3*n+1, n/2)); x/2^valuation(x, 2); \\ Michel Marcus, Feb 27 2022

Python

# first formula
def A006370(n): return 3*n+1 if n%2 else n//2
def a(n): return x if (x := A006370(n))%2 else a(x)
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Dec 15 2021

Python

# fourth formula, uses A006370 above
def A000265(n):
    while n%2 == 0: n //= 2
    return n
def a(n): return A000265(A006370(n))
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Dec 15 2021

Formula

a(n) = A006370(n) if A006370(n) is odd, otherwise a(A006370(n)).

a(n) = A006370(n) iff n mod 4 = 2;

a(A016825(n)) = A006370(A016825(n));

a(n) = A000265(A006370(n)).

a(A160967(n)) = 1. - Reinhard Zumkeller, May 31 2009

For odd n, a(n) = a(2*A350091((n-1)/2)+1). - Ruud H.G. van Tol, Dec 17 2021

Sum_{k=1..n} a(k) ~ n^2 / 3. - Amiram Eldar, Aug 26 2024

a(n) = A000265(A014682(n)). - Alan Michael Gómez Calderón, Apr 10 2025