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.

### 7 Responses

1. Did 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?

2. Hi 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?

3. Hi Jared,

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

4. Ah 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)))

5. on February 22, 2009 at 10:19 Rider of Giraffes

Research suggests that Mel was real, and that the incidents recounted did actually happen.

6. Hi Rider,

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

7. [...] others, I should also point out my own posts on solving mathematical problems using calc mode and on mapping aliases to dired [...]