cp's OEIS Frontend

A082983 Odd numbers which lead to 1 in the 3x+1 problem, generated by a particular "least-first" greedy algorithm (see program code).

%I A082983 #17 Jul 12 2025 21:31:59
%S A082983 1,5,3,13,17,11,7,9,21,29,19,25,33,37,45,49,53,35,23,15,61,65,43,57,
%T A082983 69,77,51,81,85,93,101,67,89,59,39,113,75,117,133,141,149,99,157,173,
%U A082983 115,153,177,181,197,131,87,205,209,139,185,123,213,229,237,241,245,163,217
%N A082983 Odd numbers which lead to 1 in the 3x+1 problem, generated by a particular "least-first" greedy algorithm (see program code).
%C A082983 It is suspected but not proved that all odd integers are in the sequence - this is equivalent to whether all numbers reach 1 in the 3x+1 problem. The program code given below does not actually represent infinite sets, but the result is the same since the smallest remaining member of each sibling-set is always present.
%e A082983 The second term is 5 because if we take m = 1 (our starting point), generate all numbers m * 2^k, k >= 1, subtract 1 and divide by 3 for those which give an integer result, we get the set {5,21,85, ...} (sequence A002450), which we call the "children" of 1, and 5 is the smallest member of that set. Next we replace 5 in the set by 5's children {3,13,53,213, ...} (sequence A072197), forming a new working set of generated numbers that are not yet in the sequence. The next term is 3 because the smallest member is 3. 3 has no children, so we simply remove 3 from the working set and the next term is 13. [Edited by _Peter Munn_, Jun 20 2021]
%o A082983 (Perl)
%o A082983 @list = ( 1 );
%o A082983 while (1) {
%o A082983     $n = shift @list;
%o A082983     print "$n ";
%o A082983     # next sibling
%o A082983     push(@list,4*$n + 1);
%o A082983     # first child
%o A082983     if (($n % 3) == 1) {
%o A082983         $n = ($n*4 - 1)/3;
%o A082983         while ($n && (($n % 2) == 0)) { $n /= 2; }
%o A082983         push(@list,$n) unless ($n <= 1);
%o A082983     } elsif (($n % 3) == 2) {
%o A082983         $n = ($n*2 - 1)/3;
%o A082983         while ($n && (($n % 2) == 0)) { $n /= 2; }
%o A082983         push(@list,$n) unless ($n <= 1);
%o A082983     }
%o A082983     #else do nothing, since == 0 mod 3 has no children
%o A082983     # Inefficient - should have heap insertion sort.
%o A082983     @list = sort numeric @list;
%o A082983 }
%o A082983 sub numeric { $a <=> $b; }
%Y A082983 Cf. A002450, A072197.
%K A082983 easy,nonn
%O A082983 0,2
%A A082983 _Howard A. Landman_, May 28 2003