Skip to content

Instantly share code, notes, and snippets.

@moserrya
Created January 9, 2013 17:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save moserrya/4494862 to your computer and use it in GitHub Desktop.
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.
# 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