Investigating the Collatz Conjecture

(From Ch. 4 ‘More in Depth’)

Application: The Collatz Conjecture

The Collatz Procedure

1. Start with a positive number.
2. Check to see if it’s even or odd.
   • If it’s even, divide it by 2.
   • If it’s odd, multiply it by 3 and add 1.
3. Keep repeating Step 2, until the number becomes 1.

Example

• Start with 5.
• Odd, so compute \(3 \times 5 +1 = 16\).
• Even, so compute \(16/2 = 8\).
• Even so, compute \(8/2 = 4\).
• Even, so compute \(4/2 = 2\).
• Even, so compute \(2/2 = 1\).
• Time to stop.

(Note that 1 -> 4 -> 2 -> 1 …, cycling forever.)

The Collatz Conjecture

No matter what positive number you start with, the Collatz procedure will eventually get you back to 1.

This simple conjecture has never been proven or disproven!

Some numbers take a surprisingly long time to get down to 1, and they often have an exciting journey along the way.

Code the Rule

collatzRule <- function(m) {
  if ( m %% 2 == 0) {
    return(m/2)
  } else {
    return(3*m + 1)
  }
}

Try It

collatzRule(300)

[1] 150

collatzRule(17)

[1] 52

Make a Sequence

collatz <- function(n) {
  numbers <- numeric()
  while ( n > 1 ) {
    # stick n onto the end of numbers:
    numbers <- c(numbers, n)
    n <- collatzRule(n)
  }
  print(numbers)
}

Try It

collatz(13)

[1] 13 40 20 10  5 16  8  4  2

collatz(300)

 [1] 300 150  75 226 113 340 170  85 256 128  64  32  16   8   4   2

Improvement to Save Memory

collatz <- function(n, limit = 10000) {
  # collatz numbers will go in this vector
  numbers <- numeric(limit)
  # keep count of how many numbers we have made:
  counter <- 0
  while ( n > 1 & counter < limit) {
    # need to make a new number
    counter <- counter + 1
    # put the current number into the vector
    numbers[counter] <- n
    # make next Collatz number
    n <- collatzRule(n)
  }
  # find how many Collatz numbers we made:
  howMany <- min(counter, limit)
  # print them out:
  print(numbers[1:howMany])
}

Further Refinement: Make Showing Sequence Optional

collatz <- function(n, limit = 10000) {
  numbers <- numeric(limit)
  counter <- 0
  while ( n > 1 & counter < limit) {
    counter <- counter + 1
    numbers[counter] <- n
    n <- collatzRule(n)
  }
  howMany <- min(counter, limit)
  cat("The Collatz sequence has ", howMany, " elements.\n", sep = "")
  show <- readline("Do you want to see it (y/n)?  ")
  if ( show == "y" ) {
    print(numbers[1:howMany])
  }
}

One More Refinement: Add Graph

collatz <- function(n, limit = 10000) {
  # record initial number because we will change n
  initial <- n  
  numbers <- numeric(limit)
  counter <- 0
  while ( n > 1 & counter < limit) {
    counter <- counter + 1
    numbers[counter] <- n
    n <- collatzRule(n)
  }
  howMany <- min(counter, limit)
  steps <- 1:howMany
  cat("The Collatz sequence has ", howMany, " elements.\n", sep = "")
  show <- readline("Do you want to see it (y/n)?  ")
  if ( show == "y" ) {
    print(numbers[steps])
  }
  # use initial value to make plot title:
  plotTitle <- paste0("Collatz Sequence for n = ", initial)
  # make the plot
  ggplot(mapping = aes(x = steps, y = numbers[steps])) +
    geom_point() + geom_line() +
    labs( x = "Step", y = "Collatz Value at Step",
          title = plotTitle)
}

Try It Out!

collatz(257). ## or whatever you like