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. on February 21, 2009 at 11:43 phayes

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. on February 21, 2009 at 17:02 Jared

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. on February 21, 2009 at 19:29 phayes

Hi Jared,

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

🙂

4. on February 21, 2009 at 21:55 Jared

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. on February 22, 2009 at 18:05 Jared

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 […]