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

References

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

Links

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

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.

Example

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

Prog

#!/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); }

Crossrefs

Sequence in context: A238588 A353863 A102464 * A035939 A365827 A116665

Adjacent sequences: A082535 A082536 A082537 * A082539 A082540 A082541

Keyword

easy,nonn

Author

Howard A. Landman, May 23 2003

Status

approved