shrunk problem 40 to a more reasonable space

SamGerber · SamGerber · commit 2a5053c7fe26 · 2015-10-05T05:52:47.000Z
diff --git a/project-euler/40-pandigital_prime.rb b/project-euler/40-pandigital_prime.rb
@@ -8,30 +8,31 @@
 
 # Solution by Sam Gerber
 
-def pandigital_prime
-  primes = primes(987_654_321)
-  puts "primes done"
-  
-  loop do
-    number = primes.pop
-    digits = number.to_s.length
-    return number if is_pandigital?(number, digits)
-  end
-end
+# Note: all numbers whose digits sum to a multiple of 3 are divisible by 3.
+# The following are the sums of the digits of n-digit pandigital numbers:
+# 2-digits: 3   = 1 + 2                               DIVISIBLE BY 3!
+# 3-digits: 6   = 1 + 2 + 3                           DIVISIBLE BY 3!
+# 4-digits: 10  = 1 + 2 + 3 + 4                       24 possible primes
+# 5-digits: 15  = 1 + 2 + 3 + 4 + 5                   DIVISIBLE BY 3!
+# 6-digits: 21  = 1 + 2 + 3 + 4 + 5 + 6               DIVISIBLE BY 3!
+# 7-digits: 28  = 1 + 2 + 3 + 4 + 5 + 6 + 7           5040 possible primes
+# 8-digits: 36  = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8       DIVISIBLE BY 3!
+# 9-digits: 45  = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9   DIVISIBLE BY 3!
+
+# With this knowledge, we simply build and sort an array of all possible
+# 4- or 7-digit pandigital numbers and beginning at the end, return the
+# first prime we find.
 
+def pandigital_prime
+  pandigitals = []
+  [4,3,2,1].permutation{|p| pandigitals << p.join.to_i}
+  [7,6,5,4,3,2,1].permutation{|p| pandigitals << p.join.to_i}
+  pandigitals.sort!.reverse!
 
-# This method retuns an array of all primes not exceeding max
-def primes(max)
-  primes = []
-  number = 2
-  
-  while number <= max
-    primes << number if is_prime? number
-    number += 1
-  end
-  primes
+  pandigitals.each{|number| return number if is_prime?(number)}
 end
 
+
 # This method returns true if a number is prime
 def is_prime?(number)
   number = number.abs
@@ -47,11 +48,4 @@ def is_prime?(number)
   true
 end
 
-# This method returns true if the numbers contain all the
-# digits from 1 to n
-def is_pandigital?(*numbers, n)
-  numbers = numbers.join.split("").sort
-  numbers.count == numbers.uniq.count && numbers.first == "1" && numbers.last == n.to_s
-end
-
 puts pandigital_prime
diff --git a/project-euler/other_sieve.rb b/project-euler/other_sieve.rb
@@ -0,0 +1,13 @@
+	def sieve(max=100)
+	  sieve = []
+	  (2..max).each { |i| sieve[i] = i }
+	  (2..Math.sqrt(max)).each do |i|
+	    (i*i).step(max, i) { |j| sieve[j] = nil } if sieve[i]
+	  end
+	  sieve.compact
+	end
+
+puts	sieve(10)
+	# => [2, 3, 5, 7]
+puts	sieve(987654321).size
+	# => 9592
diff --git a/project-euler/segmented_sieve_of_eratosthenes.rb b/project-euler/segmented_sieve_of_eratosthenes.rb
@@ -51,5 +51,5 @@ def sieve(primes = nil, block)
 end
 
 puts ""
-print primes(987654321).count
+print primes(7654321).count
 puts ""
