Project Euler: Problem 6 and Problem 1
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.
As for Problem 1, I couldn’t think of a better way to do this than by brute force. I thought about multiplying 3 and then 5 a bunch of times, but I think a simple brute force will do.
Problem 1
Find the sum of all the multiples of 3 or 5 below 1000.
(defparameter *temp* 0)
(defun problem1 (b)
(loop for x from 1 to (- b 1)
do (cond ((= (mod x 5) 0) (setf *temp* (+ *temp* x)))
((= (mod x 3) 0) (setf *temp* (+ *temp* x)))))
(print *temp*))
Evaluation took:
0.001 seconds of real time
2.15e-4 seconds of user run time
6.1e-5 seconds of system run time
You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
January 2nd, 2008 at 6:35 pm
Interesting take on problem 6. As I said before, I wouldn’t be too concerned about brute force. Half the point is to make the computer do the work for you - and not have to solve everything or come up with equations by hand.
For instance, my solution was pretty much the same as yours for 6 - except i calculated the sosq and sqos in that same loop; as opposed to simply writing the sqos equal to a function. By definition, both of our programs have the same big(O) notation of N. N being the size of that loop - which means they’d run at relatively the same speed.
For comparison my python one seems to run anywhere from 0.000154972076416 seconds to 0.00103902816772 seconds. I also have no idea how to benchmark python, as of now I’m using import time from time and just subtracting the difference.
January 2nd, 2008 at 6:59 pm
Well I was trying to figure out a way to minimize the loop. I know the notation of N is the same but I couldn’t think of a quick fix to get rid of it. (b*b +1)(b*b/2) wasn’t correct.
as for timing I use the built-in TIME function for LISP. But if I were you I would use
$time python2.5 problemx.py
Then you get the system time, otherwise I would be afraid the module time wouldn’t give you accurate results.
I agree though, we would need a way to normalize the computer speed. Then it could be straight comparison, ignoring the compiled/runtime aspect. I still would find it interesting.