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?5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
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))
(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