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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.