Created
January 9, 2013 17:07
-
-
Save moserrya/4494862 to your computer and use it in GitHub Desktop.
A solution to the ZeroCater math-y challenge that is capable of finding the fifth clean chain of primes.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Take a sequence of N numbers. We'll call the sequence a "Clean Chain of length N" | |
# if the sum of the first N - 1 numbers is evenly divisibly by the Nth number. | |
# For example, the sequence [2, 4, 6, 8, 10] forms a clean chain of length 5, | |
# since 2 + 4 + 6 + 8 = 20, which is divisible by 10, and the sequence has 5 numbers. | |
# The first clean chain formed out of the sequence of primes is simply [2], with length 1. | |
# The second is [2, 3, 5] with length 3. | |
# The third is [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, | |
# 53, 59, 61, 67, 71], with length 20 | |
# To use CleanChain, initialize it with the location of a file or files containing | |
# the numbers that will form the chain. | |
# x = CleanChain.new("../numbers/numbers_file.txt") | |
# Then call chain_length with an argument of which chain number you want to find | |
# x.chain_length(3) | |
# => 20 | |
# Alternatively, chain_length will return | |
# "A longer list of numbers is required to find chain #{nth_chain}" | |
# if that is the case | |
class CleanChain | |
attr_reader :prime_array | |
def initialize( directory ) | |
@prime_array = create_prime_array( directory ) | |
end | |
def create_prime_array( directory ) | |
prime_text = "" | |
Dir.glob(directory).each do |primes| | |
prime_text << open( primes, 'r' ).lines.drop(1).join(' ') | |
end | |
prime_array = [] | |
prime_text.split.each do |number| | |
prime_array << number.to_i | |
end | |
prime_array | |
end | |
def chain_length ( nth_chain ) | |
chain_counter = 0 | |
sum = 0 | |
@prime_array.each_with_index do |number, index| | |
sum += number | |
chain_counter += 1 if ( sum % number ).zero? | |
return @prime_array.index(number) + 1 if chain_counter == nth_chain | |
end | |
"A longer list of numbers is required to find chain #{nth_chain}" | |
end | |
end | |
# Note: downloaded the first 50 million primes from http://primes.utm.edu/lists/small/millions/ | |
# This makes it possible to find the fifth clean chain in a reasonable timeframe | |
x = CleanChain.new("./primes*.txt") | |
puts x.chain_length(4) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment