12
$\begingroup$

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:

Plot for OEIS sequence A293689

$\endgroup$
  • $\begingroup$ 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))}$. $\endgroup$ – Peter Kagey Oct 24 '17 at 6:40
  • $\begingroup$ What as $a(n)$? The position after $n$ moves? $\endgroup$ – Neal Young Oct 24 '17 at 21:32
  • $\begingroup$ Yes, thanks for clarifying @NealYoung. $\endgroup$ – Peter Kagey Oct 24 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.