What makes a *real programmer*^{1}. 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 time^{2}.

```
(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-read-only 0) (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.