A Puzzle

Think of a positive whole number, and apply the following rules:

1. if the number is even, divide it by 2
2. if the number is odd, multiply it by 3 and add 1
3. if you reach 1, stop; otherwise go to Step 1

Do you always reach 1? Prove your answer.

The Collatz-Syracuse-Ulam Problem

The puzzle is known as the Collatz-Syracuse-Ulam problem (and has many other names).

No one knows if the sequence always reaches 1, but it is thought that it does.

Computer calculations show that every starting number up to at least 19 * 2⁵⁸ ≈ 5.48 * 10¹⁸ eventually hits 1. [Ian Stewart, Professor Stewart's Hoard of Mathematical Treasures].

The Halting Problem

In computability theory, the halting problem can be stated as:

Given a program and an input to the program, decide (yes or no) whether or not the program will eventually halt when run with that input.

In 1936, Alan Turing proved that the problem is undecidable: no general algorithm exists that can solve the problem for all possible program-input pairs.

See:
How Dr. Seuss would prove the halting problem undecidable
CSE2001 Introduction to the Theory of Computation

The Collatz Problem

In pseudocode:

while p is not equal to 1
   if p is even
      p = p / 2
   else
      p = 3 * p + 1

In Java:

while (p != 1)
{
   if (???)
   {
      
   }
   else
   {
      
   }
   output.println(p);
}

Loops

In Java, the code inside the block of a loop runs if a condition (logical expression) is true.

In while loops, the condition is checked once (and only once) before the loop runs the first time, and every time at the end of the loop body.

A   while (condition)
    {
       //
B      // loop body
       //
    }
C   // after loop

1. On Line A, the condition is checked; if it is true the loop body B is run, otherwise control flows to C.
2. After the B is run, the condition is checked again; if it is true the loop body B is run, otherwise control flows to C.

Reading a File One Line at a Time

You can use a Scanner object to read a file one line at a time.

Scanner has a constructor that can create a Scanner for scanning files.

Scanner has a method nextLine that scans just past the end of the current line and returns everything that was scanned.

Scanner has a method hasNextLine that returns true if there is another line of input.

Reading a File One Line at a Time

import java.io.File;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Scanner;

public class ReadFile
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;
      
      // first command line argument is a filename
      String fileName = args[0];
      File inputFile = new File(fileName);
      
      // creating the Scanner for a file might
      //   fail with an exception
      Scanner in = null;
      try
      {
         in = new Scanner(inputFile);
      }
      catch (IOException ex)
      {
         out.println("Error opening file named " + fileName);
         System.exit(1);
      }
      
      while (in.hasNextLine())
      {
         String line = in.nextLine();
         out.println(line);
      }
   }
}

Gambler's Ruin

A gambler with finite wealth playing a fair game (equal odds of winning or losing) will eventually go broke against an opponent with infinite wealth (casino). However, it is possible for a disciplined gambler to make money if he stops gambling after he has accumulated a preset amount of wealth.

What are the odds of reaching the preset amount of wealth?

How many games will it take (on average)?

Gambler's Ruin Simulation

It is easy to simulate the gambler's ruin scenario. You need to know:

1. how much money the gambler starts with
2. how much money the gambler wants to leave with

You also need to know how much it costs to play a game. To keep things simple, assume that it costs $1 to play a game.

Gambler's Ruin Simulation

import java.util.Scanner;
import java.io.PrintStream;
import java.util.Random;

public class GamblersRuin
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;
      Scanner input = new Scanner(System.in);
      
      output.print("Starts with $ ");
      int startDollars = input.nextInt();
      
      output.print("Finish with $ ");
      int target = input.nextInt();
      
      Random game = new Random();

      int dollars = startDollars;
      while (dollars > 0 && dollars < target)
      {
         if (game.nextBoolean())
         {
            dollars++;
         }
         else
         {
            dollars--;
         }
      }
      
      if (dollars == 0)
      {
         output.println("Busted!");
      }
      else
      {
         output.println("Winner!");
      }
   }
}

Gambler's Ruin

Modify the gambler's ruin program so that it simulates 1000 full games (i.e., the player accumulates enough wealth or goes broke a total of 1000 times). Each of the 1000 full games should be run with the same original amounts of starting and goal money. Using your simulation, estimate the odds of winning (accumulating enough wealth to stop).