A159999 Number of numbers not greater than n occurring in Collatz (3x+1) trajectory starting with n.

1, 2, 3, 3, 4, 6, 5, 4, 7, 6, 7, 9, 7, 10, 7, 5, 9, 14, 11, 8, 6, 12, 9, 11, 14, 10, 10, 16, 14, 11, 10, 6, 17, 12, 9, 20, 18, 17, 18, 9, 13, 8, 20, 16, 14, 12, 13, 12, 20, 21, 18, 12, 10, 18, 15, 20, 24, 19, 22, 16, 14, 17, 15, 7, 23, 25, 22, 15, 13, 12, 16, 23

Offset

1,2

Comments

If the Collatz conjecture is true, there are no cycles in the 3x+1 trajectory and the difference between the counts here and those of A076228 is that the start value is counted here but not there; then a(n) = 1+A076228(n) [discovered by sequencedb.net]. - R. J. Mathar, Jun 24 2021

Links

R. Zumkeller, Table of n, a(n) for n = 1..10000

Index entries for sequences related to 3x+1 (or Collatz) problem

Formula

a(n) < n for n>6;

a(A033496(n)) = A008908(A033496(n)).

a(n) = f(n,n,1) with f(n,m,x) = if m=1 then x else f(n, A006370(m), if A006370(m)<n then x+1 else x).

a(n) = n - A246436(n); row lengths of triangle A214614. - Reinhard Zumkeller, Sep 01 2014

Example

a(9) = #{1,2,4,5,7,8,9} = 7, as
9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-[4-2-1]*
9-..-..-7-..-..-..-..-..-..-..-..-..-..-5-..-8-[4-2-1]*.

Maple

b:= proc(n, m) option remember; `if`(n<=m, 1, 0)+
     `if`(n=1, 0, b(`if`(n::even, n/2, 3*n+1), m))
    end:
a:= n-> b(n$2):
seq(a(n), n=1..72);  # Alois P. Heinz, Dec 02 2025

Mathematica

Collatz[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; f[n_] := Module[{c = Collatz[n]}, Length[Select[c, # <= n &]]]; Table[ f[n], {n, 100}] (* T. D. Noe, Mar 07 2013 *)

Prog

(Haskell)
a159999 n = length $ takeWhile (<= n) $ sort $ a070165_row n
-- Reinhard Zumkeller, Sep 01 2012

Crossrefs

Cf. A033496, A008908, A070165, A214614.

Sequence in context: A320509 A358298 A347712 * A003977 A003971 A349371

Adjacent sequences: A159996 A159997 A159998 * A160000 A160001 A160002

Keyword

nonn,look

Author

Reinhard Zumkeller, May 04 2009

Status

approved