The prime ant 🐜

Question

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. — Cave Johnson, Commented Oct 9, 2017 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, Commented Oct 9, 2017 at 6:59
@MartinEnder Another open question is whether a prime > 7 can eventually be left behind for good. — Arnauld, Commented Oct 9, 2017 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, Commented Oct 12, 2017 at 3:17
I added this sequence to the On-Line Encylopedia of Integer Sequences as sequence A293689. The graph is worth looking at. — Peter Kagey, Commented Oct 19, 2017 at 4:39

Nitrodon · Accepted Answer · 2017-10-09 05:28:07Z

Alice, 45 bytes

/o
\i@/.&wqh!]k.&[&w;;?c]dt.n$k&;[.?~:![?+!kq

Try it online!

Mostly straightforward implementation.

Looping n times in Alice is typically done by pushing a return address n-1 times, then returning at the end of each iteration with k. The last time through the loop, the k instruction has nowhere to return to, and execution proceeds forward.

This program uses the same k instruction to stop early when the number is prime. As a result, the final iteration will always move the ant left. To compensate for this bug, we do n+1 iterations on a 1-indexed array, which gives exactly the result we want (and gives the case n=0 for free).

lynn · Accepted Answer · 2017-10-09 16:27:20Z

7

Python 2, 120 bytes

p=0
A=range(2,input()+2)
for _ in A:
 for q in range(2,A[p]):
	if A[p]%q<1:A[p]/=q;p-=1;A[p]+=q;break
 else:p+=1
print p

Try it online!

Ah, the rare for–else loop! The else clause only executes if the for body is not exited via break. In our case, this means we checked all qs and found none of them to divide p.

answered Oct 9, 2017 at 16:27

lynn

69k11 gold badges133 silver badges282 bronze badges

Add a comment |

Tom Carpenter · Accepted Answer · 2017-10-20 10:13:00Z

Octave, 109 103 101 94 bytes

function i=a(n)i=1;for l=z=2:n+1
if nnz(q=factor(z(i)))>1
z(i--)/=p=q(1);z(i--)+=p;end
i++;end

Try it online!

This code will output the position in 1-indexing, so outputs for test cases are:

0 => 1
10 => 7
47 => 10
4734 => 275
10000 => 513

This version uses some Octave optimisations so isn't compatible with MATLAB. The code below is a MATLAB compatible version.

MATLAB, 130 123 118 117 bytes

function i=a(n)
z=2:n+1;i=1;for l=z
q=factor(z(i));if nnz(q)>1
z(i)=z(i)/q(1);i=i-1;z(i)=z(i)+q(1);else
i=i+1;end
end

Uses 1-indexing as with the Octave version. I've tested it against all test cases in MATLAB. As an example the output at 100000 is 3675 (one-indexing).

An commented version of the above code:

function i=a(n)
    z=2:n+1;                %Create our field of numbers
    i=1;                    %Start of at index of 1 (MATLAB uses 1-indexing)
    for l=1:n               %For the required number of iterations
        q=factor(z(i));     %Calculate the prime factors of the current element
        if nnz(q)>1         %If there are more than one, then not prime
            z(i)=z(i)/q(1); %So divide current by the minimum
            i=i-1;          %Move back a step
            z(i)=z(i)+q(1); %And add on the minimum to the previous.
        else
            i=i+1;          %Otherwise we move to the next step
        end
    end

As a matter of interest, this is the ants positions vs number of iterations for the first 10000 values of n.

Seems likely that the Ant will probably tend to infinity, but who knows, looks can be deceiving.

MATLAB: Saved 6 bytes with for instead of while and removing brackets from if - Thanks @Giuseppe
MATLAB: Save 2 bytes - Thanks @Sanchises
Octave: Save 10 bytes by using Octave \= and += operations - Thanks @Giuseppe
Octave: Save 2 bytes with i++ and i-- - Thanks @LuisMendo
Octave: Save 7 bytes - Thanks @Sanchises

To get it to work on TIO, I think you need an end to match the function signature — Giuseppe, Commented Oct 9, 2017 at 11:12
you can make anonymous function by using @(n) at the start instead of using function i=a(n) — Michthan, Commented Oct 9, 2017 at 11:39
@Michthan can't do that in MATLAB. I don't think it is possible in Octave either as it has loops? — Tom Carpenter, Commented Oct 9, 2017 at 11:44
The trailing end is optional in Octave too. Here it is only needed because you have code after the function — Luis Mendo, Commented Oct 9, 2017 at 11:52

Arnauld · Accepted Answer · 2017-10-09 07:12:08Z

6

JavaScript (ES6), 91 bytes

f=(n,a=[p=0])=>n--?f(n,a,(P=n=>++x<n?n%x?P(n):a[a[p]/=x,--p]+=x:p++)(a[p]=a[p]||p+2,x=1)):p

Demo

NB: You may have to increase the default stack size of your engine to have it pass all test cases.

Try it online!

edited Oct 9, 2017 at 7:12

answered Oct 9, 2017 at 6:18

Arnauld

195k20 gold badges178 silver badges644 bronze badges

Add a comment |

Laikoni · Accepted Answer · 2017-10-10 06:42:36Z

Haskell, 108 106 94 bytes

([0]#[2..]!!)
(a:b)#(p:q)=length b:([b#(a+d:div p d:q)|d<-[2..p-1],mod p d<1]++[(p:a:b)#q])!!0

Try it online! Example usage: ([0]#[2..]!!) 10 yields 6 (0-indexed).

The function # operates on two list, the reversed front of the array [p-1, p-2, ..., 1] and the infinite rest of the array [p, p+1, p+2, ...]. It constructs an infinite list of positions, from which the nth position is returned given an input n.

The pattern ((a:b)#(p:q)) binds p to the value of the current position of the ant and a to the value a the previous position. b is the prefix of the array from position 1 to p-2 and q the infinite rest starting from position p+1.

We construct a list of recursive calls in the following way: We look at each divisor d of p (which is larger than one and smaller than p) in ascending order and add b#(a+d:div p d:q) for each of them, that is the current value p is divided by d and the ant moves one step to the left where d is added to a. Then we append (p:a:b)#q to the end of this list, which indicates the ant moving one step to the right.

We then take the first of those recursive calls from the list and prepend the current position, which coincides with the length of the prefix list b. Because the divisors are in ascending order, picking the first from the list of recursive calls ensures we use the smallest one. Additionally, because (p:a:b)#q is added to the end of the list, it is only selected if there are no divisors and p is thus prime.

Edits:
-2 bytes by switching the list of functions from descending to ascending order.
-12 bytes thanks to Zgarb's idea to index into an infinite list instead handling a counter, and by switching to 0-indexing.

96 bytes by building an infinite list and indexing, instead of carrying around the counter. — Zgarb, Commented Oct 9, 2017 at 15:17
@Zgarb Thanks a lot! It's even only 94 bytes when switching to 0-indexing. — Laikoni, Commented Oct 10, 2017 at 6:30

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

TI-BASIC, 108 103 102 98 bytes

Input and output are stored in Ans. Output is 1-indexed.

Ans→N
seq(X,X,2,9³→A
1→P
For(I,1,N
1→X:∟A(P→V
For(F,2,√(V
If X and not(fPart(V/F:Then
DelVar XV/F→∟A(P
P-1→P
F+∟A(P→∟A(P
End
End
P+X→P
End

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 9, 2017 at 12:37

kamoroso94

7995 silver badges9 bronze badges

\$\begingroup\$ You can take a byte off of fPart(∟A(P)/F: with fPart(F¹∟A(P:. Same thing in the next line. \$\endgroup\$
– Scott Milner
Commented Oct 11, 2017 at 0:51
\$\begingroup\$ @ScottMilner That doesn't always work. not(fPart(7⁻¹7 is 0 but not(fPart(7/7 is 1. \$\endgroup\$
– kamoroso94
Commented Oct 11, 2017 at 1:18

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

MATL, 41 bytes

:Q1y"XHyw)Zp?5MQ}1MtYf1)/H(8MyfHq=*+9M]]&

Output is 1-based. The program times out for the last test case in the online interpreter.

Try it online!

Explanation

The program applies the procedure as described in the challenge. To do so, it makes unusually heavy use of MATL's manual and automatic clipboards.

The smallest divisor is obtained as the first entry in the prime factor decomposition.

The "divide" update is done by overwriting the corresponding entry of array A. The "add" update is done by element-wise adding to A an array that contains zeros except at the desired position.

:Q        % Implicitly input n. Push array [2 3 ... n+1]. This is the initial array A. 
          % It contains all required positions. Some values will be overwritten
1         % Push 1. This is the initial value for p
y         % Duplicate from below
"         % For each loop. This executes the following n times.
          %   STACK (contents whosn bottom to top): A, p
  XH      %   Copy p into clipboard H
  y       %   Duplicate from below. STACK: A, p, A
  w       %   Swap. STACK: A, A, p
  )       %   Reference indexing. STACK: A, A[p]
  Zp      %   Isprime. STACK: A, false/true
  ?       %   If true (that is, if A[p] is prime)
    5M    %     Push p from automatic clipboard. STACK: A, p
    Q     %     Add 1. STACK: A, p+1
  }       %   Else (that is, if A[p] is not prime)
    1M    %     Push A[p] from automatic clipboard. STACK: A, A[p]
    t     %     Duplicate. STACK: A, A[p], A[p]
    Yf    %     Prime factors, with repetitions. STACK: A, A[p], prime factors of A[p]
    1)    %     Get first element, d. STACK: A, A[p], d
    /     %     Divide. STACK: A, A[p]/d
    H     %     Push p from clipboard H. STACK: A, A[p]/d, p
    (     %     Assignment indexing: write value. STACK: A with A[p] updated
    8M    %     Push d from automatic clipboard.
    y     %     Duplicate from below. STACK: A with A[p] updated, d, A with A[p] updated
    f     %     Find: push indices of nonzero entries.
          %     STACK: A with A[p] updated, d, [1 2 ... n]
    Hq    %     Push p from clipboard H, subtract 1.
          %     STACK: A with A[p] updated, d, [1 2 ... n], p-1
    =     %     Test for equality, element-wise.
          %     STACK: A with A[p] updated, d, [0 ... 0 1 0 ... 0]
    *     %     Multiply, element-wise. STACK: A with A[p] updated, [0 ... 0 d 0 ... 0]
    +     %     Add, element-wise. STACK: A with A[p-1] and A[p] updated
    9M    %     Push p-1 from automatic clipboard.
          %     STACK: A with A[p-1] and A[p] updated, p-1
  ]       %   End if. The stack contains the updated array and index
]         % End for each. Process the next iteration
&         % Specify that the following implicit display function should display only
          % the top of the stack. Implicitly display

Community · Accepted Answer · 2020-06-17 09:04:33Z

PARI/GP, 87 bytes

f(n)=A=[2..9^5];p=1;for(i=1,n,q=factor(A[p])[1,1];if(A[p]-q,A[p]/=q;p--;A[p]+=q,p++));p

Pretty self-explanatory (not so golf-ish). If you do not count the f(n)= part, that is 82 bytes. You can also start by n-> (85 bytes).

It is a 1-indexed language.

Edit: The modification illustrate(n,m)=A=[2..m+1];p=1;for(i=1,n,for(j=1,m,printf("%5s",if(j==p,Str(">",A[j],"<"),Str(A[j]," "))));print();q=factor(A[p])[1,1];if(A[p]!=q,A[p]/=q;p--;A[p]+=q,p++)) will print an illustration of the ant's walk (given a wide enough terminal). For example illustrate(150,25) will give the first 150 steps on 25 columns, like this:

  >2<   3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2   >3<   4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    3   >4<   5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2   >5<   2    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5   >2<   5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2   >5<   6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    5   >6<   7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2   >7<   3    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    7   >3<   7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    7    3   >7<   8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    7    3    7   >8<   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    7    3   >9<   4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2    7   >6<   3    4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    2   >9<   3    3    4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5   >5<   3    3    3    4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5   >3<   3    3    4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3   >3<   3    4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3   >3<   4    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    3   >4<   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3   >5<   2    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5   >2<   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    2   >9<  10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5   >5<   3   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5   >3<  10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    3  >10<  11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5   >5<   5   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5   >5<  11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5    5  >11<  12   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5    5   11  >12<  13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5    5  >13<   6   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5    5   13   >6<  13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5    5  >15<   3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    5   >8<   5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5   >7<   4    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5    7   >4<   5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5    5   >9<   2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    5   >8<   3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3   >7<   4    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3    7   >4<   3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3    3   >9<   2    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    3   >6<   3    2    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5   >5<   3    3    2    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5   >3<   3    2    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3   >3<   2    3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3   >2<   3    2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2   >3<   2    5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3   >2<   5    3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2   >5<   3   13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    5   >3<  13   14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    5    3  >13<  14   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    5    3   13  >14<  15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    5    3  >15<   7   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    5   >6<   5    7   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2   >7<   3    5    7   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7   >3<   5    7   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3   >5<   7   15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    5   >7<  15   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    5    7  >15<  16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    5  >10<   5   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3   >7<   5    5   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7   >5<   5   16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7    5   >5<  16   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7    5    5  >16<  17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7    5   >7<   8   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7    5    7   >8<  17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7    5   >9<   4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3    7   >8<   3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7    3   >9<   4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2    7   >6<   3    4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    2   >9<   3    3    4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3   >5<   3    3    3    4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5   >3<   3    3    4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3   >3<   3    4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3   >3<   4    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    3   >4<   3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3   >5<   2    3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5   >2<   3    4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2   >3<   4   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    3   >4<  17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2   >5<   2   17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5   >2<  17   18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5    2  >17<  18   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5    2   17  >18<  19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5    2  >19<   9   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5    2   19   >9<  19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5    2  >22<   3   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    5   >4<  11    3   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2   >7<   2   11    3   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7   >2<  11    3   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2  >11<   3   19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   11   >3<  19   20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   11    3  >19<  20   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   11    3   19  >20<  21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   11    3  >21<  10   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   11   >6<   7   10   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2  >13<   3    7   10   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   13   >3<   7   10   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   13    3   >7<  10   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   13    3    7  >10<  21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   13    3   >9<   5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2   13   >6<   3    5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    2  >15<   3    3    5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7   >5<   5    3    3    5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5   >5<   3    3    5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5   >3<   3    5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3   >3<   5   21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    3   >5<  21   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    3    5  >21<  22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    3   >8<   7   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3   >5<   4    7   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    5   >4<   7   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3   >7<   2    7   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7   >2<   7   22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    2   >7<  22   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    2    7  >22<  23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    2   >9<  11   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7   >5<   3   11   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5   >3<  11   23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    3  >11<  23   24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    3   11  >23<  24   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    3   11   23  >24<  25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    3   11  >25<  12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    3  >16<   5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5   >5<   8    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    5   >8<   5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5   >7<   4    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5    7   >4<   5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7    5   >9<   2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3    7   >8<   3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5    3   >9<   4    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    5   >6<   3    4    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5   >7<   3    3    4    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7   >3<   3    4    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3   >3<   4    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    3   >4<   3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3   >5<   2    3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5   >2<   3    2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2   >3<   2    5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3   >2<   5   12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    2   >5<  12   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    2    5  >12<  25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    2   >7<   6   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    2    7   >6<  25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    2   >9<   3   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3   >5<   3    3   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    5   >3<   3   25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    5    3   >3<  25   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    5    3    3  >25<  26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    5    3   >8<   5   26
   2    5    5    5    3    3    2    3    5    3    3    5    2    7    5    7    3    5    2    3    5   >5<   4    5   26

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Pyth - 44 bytes

Straightforward procedural implementation.

K}2hhQVQJ@KZIP_J=hZ).?=GhPJ XKZ/JG=tZ XZKG;Z

Test Suite.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 9, 2017 at 3:17

Maltysen

25.7k4 gold badges55 silver badges127 bronze badges

Add a comment |

Jonathan Frech · Accepted Answer · 2017-10-09 06:59:28Z

2

Python 2, 142 127 bytes

Saved fifteen bytes thanks to Sherlock9.

T=range(2,input()+2);p=0
for _ in T:
 m=T[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:T[p-1]/=d;p-=2;T[p]+=d
print p

Try it online!

edited Oct 9, 2017 at 6:59

answered Oct 9, 2017 at 6:24

Jonathan Frech

7,3411 gold badge22 silver badges43 bronze badges

\$\begingroup\$ 127 bytes if you don't use P(n) \$\endgroup\$
– Sherlock9
Commented Oct 9, 2017 at 6:30
\$\begingroup\$ 126 bytes \$\endgroup\$
– Felipe Nardi Batista
Commented Oct 9, 2017 at 11:41
\$\begingroup\$ @FelipeNardiBatista Unfortunately, your suggestion doesn't seem to work for test cases n<=4 \$\endgroup\$
– Sherlock9
Commented Oct 9, 2017 at 13:56

Add a comment |

ZaMoC · Accepted Answer · 2017-10-09 07:16:58Z

2

Mathematica, 118 103 bytes

(s=Range[2,5^6];t=1;Do[If[PrimeQ@s[[t]],t++,s[[t]]/=(k=#2&@@ Divisors@s[[t]]);s[[t-1]]+=k;t--],#];t-1)&

Try it online!

Martin Ender saved 15 bytes

edited Oct 9, 2017 at 7:16

answered Oct 9, 2017 at 6:48

ZaMoC

24.9k2 gold badges30 silver badges81 bronze badges

\$\begingroup\$ You'd got a stray space in front of Divisors, you can use infix notation for Do, and you can just return t instead of t-1 (1-based result). \$\endgroup\$
– Martin Ender
Commented Oct 9, 2017 at 16:16

Add a comment |

Sherlock9 · Accepted Answer · 2017-10-09 11:42:41Z

2

Python 3, 158 149 133 bytes

This is a straightforward procedural implementation with one or two quirks to make sure the code works for all test cases. I use [*range(2,n+9)] to ensure that A is large enough (except for n<3, n+9 is more than enough). The else clause divides the old A[p] by d, decrements p, and then adds d to the new A[p], which is definitely bad coding practice. Otherwise, pretty straightforward. Golfing suggestions welcome!

Edit: -9 bytes without sympy thanks to Halvard Hummel. -14 bytes from Felipe Nardi Batista, -6 bytes from some cues from Jonathan Frech's Python 2 answer

p,_,*A=range(int(input())+2)
for _ in A:
 m=A[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:A[p-1]//=d;p-=2;A[p]+=d
print(p)

Try it online!

edited Oct 9, 2017 at 11:42

answered Oct 9, 2017 at 4:57

Sherlock9

12.3k1 gold badge29 silver badges68 bronze badges

\$\begingroup\$ 145 bytes \$\endgroup\$
– Halvard Hummel
Commented Oct 9, 2017 at 9:57
\$\begingroup\$ 148 bytes by making it a full program \$\endgroup\$
– Felipe Nardi Batista
Commented Oct 9, 2017 at 10:54
\$\begingroup\$ if d-m:A[p]... and else:p+=1 to save a byte \$\endgroup\$
– Felipe Nardi Batista
Commented Oct 9, 2017 at 10:55
\$\begingroup\$ 143 bytes by removing the else statement \$\endgroup\$
– Felipe Nardi Batista
Commented Oct 9, 2017 at 11:06
\$\begingroup\$ after removing the else statement, there is no difference in bytes to the function version \$\endgroup\$
– Felipe Nardi Batista
Commented Oct 9, 2017 at 11:10

| Show 1 more comment

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

PHP, 102+1 bytes

for($a=range(2,$argn);$argn--;$d<$a[+$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[+$p]%++$d;);echo$p;

Run as pipe with -R or try it online.

Empty output for input 0; insert + after echo for a literal 0

or use this 1-indexed version (103+1 bytes):

for($a=range($p=1,$argn);$argn--;$d<$a[$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[$p]%++$d;);echo$p;

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 9, 2017 at 11:42

Titus

14.8k1 gold badge24 silver badges41 bronze badges

Add a comment |

NofP · Accepted Answer · 2017-10-11 20:16:13Z

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!

user285259 · Accepted Answer · 2017-10-12 06:10:21Z

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;}

Formated with some comments

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

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");
  }
  ...

Call display()
```
  A[i] = i + 2;
display();
```
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, Commented Apr 25, 2019 at 15:04

NikoNyrh · Accepted Answer · 2017-10-09 12:51:57Z

1

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.

answered Oct 9, 2017 at 12:51

NikoNyrh

2,6819 silver badges8 bronze badges

\$\begingroup\$ Why did you use pattern matching in the loop? You should be able to lose a few bytes without that. \$\endgroup\$
– clismique
Commented Oct 12, 2017 at 7:21
\$\begingroup\$ Also, you might be able to change the first thing to a some statement. \$\endgroup\$
– clismique
Commented Oct 12, 2017 at 7:35
\$\begingroup\$ 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 \$\endgroup\$
– NikoNyrh
Commented Oct 12, 2017 at 7:59

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

clismique · Accepted Answer · 2019-04-25 01:17:52Z

Clojure, 198 193 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))))))))

Stack Exchange Network

The prime ant 🐜

18 Answers 18

Alice, 45 bytes

Python 2, 120 bytes

Octave, 109 103 101 94 bytes

MATLAB, 130 123 118 117 bytes

JavaScript (ES6), 91 bytes

Demo

Haskell, 108 106 94 bytes

TI-BASIC, 108 103 102 98 bytes

MATL, 41 bytes

Explanation

PARI/GP, 87 bytes

Pyth - 44 bytes

Python 2, 142 127 bytes

Mathematica, 118 103 bytes

Python 3, 158 149 133 bytes

PHP, 102+1 bytes

R, 123 bytes

C (gcc), 152 148 bytes

Minified

Formated with some comments

Main function for testing

For showing each step

Clojure, 185 bytes

Java 8, 138 135 bytes

Clojure, 198 193 191 bytes

Usage:

Ungolfed code:

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
primes
or ask your own question.

Hot Network Questions

The prime ant 🐜

18 Answers 18

Alice, 45 bytes

Python 2, 120 bytes

Octave, 109 103 101 94 bytes

MATLAB, 130 123 118 117 bytes

JavaScript (ES6), 91 bytes

Demo

Haskell, 108 106 94 bytes

TI-BASIC, 108 103 102 98 bytes

MATL, 41 bytes

Explanation

PARI/GP, 87 bytes

Pyth - 44 bytes

Python 2, 142 127 bytes

Mathematica, 118 103 bytes

Python 3, 158 149 133 bytes

PHP, 102+1 bytes

R, 123 bytes

C (gcc), 152 148 bytes

Minified

Formated with some comments

Main function for testing

For showing each step

Clojure, 185 bytes

Java 8, 138 135 bytes

Clojure, 198 193 191 bytes

Usage:

Ungolfed code:

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequenceprimes or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
primes
or ask your own question.