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

Advertisements

Pages: 1 2

3 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, [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 -= 1
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: