Sunday, August 23, 2009

Euler Project 71


Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

My Solution
(defun Euler71(n)
  (let ((constnumber (/ 3 7))
         (currentnumber 0)
         (tempar 0)
         (low 0)
         (high 0)
         (num 0))
    (loop for i from 100000 to n
        do(progn (setq high (ceiling (* i (/ 3 7))))
                      (setq low (- high 200))
                      (loop for j from low to high

  do(progn (setq tempar (/ j i))
                (if (and (= 1 (gcd i j))
                            (> tempar currentnumber)
                            (< tempar constnumber))
                    (progn (setq currentnumber tempar)
                              (incf num)))))))

    currentnumber))

No comments:

Post a Comment