Posts Tagged ‘math’

What makes a real programmer1. Well, apart from the ability to write a blackjack program that always wins, I think it is probably someone who actually programs for fun outside of work (novel concept, I know), not necessarily someone who is good at it. I’m not a real programmer, but I do play one occasionally on various blogs.

One of the places I look for fun problems to solve is Project Euler. Actually that isn’t true. I’ve only solved two problems there which gives me a smartness rating of 1%. But what is Project Euler? Fortunately, that is one of the FAQs.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I think problem 26 looks pretty interesting.

Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

How would you solve this problem?

(/ 1.0 7) ;; 0.14285714285714285
(length (format "%s" (/ 1.0 7))) ;; 19

It looks like standard floating point can do around 19 sig figs. That probably isn’t going to be enough, but fortunately emacs has an arbitrary precision calculator built in called calc.

  (calc-precision 30)
  (calc-eval (format "1/7"))) ;; "0.142857142857142857142857142857"

Now all I need to do is find a way to measure how long the recurring cycle is. Having solved it prior to writing the article, I can say a couple of things which I discovered by experimentation at the REPL.

  • There is no 1/d for d < 1000 where the cycle is longer than d – 1.
  • The long cycles are all where d is prime number

The second of these means that I only need to process the prime numbers which will save a lot of calculation effort. The first, leads to a strategy to calculate the cycle.

If I set the precision to, say, 1050, there will always be a cycle. Therefore, all I have to do is take digits 1020 to 1040 or so and figure out where they occurred previously.

(let* ((where (- l 30))
       (pos (string-match (substring r where (+ where 20)) r))
       (diff (- where pos)))

If r contains a string representation of the floating-point ratio, then diff will contain the length of the cycle. This assumes the cycle only occurs once in the string which isn’t necessarily the case. I therefore add a check that an arbitrary 20 digit sequence in the middle of the string occurs at that point for the first time2.

(when (and (> (length r) 600)
           (> (string-match (substring r 501 520) r) 400))

Putting it all together along with a method to get a list of prime numbers gets me this entirely adequate solution. And d is therefore… actually, no I’m not going to tell you. You’ll just have to run the code for yourself.

(require 'calc)
(require 'calc-comb)

(defun primes (from to)
  (let ((p (calcFunc-nextprime (1- from))))
    (if (> p to) '()
      (cons p (primes (1+ p) to)))))

(defun find-ratios ()
  (toggle-read-only 0)
  (toggle-truncate-lines 0)
  (calc-precision 1050)
  (insert "\n\n")
  (dolist (i (primes 900 1000))
    (let* ((r (calc-eval (format "1/%s" i)))
           (l (length r)))
      (when (and (> (length r) 600)
                 (> (string-match (substring r 501 520) r) 400))
        (let* ((where (- l 30))
               (pos (string-match (substring r where (+ where 20)) r)))
          (insert (format "%3d : %s (%s)\n\n" i r (- where pos))))))))

1. Actually, for me, a real programmer is someone real (as opposed to Bugs Bunny for example) who writes programs but it’s always fun to redefine terms isn’t it?

2. Yes, I know that first of all, that is not exactly what the code is doing and second of all it isn’t precise in the least, but hey, I’m an engineer, not a mathematician.


Read Full Post »