# The prime ant 🐜

The "prime ant" is an obstinate animal that navigates the integers and divides them until there are only primes left!

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  ...
^

Your program should output the ant's position after n moves. (you can assume n <= 10000)

Test cases:

0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512

Edit. you can also use 1-indexed lists, it's acceptable to display the results 1, 7, 10, 275, 513 for the above test case.

This is code-golf, so the code with the shortest code in bytes wins.

• I honestly thought there was an ant on my screen when I saw this in the Hot Network Questions. – Kodos Johnson Oct 9 '17 at 6:09
• 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 '17 at 6:59
• @SuperChafouin so outputs of for the test cases can be: 1,7,10,275,513 if 1-indexing stated? Or would they still need to match your outputs. – Tom Carpenter Oct 9 '17 at 9:22
• @MartinEnder Another open question is whether a prime > 7 can eventually be left behind for good. – Arnauld Oct 9 '17 at 10:39
• @Arnauld Out as far as move n = 1,000,000,000 (where p = 17156661), the relationship between n and p is very close to p = n/(ln(n)*ln(ln(n))) . – Penguino Oct 12 '17 at 3:17

/o

# R, 123 bytes

A straightforward implementation. It is provided as a function, which takes the number of moves as input and returns the position p.

It loops over the sequence and moves the pointer forth and back according to the rules. The output is 0-based.

A note: in order to find the smallest prime factor of a number x, it computes the modulus of x relative to all integers from 0 to x. It then extracts the numbers with modulus equal to 0, which are always [0,1,...,x]. If the third such number is not x, then it is the smallest prime factor of x.

p=function(l){w=0:l;v=w+1;j=1;for(i in w){y=v[j];x=w[!y%%w][3]
if(x%in%c(NA,y))j=j+1
else{v[j]=y/x;j=j-1;v[j]=v[j]+x}}
j-2}

Try it online!

# C (gcc), 152 148 bytes

### Minified

int f(int n){int*A=malloc(++n*4),p=0,i,q;for(i=0;i<n;i++)A[i]=i+2;for(i=1;i<n;i++){for(q=2;A[p]%q;q++);if(A[p++]>q){A[--p]/=q;A[--p]+=q;}}return p;}

int f(int n) {
int *A = malloc(++n * 4), p = 0, i, q;
// Initialize array A
for (i = 0; i < n; i++)
A[i] = i + 2;
// Do n step (remember n was incremented)
for (i = 1; i < n; i++) {
// Find smallest divisor
for (q = 2; A[p] % q; q++)
;
if (A[p++] > q) {
A[--p] /= q;
A[--p] += q;
}
}
return p;
}

### Main function for testing

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
if (argc != 2)
return 2;
int n = atoi(argv[1]);
int p = f(n);
printf("%d => %d\n", n, p);
return 0;
}

### For showing each step

1. Declare display() inside f()

int f(int n) {
int *A = malloc(++n * 4), p = 0, i, q;
void display(void) {
for (int i=0; i < p; i++) {
printf(" %d", A[i]);
}
printf(" \033[1;31m%d\033[m", A[p]);
if (p+1 < n)
printf(" %d", A[p+1]);
printf("\n");
}
...

2. Call display()

A[i] = i + 2;
display();

3. Call display()

}
display();
}

• You can shave off some bytes by declaring A as an array and initializing your loop controls prior to the loops where possible, right? – squid Apr 25 '19 at 15:04

## Clojure, 185 bytes

#(loop[[n p][(vec(range 2 1e3))0]i %](if(= i 0)p(recur(if-let[q(first(for[i(range 2(n p)):when(=(mod(n p)i)0)]i))][(assoc n p(/(n p)q)(dec p)(+(n(dec p))q))(dec p)][n(inc p)])(dec i))))

Ouch, editing a "state" is not ideal in Clojure. You'll need to increase the exponent for larger inputs.

• Why did you use pattern matching in the loop? You should be able to lose a few bytes without that. – clismique Oct 12 '17 at 7:21
• Also, you might be able to change the first thing to a some statement. – clismique Oct 12 '17 at 7:35
• Without pattern matching I had to repeat recur twice, one for each if-let branch. Also (dec i) would be duplicated. some needs a predicate, I could use + as we are dealing with numbers but this is one character longer than first. CMIIW – NikoNyrh Oct 12 '17 at 7:59

# Java 8, 138 135 bytes

n->{int a[]=new int[++n],s=0,p=0,j=0;for(;j<n;a[j++]=j+1);for(;++s<n;p++)for(j=1;++j<a[p];)if(a[p]%j<1){a[p--]/=j;a[p--]+=j;}return p;}

Explanation:

Try it here.

n->{                     // Method with integer as both parameter and return-type
int a[]=new int[++n],  //  Integer-array with a length of n+1
s=0,               //  Steps-counter (starting at 0)
p=0,               //  Current position (starting at 0)
j=0;               //  Index integer (starting at 0)
for(;j<n;              //  Loop (1) from 0 to the input (inclusive due to ++n above)
a[j++]=j+1           //   And fill the array with 2 through n+2
);                     //  End of loop (1)
for(;++s<n;            //  Loop (2) n amount of steps:
p++)               //    And after every iteration: increase position p by 1
for(j=1;             //   Reset j to 1
++j<a[p];)       //   Inner loop (3) from 2 to a[p] (the current item)
if(a[p]%j<1){      //    If the current item is divisible by j:
a[p--]/=j;       //     Divide the current item by j
a[p--]+=j;}      //     And increase the previous item by j
//     And set position p two steps back (with both p--)
//   End of inner loop (3) (implicit / single-line body)
//  End of loop (2) (implicit / single-line body)
return p;              //  Return the resulting position p
}                        // End of method

# Clojure, 198193 191 bytes

This needs to be severely golfed...

#(loop[i(vec(range 2(+ % 9)))c 0 p 0](if(= % c)p(let[d(dec p)u(i p)f(some(fn[n](if(=(mod u n)0)n))(range 2(inc u)))e(= u f)](recur(if e i(assoc i d(+(i d)f)p(/ u f)))(inc c)(if e(inc p)d)))))

Golf 1: Saved 5 bytes by changing (first(filter ...)) to (some ...)

Golf 2: Saved 2 bytes by changing (zero? ...) to (= ... 0)

## Usage:

(#(...) 10000) => 512

## Ungolfed code:

(defn prime-ant [n]
(loop [counter 0
pos 0
items (vec (range 2 (+ n 9)))]
(if (= n counter) pos
(let [cur-item (nth items pos)
prime-factor
(some #(if (zero? (mod cur-item %)) %)
(range 2 (inc cur-item)))
equals? (= cur-item prime-factor)]
(recur
(inc counter)
(if equals? (inc pos) (dec pos))
(if equals? items
(assoc items
(dec pos) (+ (items (dec pos)) prime-factor)
pos (/ cur-item prime-factor))))))))