## 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 = 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

### 8 Responses to “The Prime Ant”

1. David Liu said

In Python:

```import math

def is_prime(a):

for i in range(2, int(math.sqrt(a))+1):
if a%i == 0:
return i
return True

def prime_ant(turns):
p = 0   #Starting index
A = []
for i in range(turns):
A.append(i+2)

for n in range(turns):

q = is_prime(A[p])

if q == True:
p+=1
else:
A[p] = A[p] // q
A[p-1] = A[p-1]+q
p-=1

return p

print(prime_ant(47))
```

Output: 9

2. David Liu said

Update: Cleaned up the code a bit, changed the function name and added some comments for clarity.

```import math

def divisor(a):
# Takes an integer and returns the smallest divisor, or 0 if number is prime

for i in range(2, int(math.sqrt(a))+1):
if a%i == 0:
return i
return 0

def prime_ant(turns):
p = 0   #Starting index
A = list(range(2,turns)) #Generate initial array A

for n in range(turns):

q = divisor(A[p])

if q:
A[p] = A[p] // q
A[p-1] = A[p-1]+q
p-=1
else: p+=1

return p

print(prime_ant(47))
```

Output: 9

3. Paul said

In Python. The array for the ant grows when needed.

```def smallest_factor(n):
for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))):
if not n % f:
return f
if f * f > n:
return n

def prime_ant():
p, A, lenA = 0, , 1
while 1:
yield p
q = smallest_factor(A[p])
if q == A[p]:
if lenA == p+1:  # need to grow array?
A.append(p+2)
lenA += 1
p += 1
else:
A[p] //= q
A[p-1] += q
p -= 1
```
4. ```def is_prime(n, i=3):
if int(n)&1 is 0 and n>2: return False;
while i<n:
if n%i == 0: return False
i += 2
return True;

def div(n, i=2): # return smallest divisor of n, assumes a non-prime number
while n%i: i+=1
return i

def prime_ant(n, p=0, i=0):
A = {}   # use an empty dict
while i < n:
if p not in A: A[p] = 2+p   # set cell item if not set
if is_prime(A[p]):
p += 1
else:
q = div(A[p])
A[p] = A[p]/q
if p-1 not in A: A[p-1] = 2+(p-1)
A[p-1] += q
p -= 1
i += 1
return p

```
5. Update:

```def div(n, i=2):
if n is 2: return 0
while n%i and i < n**0.5: i+=1
return i if n%i is 0 else 0

def prime_ant(n):
A, p, i = {}, 0, 0
while i < n:
if p not in A: A[p] = 2+p
q = div(A[p])
if q is 0:
p += 1
else:
A[p] //= q
if p-1 not in A: A[p-1] = 2+(p-1)
A[p-1] += q
p -= 1
i += 1
return p
```
6. B said

Hi,

Can you explain how you came up with the wheel, and why it works?

Thanks

7. programmingpraxis said
8. B said

@programmingpraxis, thanks!