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

1, 5, 3, 13, 17, 11, 7, 9, 21, 29, 19, 25, 33, 37, 45, 49, 53, 35, 23, 15, 61, 65, 43, 57, 69, 77, 51, 81, 85, 93, 101, 67, 89, 59, 39, 113, 75, 117, 133, 141, 149, 99, 157, 173, 115, 153, 177, 181, 197, 131, 87, 205, 209, 139, 185, 123, 213, 229, 237, 241, 245, 163, 217

Offset: 0

Author

Howard A. Landman, May 28 2003

Keywords

• easy
• nonn

Comments

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.

Examples

			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]
		

Crossrefs

Cf. A002450, A072197.

Programs

Perl

@list = ( 1 );
while (1) {
    $n = shift @list;
    print "$n ";
    # next sibling
    push(@list,4*$n + 1);
    # first child
    if (($n % 3) == 1) {
        $n = ($n*4 - 1)/3;
        while ($n && (($n % 2) == 0)) { $n /= 2; }
        push(@list,$n) unless ($n <= 1);
    } elsif (($n % 3) == 2) {
        $n = ($n*2 - 1)/3;
        while ($n && (($n % 2) == 0)) { $n /= 2; }
        push(@list,$n) unless ($n <= 1);
    }
    #else do nothing, since == 0 mod 3 has no children
    # Inefficient - should have heap insertion sort.
    @list = sort numeric @list;
}
sub numeric { $a <=> $b; }