A347409 Longest run of halving steps in the trajectory from n to 1 in the Collatz map (or 3x+1 problem), or -1 if no such trajectory exists.

0, 1, 4, 2, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 6, 4, 5, 4, 4, 4, 5, 4, 4, 5, 5, 5, 4, 4, 5, 4, 4, 4, 4, 4, 5, 6, 4, 4, 4, 5, 5, 4, 4, 4, 4, 4, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5, 6, 4, 4, 4, 4, 4, 5, 5, 4, 5, 4, 8, 4, 4, 4, 4, 4, 5, 5, 5, 6, 8, 4, 4

Offset: 1

Author

Paolo Xausa, Aug 30 2021

Keywords

• nonn
• easy

Comments

If the longest run of halving steps occurs as the final part of the trajectory, a(n) = A135282(n), otherwise a(n) > A135282(n).

Every nonnegative integer appears in the sequence at least once, since for any k >= 0 a(2^k) = k.

Conjecture: every integer >= 4 appears in the sequence infinitely many times.

Examples

			a(15) = 5 because the Collatz trajectory starting at 15 contains, as the longest halving run, a 5-step subtrajectory (namely, 160 -> 80 -> 40 -> 20 -> 10 -> 5).
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A006370, A070165, A135282.

Cf. A347668 (indices of records), A347669 (indices of first occurrences), A348007.

Programs

Mathematica

nterms=100;Table[c=n;sm=0;While[c>1,If[OddQ[c],c=3c+1,If[(s=IntegerExponent[c,2])>sm,sm=s];c/=2^s]];sm,{n,nterms}]

PARI

a(n)=my(nb=0); while (n != 1, if (n % 2, n=3*n+1, my(x = valuation(n, 2)); n /= 2^x; nb = max(nb, x));); nb; \\ Michel Marcus, Sep 03 2021

Python

def A347409(n):
    m, r = n, 0
    while m > 1:
        if m % 2:
            m = 3*m + 1
        else:
            s = bin(m)[2:]
            c = len(s)-len(s.rstrip('0'))
            m //= 2**c
            r = max(r,c)
    return r # Chai Wah Wu, Sep 29 2021