euler.lisp

;; Project Euler in Common Lisp (specifically SBCL)
;; John Evans <john@jpevans.com>
;; Project Euler Account name: john-sbcl

;; Misc notes for myself:
;; To create an image:
;;     (load "euler.lisp")
;;     (sb-ext:save-lisp-and-die "foo.core")

;; Problem 1
;; Answer: 233168
;;
;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
;; we get 3, 5, 6 and 9. The sum of these multiples is 23.
;;
;; Find the sum of all the multiples of 3 or 5 below 1000.

(defun e1acc (n max acc)
    (if (>= n max)
        acc
        (e1acc (+ n 1)
               max
               (if (or 
                       (= 0 (mod n 3)) 
                       (= 0 (mod n 5)))
                   (+ n acc)
                   acc))))

(defun euler1 ()
    (e1acc 1 1000 0))


;; Problem 2
;; Answer: 4613732
;;
;; Each new term in the Fibonacci sequence is generated by adding the previous 
;; two terms. By starting with 1 and 2, the first 10 terms will be:
;;
;; 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
;; 
;; Find the sum of all the even-valued terms in the sequence which do not 
;; exceed four million.
;; Note: This problem has been changed recently, please check that you are 
;; using the right parameters.

(defun euler2-iter (x y s)
  (if (> y 4000000)
      s
      (if (= (mod y 2) 0)
          (euler2-iter y (+ y x) (+ s y))
          (euler2-iter y (+ y x) s))))


(defun euler2 ()
    (euler2-iter 1 1 0))


;; Euler #3:
;; Answer: 6857
;;
;; The prime factors of 13195 are 5, 7, 13 and 29.
;;
;; What is the largest prime factor of the number 600851475143 ?

(defun prime?-acc (n x)
    (if (or (< x 2) (= n 2))
        't
        (if (= 0 (mod n x))
            nil
            (prime?-acc n (- x 1)))))

(defun prime? (n)
    (prime?-acc n (ceiling (sqrt n))))

(defun euler3-accumulate (factor n)
    (if (and (= 0 (mod n factor)) (prime? factor))
        factor
        (euler3-accumulate (- factor 1) n)))

(defun euler3 ()
    (let ((x 600851475143))
        (euler3-accumulate (ceiling (sqrt x)) x)))


;; Problem #4
;; Answer: 906609
;;
;; A palindromic number reads the same both ways. The largest
;; palindrome made from the product of two 2-digit numbers is 9009 =
;; 91 99.
;;
;; Find the largest palindrome made from the product of two 3-digit
;; numbers.

(defun palindromic-number? (n)
    (let ((s (write-to-string n)))
        (string= s (reverse s))))

(defun euler4-accumulate (x y acc)
    (if (> y 999)
        acc
        (if (> x 999)
            (euler4-accumulate 100 (+ 1 y) acc)
            (let ((p (* x y)))
                (euler4-accumulate (+ 1 x) y (if (and (> p acc) (palindromic-number? p))
                                                  p
                                                  acc))))))

(defun euler4 ()
    (euler4-accumulate 100 100 0))


;; Problem #5
;; Answer: 232792560
;;
;; 2520 is the smallest number that can be divided by each of the
;; numbers from 1 to 10 without any remainder.
;;
;; What is the smallest number that is evenly divisible by all of the
;; numbers from 1 to 20?


(defun euler5-accumulate (acc n)
    (if (> n 20)
        acc
        (euler5-accumulate (lcm acc n) (+ 1 n))))

(defun euler5 ()
    (euler5-accumulate (lcm 1 2) 3))


;; Problem #6
;; Answer: 25164150
;;
;; The sum of the squares of the first ten natural numbers is,
;;     1² + 2² + ... + 10² = 385
;; The square of the sum of the first ten natural numbers is,
;;     (1 + 2 + ... + 10)² = 55² = 3025
;; Hence the difference between the sum of the squares of the first
;; ten natural numbers and the square of the sum is 3025 - 385 = 2640.
;;
;; Find the difference between the sum of the squares of the first one
;; hundred natural numbers and the square of the sum.

(defun square (n)
    (* n n))

(defun range (start end)
    (loop for i from start below end collect i))

(defun sum-xs (xs)
    (if xs
        (+ (car xs) (sum-xs (cdr xs)))
        0))

(defun euler6 ()
    (let ((xs (range 1 101)))
        (- (square (sum-xs xs))
           (sum-xs (mapcar #'square xs)))))


;; Problem #7
;; Answer: 104743
;;
;; By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
;;
;; What is the 10001st prime number?

(defun divisible-by-any? (xs n)
    (if xs
        (if (= (rem n (car xs)) 0)
            't
            (divisible-by-any? (cdr xs) n))
        nil))

(defun next-prime-accumulate (primes n)
    (if (divisible-by-any? primes n)
        (next-prime-accumulate primes (+ 1 n))
        n))

(defun next-prime (primes)
    (next-prime-accumulate primes (+ 1 (car primes))))

(defun nth-prime (n primes)
    (let ((len (length primes)))
        (if (= len n)
            (car primes)
            (if (> len n)
                (nth-prime n (cdr primes))
                (nth-prime n (cons (next-prime primes) primes))))))

(defun euler7 ()
    (nth-prime 10001 '(2)))


;; "Main"

(defconstant *eulers*
    '(#'euler1 
      #'euler2
      #'euler3
      #'euler4
      #'euler5
      #'euler6
      #'euler7))

(defun main ()
   (if (> (length *posix-argv*) 1)
    ;; For each arg, run the appropriate euler
       (loop for arg in (cdr *posix-argv*) do
           (print "would eval here"))
       (loop for euler in *eulers* do
           ; I feel like the eval shouldn't be necessary...
           (print (funcall (eval euler))))))

;; (main)