A082538 Number of numbers k which give 1 after applying exactly n iterations of the 3k+1 algorithm (if a number is even, divide it by 2; if it is odd, multiply by 3 and add 1). This total includes numbers k which also give 1 for a smaller number of iterations (i.e., for this sequence we do not assume the algorithm halts when 1 is reached).

1, 1, 1, 2, 2, 3, 4, 6, 7, 10, 12, 15, 20, 26, 33, 44, 55, 69, 88, 113, 141, 179, 226, 284, 358, 453, 571, 724, 913, 1149, 1456, 1839, 2323, 2945, 3718, 4688, 5933, 7498, 9476, 11982, 15126, 19111, 24172, 30535, 38563, 48733, 61560, 77792, 98313, 124240

Offset: 0

Author

Howard A. Landman, May 23 2003

Keywords

• easy
• nonn

Examples

			a(3)=2 because both 1 and 8 lead to 1 in 3 steps (1->4->2->1 and 8->4->2->1).
		

References

• Gunther J. Wirsching, "The Dynamical System Generated by the 3n+1 Function" Lecture Notes in Mathematics (Springer Verlag, 1999), p. 1681

Links

• K. Conrow, 3n+1 Problem Statement.
• Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Month1y v.92 (1985), pp. 3-23.

Programs

Perl

#!/usr/bin/perl @old = ( 1 ); while (1) { print scalar(@old), " "; @new = ( ); foreach $n (@old) { if (($n % 6) == 4) { push(@new,($n-1)/3); } push(@new,$n+$n); } @old = @new; } sub numeric { return ($a <=> $b); }