Project Euler: Problem 12

Challenge:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Programming Language:

LISP

Solution:

(defparameter *primes* (gen-primes 2000000))
(setq duplicates '())

(defun isprime-p (num)
  (defparameter isprime T)
  (if (= num 2)
      (setq isprime T)
      (if (< 1 num 10)
	  (loop named loop-1 for x from 2 below num
	       do (if (= (mod num x) 0)
		      (progn (setq isprime NIL)
			     (return-from loop-1 NIL))))
	  (if (>= num 10)
	      (loop named loop-2 for x from 2 to (+ (isqrt num) 1)
		 do (if (or (= (mod num x) 0) (= (- (sqrt num) (isqrt num)) 0)) 
			(progn (setq isprime NIL)
			       (return-from loop-2 NIL))))
	      (setq isprime NIL))))
  (print isprime))

(defun gen-primes (how-many)
  (loop for x from 1 to how-many if (isprime-p x) collect x))

(defun list-prime-factors (num *primes*)
  (defparameter prime-factors ())
  (loop while (> num 1)
      do (loop for x in *primes*
	 do (if (eql 0 (mod num x))
		(progn (push x prime-factors)
		       (setq num (/ num x))))))
					;(if prime-factors
					;(print prime-factors))
  )

(defun how-many-factors (num)
  (setq duplicates '())
  (list-prime-factors num *primes*)
  (list-dupes prime-factors)
  (if duplicates
      (* (reduce '* (mapcar (lambda (z) (+ z 1))
			    (loop for y in duplicates for j from 1 if (oddp j) collect y)))
	 (expt 2 (- (list-length prime-factors)
		    (reduce '+ (loop for x in duplicates for i from 1 if (oddp i) collect x)))))
  (expt 2 (list-length prime-factors))))
      

(defun list-dupes (lst)
  ;; Start Counter at 1 because there will always be at least 1 of the item you are looking for.
  (defparameter counter 1)
  (cond ((null lst) ())
	(t (loop for x in (cdr lst)
	      do (if (= (car lst) x)
		     (progn (setq counter (+ counter 1)))))
	   (if (> counter 1)
					;(format t "(~a ~a) " counter (car lst))
	       (setq duplicates (append (list counter (car lst)) duplicates))) 
	   (list-dupes (remove (car lst) (cdr lst))))))

(defun which-tri-num (num)
  (/ (* num (+ num 1)) 2))

(defun list-factors (num)
  (loop for x from 1 to num if (= (mod num x) 0) collect x))
	    
(defun tri-num-with-this-many-factors (limit)
  (defparameter num 1)
  (loop while (< (how-many-factors (which-tri-num num)) limit)
     do (setq num (+ 1 num)))
  (format t "Triangle number ~a is (~a) and it is the first triangle number with ~a factors.~%" num (which-tri-num num) (how-many-factors (which-tri-num num))))

Overview:

Coming soon…