A075680 For odd numbers 2n-1, the minimum number of iterations of the reduced Collatz function R required to yield 1. The function R is defined as R(k) = (3k+1)/2^r, with r as large as possible.

0, 2, 1, 5, 6, 4, 2, 5, 3, 6, 1, 4, 7, 41, 5, 39, 8, 3, 6, 11, 40, 9, 4, 38, 7, 7, 2, 41, 10, 10, 5, 39, 8, 8, 3, 37, 42, 3, 6, 11, 6, 40, 1, 9, 9, 33, 4, 38, 43, 7, 7, 31, 12, 36, 41, 24, 2, 10, 5, 10, 34, 15, 39, 15, 44, 8, 8, 13, 32, 13, 3, 37, 42, 42, 6, 3, 11, 30, 11, 18, 35, 6, 40, 23

Offset: 1

Author

T. D. Noe, Sep 25 2002

Keywords

• easy
• nonn

Comments

See A075677 for the function R applied to the odd numbers once. The 3x+1 conjecture asserts that a(n) is a finite number for all n. The function R applied to the odd numbers shows the essential behavior of the 3x+1 iterations.

Bisection of A006667. - T. D. Noe, Jun 01 2006

Examples

			a(4) = 5 because 7 is the fourth odd number and 5 iterations are needed: R(R(R(R(R(7)))))=1.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..5000

Crossrefs

Cf. A075677.

Cf. A075684 for the largest number attained during the iteration.

Cf. A000265.

Cf. A060445 which also counts intermediate even steps.

Cf. A173732.

Programs

Haskell

a075680 n = snd $ until ((== 1) . fst)
            (\(x, i) -> (a000265 (3 * x + 1), i + 1)) (2 * n - 1, 0)
-- Reinhard Zumkeller, Jan 08 2014

Mathematica

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[m=n; cnt=0; If[n>1, While[m=nextOddK[m]; cnt++; m!=1]]; cnt, {n, 1, 200, 2}]

PARI

a(n)=my(s); n+=n-1; while(n>1, n+=n>>1+1; if(n%2==0, n>>=valuation(n,2)); s++); s \\ Charles R Greathouse IV, Dec 22 2021

Perl

sub a {
  my $v = 2 * shift() - 1;
  my $c = 0;
  until (1 == $v) {
    $v = 3 * $v + 1;
    $v /= 2 until ($v & 1);
    $c += 1;
  }
  return $c;
} # Ruud H.G. van Tol, Nov 16 2021

Formula

a(n) = a(A173732(n-1) + 1) + 1 for n >= 2. - Alan Michael Gómez Calderón, Apr 10 2025