Wednesday, September 9, 2009

Euler Project 77


It is possible to write ten as the sum of primes in exactly five different ways:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?


My Solution Using Mathematica
MyPrimesList = Table[Prime[i], {i, PrimePi[10000]}]

For[i = 2, i < 1000000, i++, 
 If[Length[IntegerPartitions[i, All, MyPrimesList]] > 5000, Print[i]; Break[]]]

Others' Solutions
First Solutions
(defun sieve (lst)
(let ((primes '())
(last (car (last lst))))
(loop while (and lst (> last (* (car lst) (car lst))))
do (let ((factor (car lst)))
(setq primes (cons factor primes))
(setq lst (remove-if
#'(lambda (n)
(= (mod n factor) 0))
(cdr lst)))))
(append (reverse primes) lst)))

(defun seq-list (min max)
(loop for i from min to max collect i))

(defun all-primes (limit)
(sieve (seq-list 2 limit)))

(defun fill-partitions-hash (max)
(setq partitions-hash (make-hash-table :test 'equal))
(setf (gethash (list 0 0) partitions-hash) 1)
(setf (gethash (list 1 1) partitions-hash) 0)
(loop for n from 1 to max
do (fill-partitions-helper n n)))

(defun fill-partitions-helper (n max)
(let ((memo (gethash (list n max) partitions-hash)))
(if memo
memo
(loop for i in all-primes
while (<= i max)
sum (fill-partitions-helper (- n i) (min i (- n i) max)) into p
finally (return (setf (gethash (list n max) partitions-hash) p))))))

(defun euler77 ()
(setq all-primes (all-primes 100))
(fill-partitions-hash 10)
(loop for i from 10
do (fill-partitions-helper i i)
if (> (gethash (list i i) partitions-hash) 5000)
return i)) 


Second Solution
Length@IntegerPartitions[n, n, Prime@Range@n]

Third Solution
(defun init-counts-table (n) 
    (let ((table (make-array (1+ n) :initial-element 0))) 
     table))
  
(defun update-counts-table! (table i n) 
    (incf (aref table i) 1) 
    (iterate loop ((c (+ 2 i))) 
        (unless (> c n) 
            (setf (aref table c) (lengthened-row-size table i c)) 
            (loop (1+ c)))))
  

(defun lengthened-row-size (table i c) 
    (let ((row-c (aref table c)) 
          (row-c-i (aref table (- c i)))) 
        (+ row-c-i row-c)))
  

(defun my-partition-counts.2 (n) 
    (let ((primes-vec (array-of-primes n)) 
          (table (init-counts-table n))) 
        (iterate loop ((i 0)) 
            (if (< i (array-dimension primes-vec 0)) 
                (let ((p (aref primes-vec i))) 
                    (update-counts-table! table p n) 
                    (loop (1+ i))))) 
        (aref table n)))

No comments:

Post a Comment