|
%I #40 Jan 19 2023 01:44:10
%S 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,
%T 55,57,60,63,66,69,72,73,75,78,79,81,84,87,90,93,96,97,99,102,105,108,
%U 109,111,114,115,117,120,123,126,127,129,132,133,135,138,141,144,145
%N Pure numbers in the Collatz (3x+1) iteration. Also called pure hailstone numbers.
%C 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)).
%C 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).
%C 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.
%C 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...
%C 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
%C 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
%C 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
%C A016945 is a subsequence. - _Reinhard Zumkeller_, Apr 17 2008
%H T. D. Noe, <a href="/A061641/b061641.txt">Table of n, a(n) for n = 1..10000</a>
%H Douglas J. Shaw, <a href="http://www.fq.math.ca/Papers1/44-3/quartshaw03_2006.pdf">The Pure Numbers Generated by the Collatz Sequence</a>, The Fibonacci Quarterly, Vol. 44, Number 3, August 2006, pp. 194-201.
%H B. Snapp and M. Tracy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Snapp/snapp.html">The Collatz Problem and analogues</a>, JIS 11 (2008) 08.4.7.
%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%e 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.
%e 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.
%t 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 *)
%o (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))); };
%o 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; };
%o makeVec(m) = { my(v = [], A = Set([]), i); for(i = 1, m, v = concat(v, firstMiss(A)); if (i < m, A = iter(A))); v; };
%o makeVec(64) \\ _Markus Sigg_, Aug 08 2020
%Y Cf. A070165 (Collatz trajectories), A127633, A336938, A336938. See A177729 for a variant.
%K nice,nonn
%O 1,3
%A Frederick Magata (frederick.magata(AT)uni-muenster.de), Jun 14 2001
%E Edited by _T. D. Noe_ and _N. J. A. Sloane_, Oct 16 2007
|
