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:
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.