## The Prime Ant

### October 27, 2017

This is a simple matter of following the rules of the game:

(define (prime-ant n . verbose?) (let ((a (make-vector (+ n 2)))) (do ((i 0 (+ i 1))) ((= (+ n 2) i)) (vector-set! a i (+ i 2))) (let loop ((n n) (p 0)) (when (and (pair? verbose?) (equal? (car verbose?) #t)) (display a) (display " ") (display p) (newline)) (if (zero? n) p (if (prime? (vector-ref a p)) (loop (- n 1) (+ p 1)) (let ((q (lpf (vector-ref a p)))) (vector-set! a p (/ (vector-ref a p) q)) (vector-set! a (- p 1) (+ (vector-ref a (- p 1)) q)) (loop (- n 1) (- p 1))))))))

We make use of two auxiliary functions: `lpf`

returns the least prime factor of *n*, and `prime?`

returns `#t`

if and only if the least prime factor of *n* is *n*:

(define (lpf n) ; least prime factor (let ((wheel '#(1 2 2 4 2 4 2 4 6 2 6))) (let loop ((f 2) (w 0)) (if (< n (* f f)) n (if (zero? (modulo n f)) f (loop (+ f (vector-ref wheel w)) (if (= w 10) 3 (+ w 1)))))))) (define (prime? n) (= (lpf n) n))

Here are two examples:

> (prime-ant 20 #t) #(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 0 #(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 1 #(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2 #(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 1 #(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2 #(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3 #(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4 #(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3 #(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4 #(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5 #(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6 #(2 5 2 7 3 9 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5 #(2 5 2 7 6 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4 #(2 5 2 9 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3 #(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2 #(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3 #(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4 #(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5 #(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6 #(2 5 5 3 3 5 2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5 #(2 5 5 3 3 5 2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6 6 > (prime-ant 47) 9

If it works forever, the prime ant will convert the entire array *A* to contain prime numbers. You can run the program at https://ideone.com/dok8t1.

Advertisements

In Python:

Output: 9

Update: Cleaned up the code a bit, changed the function name and added some comments for clarity.

Output: 9

In Python. The array for the ant grows when needed.

Update:

Hi,

Can you explain how you came up with the wheel, and why it works?

Thanks

@B: See https://programmingpraxis.com/2009/05/08/wheel-factorization/.

@programmingpraxis, thanks!