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.
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
#!/usr/bin/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
KEYWORD
easy,nonn
AUTHOR
Howard A. Landman, May 28 2003
STATUS
approved