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,2

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.

Links

Table of n, a(n) for n=0..62.

Example

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]

Prog

(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; }

Crossrefs

Cf. A002450, A072197.

Sequence in context: A280818 A085910 A093544 * A083594 A178497 A364888

Adjacent sequences: A082980 A082981 A082982 * A082984 A082985 A082986

Keyword

easy,nonn

Author

Howard A. Landman, May 28 2003

Status

approved