## The Prime Ant

### October 27, 2017

The *prime ant* (A293689) is an obstinate animal that navigates the integers and divides them until there are only primes left, according to the following procedure:

An infinite array *A* is initialized to contain all the integers greater than 1: [2, 3, 4, 5, 6, …].

Let *p* be the position of the ant on the array. Initially *p* = 0, so the ant is at *A*[0] = 2.

At each turn, the ant moves as follows:

- If
*A*[*p*] is prime, move the ant one position forward, so*p*←*p*+ 1. - Otherwise (if
*A*[*p*] is composite), let*q*be its smallest divisor greater than 1. Replace*A*[*p*] with*A*[*p*] ÷*q*. Replace*A*[*p*−1] with*A*[*p*−1] +*q*. Move the ant one position backward, so*p*←*p*− 1.

Your task is to write a program that computes the position of the prime ant after *n* turns; for instance, after 47 turns the prime ant will be at *p* = 9. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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!