# Does the “prime ant” ever backtrack?

A few mathematical questions have come up from the question "The prime ant 🐜" on the Programming Puzzles & Code Golf Stack Exchange.

Here is how the prime ant is defined:

Initially, we have an infinite array A containing all the integers >= 2 : [2,3,4,5,6,.. ]

Let p be the position of the ant on the array. Initially, p = 0 (array is 0-indexed)

Each turn, the ant will move as follows:

• if A[p] is prime, the ant moves to the next position : p ← p+1
• else, if A[p] is a composite number, let q be its smaller divisor > 1. We divide A[p] by q, and we add q to A[p-1]. The ant moves to the previous position: p ← p-1

Here are the first moves for the ant:

 2  3  4  5  6  7  8  9  ...
^
2  3  4  5  6  7  8  9  ...
^
2  3  4  5  6  7  8  9  ...
^
2  5  2  5  6  7  8  9  ...
^
2  5  2  5  6  7  8  9  ...
^
2  5  2  5  6  7  8  9  ...
^
2  5  2  5  6  7  8  9  ...
^
2  5  2  7  3  7  8  9  ...
^


Questions relate to proving the sequence is well-defined:

I wonder whether the sequence is well-defined for arbitrarily large n (or whether the composite case could ever push the ant to the left of the initial 2). – Martin Ender♦ Oct 9 at 6:59

Whether all prime values appear:

@MartinEnder Another open question is whether a prime > 7 can eventually be left behind for good. – Arnauld Oct 9 at 10:39

And what the asymptotic growth looks like:

@Arnauld I'm curious how the ant's position grows with respect to the number of moves. My guess is logarithmic. – kamoroso94 Oct 9 at 12:58

I have added this sequence to the On-Line Encylopedia of Integer Sequences (OEIS) as sequence A293689. Here's what the plot of the first 10000 terms looks like:

• Code Golf Stack Exchange User Penguino said in a comment that $a(10^9) = 17156661$, and suggested that $a(n) \approx \frac{n}{\ln(n)\ln(\ln(n))}$. – Peter Kagey Oct 24 '17 at 6:40
• What as $a(n)$? The position after $n$ moves? – Neal Young Oct 24 '17 at 21:32
• Yes, thanks for clarifying @NealYoung. – Peter Kagey Oct 24 '17 at 21:38