Mental Exercise for Menial Chores

If there’s one thing I learned from teaching, it’s that one of the most mind numbing activities is test proctoring. Most proctors aren’t allowed to use their smartphone, read a book, draw, or even sit. You are supposed to walk around and “actively proctor,” whatever that means. One of my coping tricks was to determine the collatz sequence of a random starting number, mentally.

A collatz sequence is a simple algorithm that creates a chain of numbers based on a starting ‘seed’ number. The rule is simple:

If n is even then:

n –> n/2

If n is odd then:

n –> 3n + 1

For example if you start with 5, an odd number, the next number would be

3*5 + 1 = 16

Since 16 is even, we divide it by two, so the next number is 8. So far our sequence is

5 –> 16 –> 8

Since 8 is even, we divide by two again, giving us 4. Divide that, and on and on until you reach 1. The overall sequence contains 6 numbers:

5 — > 16 –> 8 –> 4 –> 2 –> 1

This is called the collatz conjecture because it’s unproven whether or not any starting number will always reach one, like in the example above. Here is the question from Project Euler  which I will try to solve.

Which starting number, under one million, produces the longest chain?

How I will approach this problem

  1. Write a helper function that will determine the next number in the sequence
  2. Write a function that will loop through every number keeping track of the number of iterations.
  3. Once the chain has finished, check if it has surpassed the last winner. If it has, then replace it as the current ‘leader’ .

First, the helper function to determine the next number:

def next_collatz(n)
  if (n%2 == 0)
    return n/2
    return 3*n+1

Then, declare the variables to keep track of the current leader (longest)

longest = 0
counter = 1
winning_num = 0
x = 1

Construct the loop to go through all numbers less than one million

while counter < 1000000
  x = counter
  chain = 1
  while x > 1
    x = next_collatz(x)
  #print("N: ", counter, " Had a chain of: ",chain,"\n")
  if (chain > longest)
    longest = chain

Print the winner!

print("longest: ",longest," winningnum: ",winning_num,"\n") #Note this is the number that produces the longest chain, not the length of chain


Champernownes Constant

Champernowne was a mathematician/friend of Alan Turing who is most well known for his research on his self-named number, Champernowne’s Constant. You can generate this number by appending positive integers in ascending order after the decimal place:

0.123456789101112131415… etc.

It was a lot easier to come up with unique numbers in the 30’s.

Here are the challenges

1. Write an algorithm to quickly determine what number (0-9) is at a given index. For example, c(4) = 4, c(11) = 0, c(14) = 1, etc.

2. From Project Euler: Determine the product of c(1) * c(10) * c(100) * c(1,000) * c(10,000) * c(100,000) * c(1,000,000)

Since this number is a geometric series, you must know the previous number to generate the next. There is a tempting brute force approach:

c = "0."
i = 1
while i < 10000000
  c += i.to_s
  i += 1

While that does work, after 100,000 loops you’re going to start running out of memory. Here’s a better, but still nonfunctional solution:

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
i = 1 #loop number counter
prod = 1
index = 1
c = "0"
while i <= 1000000
  s = i.to_s #we need to check each digit in the string
  #p s
  #c += s
  s.chars.each_index do |j|
    if idxs.include?(index)
      prod *= s[j].to_i
    index += 1 #this is the current place in the constant
p prod

That works by changing a second incrementor, index, based on each number’s value. For example, the number ’12’ would change index by 2, the number ‘142’ would change index by 3, etc. It is still too slow to actually do the math.

Unable to find a solution fast enough to store the value in memory and look through it, I went with storing the data into a file instead, and reading in from the file.

First we create the file:

#Approximately 6mb"champernownes", "a") do |f|
  i = 0
  while i < 1000000

Then we read through it character by character, storing the product whenever we reach one of the indices relevant to the challenge.

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
prod = 1"champernownes", "r") do |f|
  i = 0
  f.each_char do |c|
    if idxs.include?(i)
      prod *= c.to_i
p prod

Be assured this is nowhere near the fastest algorithm for solving this problem, but it was one of the first times that I considered storing the ‘brute force’ solution into a file and then reading from that.