Computer Science and Engineering

The mathematician Stanislav Ulam suggested that any positive integer would always converge to 1 if treated in the following way:

1. Get a number.
2. If it is odd, multiply it by three and add 1.
3. If it is even, divide it by 2.
4. Repeat 2 and 3, on the resultant number.

For instance, if the original number is 11, the sequence would be:

  11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Write a program that will print the sequence for all integers between 1 and 20 inclusive. For example:

1
2 1
3 10 5 16 8 4 2 1

// C++ Solution - Programming Puzzle - June 2008

#include <iostream>

using namespace std;

int main() {
  int num;

  for (int i=1; i <= 20; ++i) {
    num = i;
    cout << num << " ";
    while (num != 1) {
      if (num % 2 == 0) num /= 2;
      else num = num * 3 + 1;
      cout << num << " "; 
      }
    cout << endl;
    }
  
  return 0;
}



// Java solution for programming puzzle by Rabecca Gay.

public class PuzzleProgramsPractice {

  public static void main(String args[]) {
    int sum;

    for( int i = 1; i <= 20; i++ ) {
      sum = i;
      System.out.printf( "%2d " , sum );
      while( sum != 1) {
        if ( sum % 2 != 0)
          sum = sum * 3 + 1;
        else sum = sum / 2;
        System.out.printf( " %2d" , sum );
        }
      System.out.print("\n");
      } // end for loop

  } // end main
}



<?php // Recursive PHP solution provided by Russell A. Yermal

function solve($n) {
  if ($n==1) return $n;
  $a = $n;
  if ($n % 2) $n = $n * 3 + 1;
  else $n /= 2;		
  return ("$a " . solve($n));
}

for ($i=1; $i <= 20; $i++)
  echo solve($i) . "\n";
?>

If you have solutions to this puzzle in other programming languages, please submit them to webmaster {at} cse.unt.edu and we will post them here.

The output these programs produce will look something like:

1
2 1
3 10 5 16 8 4 2 1
4 2 1
5 16 8 4 2 1
6 3 10 5 16 8 4 2 1
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
8 4 2 1
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
10 5 16 8 4 2 1
11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
12 6 3 10 5 16 8 4 2 1
13 40 20 10 5 16 8 4 2 1
14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
16 8 4 2 1
17 52 26 13 40 20 10 5 16 8 4 2 1
18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
20 10 5 16 8 4 2 1