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
  else
    return 3*n+1
  end
end

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)
    chain+=1
  end
  #print("N: ", counter, " Had a chain of: ",chain,"\n")
  if (chain > longest)
    longest = chain
    winning_num=counter
  end
  counter+=1
end

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
end

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
    end
    index += 1 #this is the current place in the constant
  end
  i+=1
end
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
File.open("champernownes", "a") do |f|
  i = 0
  while i < 1000000
    f<<i.to_s
    i+=1
  end
end

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
File.open("champernownes", "r") do |f|
  i = 0
  f.each_char do |c|
    if idxs.include?(i)
      prod *= c.to_i
    end
    i+=1
  end
end
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.