CSCI A201/A597 Lab Notes 2 Spring 2000

Read section 3.4.2 (page 79) in your text about Syracuse numbers. I will summarize it here. We work with positive numbers which are integers, and greater or equal than 2. For each such number consider the following iterative process:

1. if the number is even divide it by 2
   otherwise multiply it by 3 and add 1

2. if the resulting value is not 1 repeat step 1
   otherwise stop

1. 5 is not even so we multiply it by 3 and add 1 and we obtain 16
   16 is not 1 so we need to keep going

2. 16 is even so we divide it by 2 and obtain 8
   8 is not 1 so we need to keep going

3. 8 is even so we divide by 2 and obtain 4
   4 is not 1 so we need to go on

4. 4 is even so we divide by 2 and obtain 2
   2 is not 1 so we need to go on

5. 2 is even so we divide by 2 and obtain 1
   we have reached 1 so we can stop.

How long does it take for 8?

How about 3?

Or 27? (Can you do this one by hand?)

For 27 it actually takes over 100 iterations so doing it by hand is likely to take a long time and produce errors too.

So let's write a program that given a number will count the number of times we have to execute the if statement mentioned in the pseudocode at the beginning of these notes before we reach a value of 1 (which, as the pseudocode says, is the end of the process).

Your program could work like this:

frilled.cs.indiana.edu%javac Syracuse.java
frilled.cs.indiana.edu%java Syracuse 5
For 5 it takes 5 steps.
frilled.cs.indiana.edu%java Syracuse 8
For 8 it takes 3 steps.
frilled.cs.indiana.edu%java Syracuse 3
For 3 it takes 7 steps.
frilled.cs.indiana.edu%java Syracuse 27
For 27 it takes 111 steps.
frilled.cs.indiana.edu%

public class Syracuse {
    public static void main(String[] args) {
	int number = Integer.parseInt(args[0]); 
        int workingValue = number; 
        int count = 0; 
        while (workingValue > 1) {
	    if (workingValue % 2 == 0) {
		workingValue = workingValue / 2;
	    } else {
		workingValue = workingValue * 3 + 1; 
	    } 
	    count = count + 1; 
	} 
	System.out.println("For " + number + " it takes " + count + " steps.");
    } 
}

Notice a few things about the solution above:

• we use Integer.parseInt to turn the first argument into an int
• we need to keep the original number until the end so we use a copy of it for iterations
• we use a separate variable, count, to count the number of times we go around the loop

1. accept two values, representing the range of values for which you want to run the program
2. report the number with the max number of iterations in the given range (and the max value too)

• the two numbers are positive integers greater or equal to 2
• the second number is greater or equal to the first (for the range to be valid)

frilled.cs.indiana.edu%java Syracuse 15 30
15: 17 iterations.
16: 4 iterations.
17: 12 iterations.
18: 20 iterations.
19: 20 iterations.
20: 7 iterations.
21: 7 iterations.
22: 15 iterations.
23: 15 iterations.
24: 10 iterations.
25: 23 iterations.
26: 10 iterations.
27: 111 iterations.
28: 18 iterations.
29: 18 iterations.
30: 18 iterations.
Max: 111 iterations, for [27]
frilled.cs.indiana.edu%

How would you do it, if you were to do it by hand?

I would use a method such as this:

• I would use a location called max to store the highest value
• I would initialize it to be zero
• I would compare it with the count for each number and once I found a value that is bigger than the one I had stored in max I would store this new, bigger value in max

It is now quite easy to report the number for which that max number of iterations actually happens. I will leave it up to you to think about it.

Additional practice programs

Write a program that behaves like this:

frilled.cs.indiana.edu%javac Tri.java
frilled.cs.indiana.edu%java Tri 3

*
**
frilled.cs.indiana.edu%java Tri 6

*
**
***
****
*****
frilled.cs.indiana.edu%java Tri 4

*
**
***
frilled.cs.indiana.edu%java Tri 10

*
**
***
****
*****
******
*******
********
*********
frilled.cs.indiana.edu%

Here's my solution:

public class Tri {
    public static void main(String[] args) {
	int size = Integer.parseInt(args[0]); 
	for (int i = 0; i < size; i++) {
	    for (int j = 0; j < i; j++) {
		System.out.print("*"); 
	    } 
	    System.out.println(); 
	} 
    } 
} 

frilled.cs.indiana.edu%javac Dia.java
frilled.cs.indiana.edu%java Dia 3
   *   
  ***  
 ***** 
*******
*     *
**   **
*** ***
*******
frilled.cs.indiana.edu%java Dia 4
    *    
   ***   
  *****  
 ******* 
*********
*       *
**     **
***   ***
**** ****
*********
frilled.cs.indiana.edu%java Dia 10
          *          
         ***         
        *****        
       *******       
      *********      
     ***********     
    *************    
   ***************   
  *****************  
 ******************* 
*********************
*                   *
**                 **
***               ***
****             ****
*****           *****
******         ******
*******       *******
********     ********
*********   *********
********** **********
*********************
frilled.cs.indiana.edu%

Also note that we switch the output mode when we draw the lower half of the diamond.

Here's my solution:

public class Dia {
    public static void main(String[] args) {
	int size = Integer.parseInt(args[0]); 

	for (int i = size; i >= 0; i--) {
	    for (int j = 0; j < i; j++) {
		System.out.print(" "); 
	    } 
	    for (int j = 0; j < 2 * (size - i) + 1; j++) {
		System.out.print("*"); 
	    } 
	    for (int j = 0; j < i; j++) {
		System.out.print(" "); 
	    } 
	    System.out.println(); 
	}

	for (int i = 1; i <= size; i++) {
	    for (int j = 0; j < i; j++) {
		System.out.print("*"); 
	    } 
	    for (int j = 0; j < 2 * (size - i) + 1; j++) {
		System.out.print(" "); 
	    } 
	    for (int j = 0; j < i; j++) {
		System.out.print("*"); 
	    } 
	    System.out.println(); 
	}

	for (int j = 0; j < 2 * size + 1; j++) {
	    System.out.print("*"); 
	} 
	System.out.println();

    } 
} 

Or, two large triangles, if it's easier for you to think about it that way.

Either way, notice how there's a certain symmetry about it.