Project Euler Problem 12 Common Lisp

Project Euler Problem 12

For function problem12, every time it loops, it calculates the next triangle number (i).  It keeps looping until it reaches a triangle number that has over 500 factors.

(defun how-many-factors? (num)
  (* 2 (loop for i from 1 to (isqrt num)
             if (zerop (mod num i))
             count i)))

(defun problem12 ()
  (loop for i = 1 then (+ i j)
        and j upfrom 2
        when (> (how-many-factors? i) 500)
        return i))

Project Euler Problem 10 Common Lisp

Project Euler Problem 10

(defun prime? (num)
  (flet ((multiple? (a b) (zerop (mod a b))))
    (cond ((evenp num) (= 2 num))
          ((< num 2) nil)
          ((multiple? num 3) (= 3 num))
          ((loop for i from 5 to (isqrt num) by 6
                 never (or (multiple? num i)
                           (multiple? num (+ i 2))))))))

(defun problem10 ()
  (loop for i below 2000000
        if (prime? i) sum i))

Project Euler Problem 9 Common Lisp

Project Euler Problem 9

This solution uses Dickson's method for generating Pythagorean triples and involved only two loops whereas other solutions seen used 3 loops with the Pythagorean equation to find a, b, and c.  Note the two loops make sure that m is always greater than n. 


(defun problem9 ()
  (loop for m from 1 below 1000
        do (loop for n from 1 below m
                 for m2 = (* m m)
                 for n2 = (* n n)
                 for a = (- m2 n2)
                 for b = (* 2 m n)
                 for c = (+ m2 n2)
                 if (= 1000 (+ a b c))
                 do (return-from problem9 (* a b c)))))

Project Euler Problem 8 Common Lisp

Project Euler Problem 8

(defparameter *num*
  '(73167176531330624919225119674426574742355349194934
    96983520312774506326239578318016984801869478851843
    85861560789112949495459501737958331952853208805511
    12540698747158523863050715693290963295227443043557
    66896648950445244523161731856403098711121722383113
    62229893423380308135336276614282806444486645238749
    30358907296290491560440772390713810515859307960866
    70172427121883998797908792274921901699720888093776
    65727333001053367881220235421809751254540594752243
    52584907711670556013604839586446706324415722155397
    53697817977846174064955149290862569321978468622482
    83972241375657056057490261407972968652414535100474
    82166370484403199890008895243450658541227588666881
    16427171479924442928230863465674813919123162824586
    17866458359124566529476545682848912883142607690042
    24219022671055626321111109370544217506941658960408
    07198403850962455444362981230987879927244284909188
    84580156166097919133875499200524063689912560717606
    05886116467109405077541002256983155200055935729725
    71636269561882670428252483600823257530420752963450))

(defun digits-to-list (x &optional (lst nil))
  (multiple-value-bind (a b)
      (truncate x 10)
    (if (zerop a)
      (cons b lst)
      (digits-to-list a (cons b lst)))))

(defun problem8 ()
  (loop for i on (mapcan #'digits-to-list *num*)
        when (<= 13 (length i))
        maximizing (reduce #'* (subseq i 0 13))))

Project Euler Problem 7 Common Lisp

Project Euler Problem 7

(defun prime? (num)
  (flet ((multiple? (a b) (zerop (mod a b))))
    (cond ((evenp num) (= 2 num))
          ((< num 2) nil)
          ((multiple? num 3) (= 3 num))
          ((loop for i from 5 to (isqrt num) by 6
                 never (or (multiple? num i)
                           (multiple? num (+ i 2))))))))

(defun problem7 ()
  (loop for i upfrom 0
        when (prime? i) count i into prime-tally
        when (= prime-tally 10001) return i))

Project Euler Problem 6 Common Lisp

Project Euler Problem 6

(defun problem6 ()
  (loop for i from 1 to 100
        sum i into sqr-sums
        sum (* i i) into sum-sqrs
        finally (return (- (expt sqr-sums 2) sum-sqrs))))

Project Euler Problem 5 Common Lisp

Project Euler Problem 5

You can solve this by creating a loop that increments by 20 (20, 40 60, etc.) and then see if every increment is divisible by all the numbers from 1 to 19.   You can improve this even further by not bothering to see if every increment is divisible by 1 to 10 because if the increment is divisible by 20, 18, 16, and 14 then it's divisible by all the numbers from 1 to 10.  And finally you can improve it even further by incrementing by a number equal to 20 * 19 * 17 * 13 * 11 which is 923780.  What is special about 19, 17, 13, and 11 is that they are prime numbers.  So that just leaves incrementing by 923780 and seeing if the increment is divisible by 18, 16, 15, 14, and 12.


(defconstant +inc+ (* 20 19 17 13 11))

(defun problem5 ()
  (loop for i upfrom +inc+ by +inc+
        if (every #'(lambda (j) (zerop (mod i j)))
                  '(18 16 15 14 12))
        return i))

 Another solution inspired by Haskell.

(lcm 20 19 18 17 16 15 14 13 12 11)

Project Euler Problem 4 Common Lisp

Project Euler Problem 4

Solutions I've seen for this problem use 2 loops that will multiply every number in both loops.  For example, 2 loops with numbers from 4 to 1:

   4  3 2 1
4 16 12 8 4
3 12  9 6 3
2  8  6 4 2
1  4  3 2 1

The two loops in the below solution cuts this almost in half.  For example:

   4  3 2 1
4 16 12 8 4
3     9 6 3
2       4 2
1         1

Now the code:

(defun digits-to-list (x &optional (lst nil))
  (multiple-value-bind (a b)
      (truncate x 10)
    (if (zerop a)
      (cons b lst)
      (digits-to-list a (cons b lst)))))

(defun problem4 ()
  (loop for i from 999 downto 100
        maximizing (loop for j from i downto 100
                         for mult = (* i j)
                         for lst = (digits-to-list mult)
                         if (equal lst (reverse lst))
                         maximizing mult)))

Project Euler Problem 3 Common Lisp

Project Euler Problem 3

The factors function will return a list of all the factors of a number in descending order.  The function problem3 creates a list of all the factors of 600851475143 using the factor function.  With this list, the factor function is applied again to each element.  The first element found, where the factor function returns a single element list with that element having the value of 1, is returned because it's prime.

(defun factors (num)
  (loop for i from (isqrt num) downto 1
        if (zerop (mod num i))
        collect i))

(defun problem3 ()
  (find '(1) (factors 600851475143) :test #'equal :key #'factors))

Project Euler Problem 2 Common Lisp

Project Euler Problem 2

(defun problem2 ()
  (loop for (a b) = '(0 1) then `(,b ,(+ a b))
        while (<= a 4000000)
        when (evenp a)
          sum a))

Project Euler Problem 1 Common Lisp

Project Euler Problem 1 

The idea here is to solve Problem 1 without using a modulus operator which I take to be more expensive than using addition and if.  So it adds every multiple of 5 except every third multiple, e.g., 5 + 10 + skip + 20 + 25 + skip.

(defun problem1 ()
  (+
    (loop for i from 3 below 1000 by 3 sum i)
    (loop for j from 5 below 1000 by 5
          and k = 1 then (if (= k 3) 1 (1+ k))
          unless (= k 3) sum j)))

There's a more efficient way to solve this without using a loop, but I didn't know about it until after I solved this, so at this point, for me, I consider it cheating.

Another solution avoiding a modulus operator but probably not any more efficient:

(defun problem1 ()
  (reduce #'+
          (union (loop for i below 1000 by 3 collect i)
                 (loop for i below 1000 by 5 collect i))))