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 pp + 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 pp − 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