Example: Ulam sequence
The Ulam Sequence
A mathematician named Ulam proposed a sequence of numbers starting at any positive integer n (n > 1):
- If n is 1, stop.
- If n is even, replace it with n/2.
- If n is odd, replace it with 3*n + 1.
- Continue with this process until n reaches 1.
Here are some examples for the first few integers.
2 -> 1 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 4 -> 2 -> 1 5 -> 16 -> 8 -> 4 -> 2 -> 1 6 -> 3 -> etc as for 3 above. 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> see 5 above.
This is a well known problem. See The 3x+1 problem and its generalizations for more information.
Does every sequence stop? It's unknown if all sequences end at 1. Perhaps there are sequences that get into a loop, or increase indefinitely.
Programming 1 - Write a loop that shows the Ulam sequence
Write a loop that reads an integer n (in range 1 - 1000) and computes and displays the values in the sequence.
Solution using dialog I/O
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// File : ulam/Ulam0Dialog.java // Purpose: Compute Ulam sequence. Uses dialog I/O, // Author : Fred Swartz // Date : 2006-04-20 import javax.swing.*; public class Ulam0Dialog { public static void main(String[] args) { while (true) { //... Read an int. Quit if there is no input. String inputLine = JOptionPane.showInputDialog("Enter a number" + " between 1 and 1000"); if (inputLine == null) { break; } int n = Integer.parseInt(inputLine); //... Make sure it's in the correct range. if (n > 0 && n <= 1000) { //... Initialize variables. int count = 0; String result = "" + n; //... Loop until n gets to the value 1 while (n > 1) { if (n%2 == 0) { // if even n = n / 2; } else { // if odd n = 3 * n + 1; } //... Build output string. count++; // Count number of elements. //... Start a new line every 20 numbers if (count % 20 == 0) { result = result + "\n"; } result = result + " " + n; } //... Display result JOptionPane.showMessageDialog(null, "\nSequence = " + result + "\nElements in sequence = " + count); } } } } |
Solution using console I/O
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// File : ulam/Ulam0Console.java // Purpose: Compute Ulam sequence. // Author : Fred Swartz // Date : 2006-04-20 import java.util.*; public class Ulam0Console { public static void main(String[] args) { //... Initialization. Scanner in = new Scanner(System.in); System.out.println("Enter a number between 1 and 1000"); while (in.hasNextInt()) { int n = in.nextInt(); //... Make sure it's in the correct range. if (n > 0 && n <= 1000) { //... Initialize variables. int count = 0; // Number of elements in the sequence. String result = "" + n; // Build output string here. //... Loop until n gets to the value 1 while (n > 1) { if (n%2 == 0) { // if even n = n / 2; } else { // if odd n = 3 * n + 1; } //... Build output string. count++; // Count number of elements. if (count % 20 == 0) { result = result + "\n"; // New line every 20 numbers. } result = result + " " + n; // Append to end of result. } //... Display result System.out.println("Sequence = " + result + "\nElements in sequence = " + count); } } } } |