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.

on February 21, 2009 at 11:43phayesDid you only try the primes between 900 and 1000? I notice the largest prime d < 1000 which generates a d-1 length cyclic (is a full reptend prime) is the 166th prime, 983 – so it must be the right answer – but not all primes do so. All you can say of any prime d is that the length of its reciprocal decimal digit cycle divides d-1. Would your program have been certain to find the right answer if there had been no full reptend primes in that interval?

on February 21, 2009 at 17:02JaredHi Phayes,

No, it wouldn’t have found it if the answer hadn’t been in that range. However, I originally ran it on all the numbers (not just prime) between 2 and 999. It took a few seconds to run and determined the correct result. It wasn’t really necessary to restrict the search to just primes.

I actually solved the problem a few months ago so I forget why I chose a range of 900 to 1000. Could it be because recursion is extremely limited in emacs and it was unable to generate primes from 2 to 999?

on February 21, 2009 at 19:29phayesHi Jared,

(let ((max-lisp-eval-depth 1000)) (primes 2 997))

đź™‚

on February 21, 2009 at 21:55JaredAh yes, I know about that one, and also max-specpdl-size that is also often required at the same time. I probably didn’t know about it when I was trying to solve problem 26 though.

Thanks.

(let ((max-lisp-eval-depth 10000)

(max-specpdl-size 10000))

(length (primes 1 10000)))

on February 22, 2009 at 10:19Rider of GiraffesResearch suggests that Mel was real, and that the incidents recounted did actually happen.

on February 22, 2009 at 18:05JaredHi Rider,

I’d be interested to see that research, but I guess the story isn’t _too_ incredible.

on March 1, 2009 at 17:56Interesting Emacs Links - 2009 Week 9 « A Curious Programmer[…] others, I should also point out my own posts on solving mathematical problems using calc mode and on mapping aliases to dired […]