Feeds:
Posts

## Project Euler and Calc Mode

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.

```(progn
(calc-create-buffer)
(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 ()
(calc-create-buffer)
(calc-select-buffer)
(toggle-truncate-lines 0)
(erase-buffer)
(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.