OFFSET
1,3
COMMENTS
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, 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, 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, Apr 17 2008
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
Douglas J. Shaw, The Pure Numbers Generated by the Collatz Sequence, The Fibonacci Quarterly, Vol. 44, Number 3, August 2006, pp. 194-201.
B. Snapp and M. Tracy, The Collatz Problem and analogues, JIS 11 (2008) 08.4.7.
EXAMPLE
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.
MATHEMATICA
DoCollatz[n_] := Module[{m = n}, While[m > nn || ! reached[[m]], If[m <= nn, reached[[m]] = True]; If[EvenQ[m], m = m/2, m = 3 m + 1]]]; nn = 200; reached = Table[False, {nn}]; t = {0, 1}; While[DoCollatz[t[[-1]]]; pos = Position[reached, False, 1, 1]; pos != {}, AppendTo[t, pos[[1, 1]]]]; t (* T. D. Noe, Jan 22 2013 *)
PROG
(PARI) firstMiss(A) = { my(i); if(#A == 0 || A[1] > 0, return(0)); for(i = 1, A[#A] + 1, if(!setsearch(A, i), return(i))); };
iter(A) = { my(a = firstMiss(A)); while(!setsearch(A, a), A = setunion(A, Set([a])); a = if(a % 2, 3*a+1, a/2)); A; };
makeVec(m) = { my(v = [], A = Set([]), i); for(i = 1, m, v = concat(v, firstMiss(A)); if (i < m, A = iter(A))); v; };
makeVec(64) \\ Markus Sigg, Aug 08 2020
CROSSREFS
KEYWORD
nice,nonn
AUTHOR
Frederick Magata (frederick.magata(AT)uni-muenster.de), Jun 14 2001
EXTENSIONS
Edited by T. D. Noe and N. J. A. Sloane, Oct 16 2007
STATUS
approved