Programming Praxis

8 Responses to “The Prime Ant”

1. David Liu said

   October 28, 2017 at 3:09 AM

   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

   October 28, 2017 at 5:15 AM

   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

   October 28, 2017 at 7:18 AM

   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
   
4. Sochima Biereagu, KodeJuice said

   December 9, 2017 at 5:13 PM

   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. Sochima Biereagu, KodeJuice said

   December 9, 2017 at 6:12 PM

   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

   December 23, 2017 at 3:45 AM

   Hi,

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

   Thanks
7. programmingpraxis said

   December 23, 2017 at 2:53 PM

   @B: See https://programmingpraxis.com/2009/05/08/wheel-factorization/.
8. B said

   December 23, 2017 at 9:50 PM

   @programmingpraxis, thanks!