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[0] = 2.
At each turn, the ant moves as follows:
- If A[p] is prime, move the ant one position forward, so p ← p + 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 p ← p − 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.
Programming Praxis 
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
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
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, [2], 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 -= 1def 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 pUpdate:
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 pHi,
Can you explain how you came up with the wheel, and why it works?
Thanks
@B: See https://programmingpraxis.com/2009/05/08/wheel-factorization/.
@programmingpraxis, thanks!