1,3

Let {f(k,N), k=0,1,2,...} denote the (3x+1)-sequence with starting value N; a(n) denotes the smallest positive integer which is not contained in the union of f(k,0),...,f(k,a(n-1)).

In other words a(n) is the starting value of the next '3x+1'-sequences in the sense that a(n) is not a value in any sequence f(k,N) with N < a(n).

f(0,N)=N, f(k+1,N)=f(k,N)/2 if f(k,N) is even and f(k+1,N)=3*f(k,N)+1 if f(k,N) is odd.

For all n, a(n) mod 6 is 0, 1 or 3. I conjecture that a(n)/n -> C=constant for n->oo, where C=2.311...

The Collatz conjecture says that for all positive n, there exists k such that C_k(n) = 1. Shaw states [p. 195] that "A positive integer n is pure if its entire tree of preimages under the Collatz function C are greater than or equal to it; otherwise n is impure. Equivalently, a positive integer n is impure if there exists r<n such that C_k(r) = n for some k." Theorem 2.1: If n == 0 (mod 3), then n is pure. If n == 2 (mod 3), then n is impure, reducing the field to 1 (mod 3). (mod 18), the following congruences are pure: n == 0 (mod 18); also 3, 6, 9, 12, 15; while n == 7 (mod 18) may be pure or impure. n == [2, 4, 5, 8, 10, 11, 13, 14, 16, or 17] (mod 18) are all impure. The asymptotic density d of the set of impure numbers I is such that d <= 2/3. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 28 2007

Pure numbers remaining after deleting the impure numbers in the hailstone (Collatz) problem; where the operation C(n) = {3n+1, n odd; n/2, n even}. Add the 0 mod 3 terms in order, among the terms of A127633, since all 0 mod 3 numbers are pure. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 28 2007

After computing all a(n) < 10^9, the ratio a(n)/n appears to be converging to 2.31303... Hence it appears that the numbers in this sequence have a density of about 1/3 (due to all multiples of 3) + 99/1000. - T. D. Noe, Oct 12 2007

A016945 is a subsequence. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 17 2008

Douglas J. Shaw, "The Pure Numbers Generated by the Collatz Sequence", Fibonacci Quarterly, Vol. 44, Number 3, August 2006, p. 194.

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

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

Consider n=3: C(n), C_2(n), C_3(n)...; the iterates are 10, 5, 16, 8, 4, 2, 1, 4, 2, 1; where 4, 5, 8, 10 and 16 have appeared in the orbit of 3 and are thus impure.

a(1)=1 since Im(f(k,0))={0} for all k and so 1 is not a value of f(k,0). a(2)=3 since Im(f(k,0)) union Im(f(k,1))={0,1,2,4} and 3 is the smallest positive integer not contained in this set.

Cf. A070165 (Collatz trajectories), A127633.

Sequence in context: A120684 A026227 A026232 this_sequence A085359 A087916 A023982

Adjacent sequences: A061638 A061639 A061640 this_sequence A061642 A061643 A061644

nice,nonn

Frederick Magata (fmagata(AT)mi.uni-koeln.de), Jun 14 2001

Edited by T. D. Noe and N. J. A. Sloane (njas(AT)research.att.com), Oct 16 2007