Euler Solution 51

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 51

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

Caml by SanguineV

Runtime: 374ms

(* The sieve of Eratosthenes, takes an array and sets all non-prime positions to "false" *)
let setprimes arr =
let lim = (Array.length arr) - 1 in
let rec sieve = function
| c when c >= lim -> ()
| c -> (for i = 2 to (lim / c) do Array.set arr (c * i) false done; sieve (c + 2))
in
for i = 2 to (lim /2) do Array.set arr (i * 2) false done;
sieve 3
;;

(* Converts an integer into a list of it's digits (reverse order) *)
let rec todigs = function
| n when n < 10 -> [n]
| n -> n mod 10 :: todigs (n / 10)
;;

(* Counts how many instances of "i" in a list *)
let rec count i = function
| x::xs when i == x -> count i xs + 1
| _::xs -> count i xs
| [] -> 0
;;

(* Given an integer, it is a candidate for this problem if it has the same
 * digit three times. Return the digit if there is one, and 10 otherwise. *)
let candidate n =
let rec inner = function
| x::xs when count x xs == 2 -> x
| _::xs when List.length xs == 2 -> 10
| _::xs -> inner xs
| [] -> 10
in
inner (todigs n)
;;

(* Replace the "i" digits with "j"s in the integer "n" *)
let repl i j n =
let rec inner pow = function
| 0 -> 0
| n when n mod 10 == i -> inner (pow * 10) (n / 10) + (pow * j)
| n -> inner (pow * 10) (n / 10) + (pow * (n mod 10))
in
inner 1 n
;;

(* Given a number "n" and a digit "i" to work on, build a list of numbers
 * that are "n" with "i" replaced by "j" for some "j" up to 9. *)
let rec build n i = function
| 9 -> [repl i 9 n]
| j -> repl i j n :: (build n i (j + 1))
;;

(* Given an array that determines primes and a staring position, find the
 * first prime to have 8 variations by replacing one digit. *)
let findprimebase ps st =
let rec inner i =
if Array.get ps i
then (let ci = candidate i in
      if ci < 3 && List.fold_left (fun x y -> x + (if Array.get ps y then 1 else 0)) 1 (build i ci (ci + 1)) == 8
      then i
      else inner (i + 2))
else inner (i + 2)
in
inner st
;;

(* Create an array initialised to "true", set non-primes to false, then start at
 * 100001 and look for the prime base. *)
let primes = Array.create 1000000 true;;
setprimes primes;;
print_int (findprimebase primes 100001);;

I am surprised it is much faster then python as there is nothing in this code that really takes advantage of functional programming, so a C implementation should be faster still. I guess the algorithm is the win here.


Python by Althalus

Runtime: 110.4 seconds

from primeFunctions import genPrimes
from time import time
import re
from array import array
from copy import copy

start = time()

primes = genPrimes(1000000) # A seive implementation written a while back for use with Euler problems
primes = [array('c',str(x)) for x in primes if x > 99999]

for i in range(0,3):
    for j in range (i+1,4):
       for k in range(i+1,5):
            candidates = []
            for l in [str(l) for l in range(0,10)]:
                candidates += [x for x in primes if x[i] == l and x[j] == l and x[k] == l]
            if len(candidates) > 6:
                #At this point, we have a pool of candidates for the current i and j.
                for c in candidates:
                    c2 =copy(c)
                    c2[i] = '.' 
                    c2[j] = '.' 
                    c2[k] = '.' 
                    p = re.compile(c2.tostring())
                    #print c,c2, sum([1 for x in map(p.match,candidates) if x != None])

                    if sum([1 for x in map(p.match,candidates) if x != None]) == 8:
                        print c
                        print time()-start
                        exit()


Ruby by tomchristmas

A tale of epic proportions!

Runtimes on niflheim:

Version 1: From now until Hell freezes over (estimate)
Version 2: 8 hours, 55 minutes, 12.420 seconds
Version 3: Coming soon

Once upon a time, there was a sprightly young programmer named Tom. Tom loved nothing more than to write computer programs; morning, noon and night. He would forgo meals, sleep, social outings, even offers of intimate congress if they ever arose, just to tackle problems of a particularly difficult nature.

One day, Tom came across such a problem, although due perhaps to his considerable naivete, did not realise at the time just how difficult it would be. There it was; a seemingly simple problem involving prime numbers and combinations. Why no-one in his programming club had solved it yet, or at least published their solution, was quite a mystery to him. Nevertheless, he decided to give it a go, seeing as he had nothing better to do, apart from studying for a couple exams. "No worries, " he said. "I'll have this problem solved in a jiffy!"

Tom began in earnest, writing code to generate primes on the fly, and even gleaning an algorithm from a book (Oliver, pp. 76, 98-102) in the programming club room to generate combinations, shaking his head over the book's copious use of one-indexed arrays in its example algorithms throughout. "It should be using zero-indexed arrays, as used by real programmers such as myself," thought Tom. Sometime later, after a whole lot of debugging and cans of cola, Tom came up with the following code:

def next_prime(p)
   primeFound = false
   q = p

   while not primeFound
	  isDiv = false
         q += 1
         2.upto(q/2){|d| isDiv = ((q % d == 0) || (isDiv == true)) ? true : false } 
         primeFound = true if not isDiv
   end
   q
end

def enumerate(a, n, r)
   b1 = 0
   b2 = 0
   tmp = 0

   lastBit = a[n - 1]
   change = n
   change -= 1 while (a[change - 1] == lastBit)
       
   rightHash = (lastBit == 0) ? n : change

   nextStar = change
   nextStar -= 1 while (nextStar != 0 && a[nextStar - 1] != 1)

   if (r - (n - rightHash)) % 2 == 0
      b1 = change
      b2 = ((change + 1 + lastBit) < n ) ? (change + 1 + lastBit) : n 
   else
      if nextStar == 1
          b1 = 1
          b2 = rightHash
      else
          b1 = nextStar - 1
          b2 = (a[b1 - 1] == 0) ? change + lastBit : rightHash
      end
   end

   tmp = a[b1 - 1]
   a[b1 - 1] = a[b2 - 1]
   a[b2 - 1] = tmp

   a
end

def comb(n, r)
   c = 1.0
   0.upto(r - 1){|x| c = c * ((n - x) / (r - x).to_f)}
   c.to_i
end

def combs(n, r)
   c = []
   s = []

   0.upto(r-1){|x| s << 1}
   r.upto(n-1){|x| s << 0}

   1.upto(comb(n,r)){|x|
	tmp = ""
	0.upto(n - 1){|y| 
         if s[y] == 1 
           tmp << "*"  
         else
           tmp << "#"
         end
        }
       c << tmp
	s = enumerate(s, n, r)
   }
   
   c
end

def prime_patterns(p)
   patterns = []
   (p.length - 1).downto(1){|r|
      combs(p.length, r).each{|c|             
         pp = p.dup
	  0.upto(p.length - 1){|x| pp[x] = c[x] if (c[x].chr == "*")}
         patterns << pp
      }
   }

   patterns
end

prime = 7
prime_family = []

while prime_family.length != 8
     prime_family = []
     prime = next_prime(prime)

     prime_patterns(prime.to_s).each{|pp|
	 if prime_family.length != 8
          prime_family = []
          1.upto(9){|d|
            ppp = pp.dup  
            ppp.gsub!("*", d.to_s)
            prime_family << ppp if (ppp.to_i == next_prime(ppp.to_i - 1))
          }
        end
        puts prime_family.join(",")
     }	
end 

puts "\n Smallest prime and its family: #{prime_family.join(",")}"

Tom was mighty pleased with what he wrote. He took a deep breath and commenced execution of his masterpiece. The terminal screen began to fill with prime numbers in neat little rows, rapidly at first but then slowing down considerably. Tom waited. And waited. And waited some more. Then Tom came to the realisation that maybe - just maybe - his program might be taking longer than it should be to come up with an answer. Nevertheless, he left it to run. "It would be good to give the computer a bit of a prolonged stress test, anyhow," he thought.

Four days later, Tom returned to his computer and, much to his dismay, found that his program was still running, having yet to come up with the set of eight primes he was searching for! He terminated the running program, and reflected on what he had done wrong. "OK, so maybe generating the primes every single time using the division method isn't such a good idea," thought Tom. "Perhaps I should take the Sieve of Eratosthenes approach to the problem. Sure it'll eat up more memory, but at least it'll come up with a solution within a reasonable time frame, I hope. Besides, it's not as if I'm programming on a Commodore VIC-20 with its paltry 5K RAM. Memory's cheap and plentiful these days." So, with that in mind, Tom made a few changes to his program and came up with:

# Executed using: time ( ruby euler51-2.rb 1>&2 ) 2> 51out.txt &

def sieve(c)
   a = []
   b = Array.new(c)
   b[0] = "*"

   d = 2
   while d < c
     (c / d).times{|x| b[((x + 1) * d) + (d - 1)] = "*"}
     d += 1 
   end

   d = 2
   while d < c
     a << d if b[d - 1] == nil
     d += 1
   end

   a
end

def enumerate(a, n, r)
   b1 = 0
   b2 = 0
   tmp = 0

   lastBit = a[n - 1]
   change = n
   change -= 1 while (a[change - 1] == lastBit)
      
   rightHash = (lastBit == 0) ? n : change

   nextStar = change
   nextStar -= 1 while (nextStar != 0 && a[nextStar - 1] != 1)

   if (r - (n - rightHash)) % 2 == 0
      b1 = change
      b2 = ((change + 1 + lastBit) < n ) ? (change + 1 + lastBit) : n 
   else
      if nextStar == 1
          b1 = 1
          b2 = rightHash
      else
          b1 = nextStar - 1
          b2 = (a[b1 - 1] == 0) ? change + lastBit : rightHash
      end
   end

   tmp = a[b1 - 1]
   a[b1 - 1] = a[b2 - 1]
   a[b2 - 1] = tmp

   a
end

def comb(n, r)
   c = 1.0
   0.upto(r - 1){|x| c = c * ((n - x) / (r - x).to_f)}
   c.to_i
end

def combs(n, r)
   c = []
   s = []

   0.upto(r-1){|x| s << 1}
   r.upto(n-1){|x| s << 0}

   1.upto(comb(n,r)){|x|
	tmp = ""
	0.upto(n - 1){|y| 
         if s[y] == 1 
           tmp << "*"  
         else
           tmp << "#"
         end
        }
       c << tmp
	s = enumerate(s, n, r)
   }
   
   c
end

def prime_patterns(p)
   patterns = []
   (p.length - 1).downto(1){|r|
      combs(p.length, r).each{|c|            
         pp = p.dup
	  0.upto(p.length - 1){|x| pp[x] = c[x] if (c[x].chr == "*")}
         patterns << pp
      }
   }

   patterns
end

primes = sieve(999999)
prime_family = []
prime_idx = 0

while prime_family.length != 8 && prime_idx < primes.length
     prime_family = []
     
     prime_patterns(primes[prime_idx].to_s).each{|pp|
	 if prime_family.length != 8
          prime_family = []
          1.upto(9){|d|
            ppp = pp.dup  
            ppp.gsub!("*", d.to_s)
            prime_family << ppp if (primes.index(ppp.to_i) != nil)
          }
        end
        
     }	

     prime_idx += 1
end

puts (prime_family.length == 8) ? "\n Smallest prime and its family: #{prime_family.join(",")}" : "\n Sorry, boy-o, no primes for you!"

Tom commenced execution of the updated program and went to bed.

The next morning, Tom went to his computer as before. This time, however, he was pleased to find that the program had come up with a solution. "Much better!" exclaimed Tom. "But I'm sure I can do even better than this. I mean, do we really need to check every prime? Wouldn't it make more sense just to generate a bunch of patterns and check those for primality?"

Stay tuned for the conclusion to this tale!

Reference

Oliver, I. (1993), Programming Classics: Implementing the World's Best Algorithms, Sydney: Prentice Hall. (ISBN 0-13-100413-1)

Personal tools