Jason Sidabras

So I was not at all happy with my 0.6 second time with the previous iteration. It wasn’t clean, it used two loops and it just wasn’t as smart and beautiful as it could have been. But I have fixed all of that. This program now finds all of the primal roots of any number. And now it finds the answer in 0.004 seconds.

I’ve commented the code to show its beauty.

(defun problem3a (x lst)
  ”Find the prime factors of any number, input number and blank list ()”
  (let ((nextx x))
   ; we know 1 is a prime 2 to nextx
  (loop for i from 2 to nextx
   ; if i is a factor append it to the list
    do (cond ((eq (mod nextx i) 0)
      (setq lst (append lst (multiple-value-list i)))
   ; remove i from the number
      (setq nextx (/ nextx i))
   ; set i back to 1 (i-1 after this loop is done)
      (setq i (- i 1))
   ; if nextx is equal to one you are done, you found all the primes
      (cond ((eq 1 nextx)
        (return nil))))))
  (print lst)))

Read the rest of this entry »

After an extensive amount of research on prime numbers I have finally figured out Problem 3 efficiently. I was going to go about creating a list of prime numbers, but the problem is every equation to generate prime numbers never generates all prime numbers. Just some number of them. Then they all have failures. On-the-other-hand, testing if a number is a prime number is a relatively easy procedure.

Two pieces of knowledge were needed to efficiently solve this problem: i) all numbers can be created by the multiplication of two or more prime numbers and ii) that at most a prime number can be is the square-root of the desired number. These two rules both limited the number of terms in the for loop (ii) and create a stopping rule (i).

Read the rest of this entry »

So I’ve made no attempt to do these problems in order. The first problem I started with was Problem number 6.
Problem 6
What is the difference between the sum of squares and the square of sum?

This problem seemed easy enough, but I wanted to minimize my brute forcing.

;Define variables for sum of squares (*sosq*)
;and square of sum (*sqos*)
(defparameter *sosq* 0)
(defparameter *sqos* 0)
(defun problem6 (b)
   (loop for x from 1 to b
      do (setf *sosq* (+ *sosq* (* x x))))
   (setf *sqos* (* (+ b 1) (/ b 2)))
   (print (abs (- (* *sqos* *sqos*) *sosq*))))

I used a trick that Gauss taught us when he was 12, that the summation of all numbers from 1 to x is (x +1)*(x/2). That was one way to get out of brute forcing the damn thing. It took 0.001 seconds of real time 1.05e-4 seconds of system and user run time.

I think I need to figure out lambda expressions, that might make the programming more interesting.

Read the rest of this entry »

Since all my friends are on the bandwagon, I decided to register at Project Euler. Project Euler is a mathematical challenge website where the use of computer programming and high level mathematics meet to create efficient programs to solve a specific problem.

Project Euler practices the “one-minute rule”, which states that no computer program should run longer than one minute to get the answer. This encourages the programmer to do better than brute force problem and to actually go around and search for ways to better their programs. I expect to take a lot of time on some of the problems so I can learn the more complicated beautiful mathematical solutions to the problems.

I plan on using Lisp for the programming language. I figured one beautiful mathematical expression needs a beautiful programming language, one of which I’ve been dying to learn. I have friends that have chosen python, matlab, haskel and C++. Each person has decided to use a language that they haven’t had much experience in to maximize the fun and challenge of the projects.

The rating method puts you in % genius. Hopefully I will do well. With 175 problems, I will have plenty to work with.

I plan to run this on my G4 PowerBook, but if I need to squeeze out a little more for the one minute rule, i might thread it and run it on my quad-core 3 Ghz Intel workstation at work.

I will be posting my programs for everyone to see. If answers are posted in comments they will be deleted. No spoilers!