

A061641


Pure numbers in the Collatz (3x+1) iteration. Also called pure hailstone numbers.


18



0, 1, 3, 6, 7, 9, 12, 15, 18, 19, 21, 24, 25, 27, 30, 33, 36, 37, 39, 42, 43, 45, 48, 51, 54, 55, 57, 60, 63, 66, 69, 72, 73, 75, 78, 79, 81, 84, 87, 90, 93, 96, 97, 99, 102, 105, 108, 109, 111, 114, 115, 117, 120, 123, 126, 127, 129, 132, 133, 135, 138, 141, 144, 145
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(n1)).
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. 194201.
B. Snapp, M. Tracy, The Collatz Problem and analogues, JIS 11 (2008) 08.4.7.
Index entries for sequences related to 3x+1 (or Collatz) problem


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

Cf. A070165 (Collatz trajectories), A127633, A336938, A336938. See A177729 for a variant.
Sequence in context: A026232 A286802 A297249 * A325443 A085359 A231664
Adjacent sequences: A061638 A061639 A061640 * A061642 A061643 A061644


KEYWORD

nice,nonn


AUTHOR

Frederick Magata (frederick.magata(AT)unimuenster.de), Jun 14 2001


EXTENSIONS

Edited by T. D. Noe and N. J. A. Sloane, Oct 16 2007


STATUS

approved



