Programming Praxis

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.

Pages: 1 2