text:
The prime ant
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.

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

Can we use 1-indexing for the array instead?

@Tom Yes, no problem, as long as your program returns the correct results.

@SuperChafouin so outputs of for the test cases can be: 1,7,10,275,513 if 1-indexing stated? Or would they still need to match your outputs.

@SuperChafouin if we're using 1indexed array, is a 1-indexed result "correct"?

It's OK for me. I edit the question to allow 0-indexation or 1-indexation.

@MartinEnder Another open question is whether a prime > 7 can eventually be left behind for good.

@Arnauld I'm curious how the ant's position grows with respect to the number of moves.  My guess is logarithmic.

@kamoroso94 It's probably somehow related to ω(n) and/or Ω(n). If p is the position and n is the number of moves, then p seems to be in the order of magnitude of n.log(n)/log(log(n)). But that's a complete guess...

I have the Android widget for stack exchange...I thought there was a bug on my screen.

@Arnauld Yeah, we can conjecture that for any given position P≥0 there is an N≥0 (depending on P) such that if the number n of moves is greater than N, then the position f(n) of the ant will always be greater than P, and the array entries with indices small than P will all be one-digit prime numbers (i.e. belong to { 2, 3, 5, 7 }).

Looks oddly related to this mathematical sequence, wonder whether we could alter the projection to stop it diverging later on in the sequence:
M(0)=0; M(n+1)=M(n).f(M(n), n).f(M(n), n+1).d(M(n), n); -f(m, n)

@KodosJohnson, gotta love outdoor computing!

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

I added this sequence to the On-Line Encylopedia of Integer Sequences as sequence A293689. The graph is worth looking at.

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

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 Ah, ok. In MATLAB the trailing end is optional.

you can make anonymous function by using @(n) at the start instead of using function i=a(n)

@Michthan can't do that in MATLAB. I don't think it is possible in Octave either as it has loops?

The trailing end is optional in Octave too. Here it is only needed because you have code after the function

@TomCarpenter https://www.gnu.org/software/octave/doc/v4.0.3/Anonymous-Functions.html#Anonymous-Functions That's where I found my information about anonymous functions;

In Octave we get +=, -=, /= so this is much shorter in Octave but then it won't work in MATLAB. But if(nnz(q)>1) should be if nnz(q)>1 for -1 byte.

@Giuseppe cool, should of spotted those brackets. I like learning new optimisations like the += etc, don't know why MATLAB doesn't have them. Saved a couple more as well by using for l=z instead of for l=1:n.

@LuisMendo that's what I did as well (put the end in the footer on TIO).

Actually, I got it down to 91 bytes: Try it online!. Do you mind if I post this as my own answer? (the algorithm is the same, but the implementation is quite different)

@Sanchises might as well at this point, lol.

Actually, I don't feel like making a whole answer with explanation, so you may post my 90 bytes version, Try it online!, if you like :)

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.

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!

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 Thanks a lot! It's even only 94 bytes when switching to 0-indexing.

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

You can take a byte off of fPart(∟A(P)/F: with fPart(F¹∟A(P:. Same thing in the next line.

@ScottMilner That doesn't always work.  not(fPart(7⁻¹7 is 0 but not(fPart(7/7 is 1.

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

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

Pyth - 44 bytes
Straightforward procedural implementation.
K}2hhQVQJ@KZIP_J=hZ).?=GhPJ XKZ/JG=tZ XZKG;Z

Test Suite.

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!

145 bytes

148 bytes by making it a full program

if d-m:A[p]... and else:p+=1 to save a byte

143 bytes by removing the else statement

after removing the else statement, there is no difference in bytes to the function version

139 bytes by using unpacking in the creation of p and A

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!

127 bytes if you don't use P(n)

126 bytes

@FelipeNardiBatista Unfortunately, your suggestion doesn't seem to work for test cases n<=4

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

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

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;

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!

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?

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.

Why did you use pattern matching in the loop? You should be able to lose a few bytes without that.

Also, you might be able to change the first thing to a some statement.

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

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

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

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Expand Comparison Chains
Unlike most languages, Python evaluates a<b<c as it would be done in mathematics, actually comparing the three numbers, as opposed to comparing the boolean a<b to c. The correct way to write this in C (and many others) would be a<b && b<c.
In this challenge, your task is to expand such comparison chains of arbitrary lengths from the Python/intuitive representation, to how it would be written in other languages.
Specifications

Your program will have to handle the operators: ==, !=, <, >, <=, >=.
The input will have comparison chains using only integers.
Don't worry about the trueness of any of the comparisons along the way, this is purely a parsing/syntactical challenge.
The input won't have any whitespace to prevent answers that trivialize parsing by splitting on spaces.
However, your output may have a single space surrounding either just the &&'s, or both the comparison operators and the &&'s, or neither, but be consistent.

Test Cases
Input                  Output
---------------------------------------------------------------

3<4<5                  3<4 && 4<5
3<4<5<6<7<8<9          3<4 && 4<5 && 5<6 && 6<7 && 7<8 && 8<9
3<5==6<19              3<5 && 5==6 && 6<19
10>=5<7!=20            10>=5 && 5<7 && 7!=20
15==15==15==15==15     15==15 && 15==15 && 15==15 && 15==15

This is code-golf, so shortest code in bytes wins!

related

Can I have two spaces either side of the &&?

@H.PWiz nope, srry.

Retina, 33 22 17 bytes
-5 bytes thanks to @MartinEnder
-2`\D(\d+)
$&&&$1

Try it online!

@MartinEnder A pity 1>-2 doesn't work to limit from both ends at once...

@Neil yeah, Retina 1.0 will get a new limit syntax where that's possible.

Could you post an explanation?

Husk, 16 14 bytes
Prints a space around each operator.
wJ"&&"m←C2X3ġ±

Try it online!
Explanation:
                  Implicit input, e.g            "3<4<5<6"
            ġ±    Group digits                   ["3","<","4","<","5","<","6"]
          X3      Sublists of length 3           [["3","<","4"],["<","4","<"],["4","<","5"],["<","5","<"],["5","<","6"]]
        C2        Cut into lists of length 2     [[["3","<","4"],["<","4","<"]],[["4","<","5"],["<","5","<"]],[["5","<","6"]]]
      m←          Take the first element of each [["3","<","4"],["4","<","5"],["5","<","6"]]
 J"&&"            Join with "&&"                 ["3","<","4","&&","4","<","5","&&","5","<","6"]
w                 Print, separates by spaces

Nice one. You could use w instead of ; for a more direct approach to joining strings with spaces

Oh yes, how didn't I think of that?

Retina, 42 47 22 bytes
Massively golfed thanks to Kevin Cruijssen
(\D(\d+))(?=\D)
$1&&$2

Try it online!

(==|!=|<=?|>=?) can be  \D+

Similarly (?<!^|\d) can be (?<=\D). Also the (?=\d+) is unnecessary, the operator will always be followed by an operand, at which point you can drop the + after the \D. There's also $& instead of $1$2, and then a further byte can be saved by capturing behind and looking ahead instead of capturing ahead and looking behind.

(\D(\d+))(?=\D) on line 1, and $1&&$2 on line two is enough (22 bytes). Try it here.

V, 37 bytes
òÍ¨ä«„0-9& ]«©¨ä«©¨„0-9& ]«©/±² ¦¦ ²³

Try it online!
Hexdump:
00000000: f2cd a8e4 ab84 302d 3926 205d aba9 a8e4  ......0-9& ]....
00000010: aba9 a884 302d 3926 205d aba9 2fb1 b220  ....0-9& ]../..
00000020: a6a6 20b2 b3                             .. ..

Clojure, 88 bytes
Update: subs instead of clojure.string/join.
#(subs(apply str(for[p(partition 3 2(re-seq #"(?:\d+|[^\d]+)" %))](apply str" && "p)))4)

J, 59 46 bytes
4(}.;)_2{.\3' && '&;\]</.~0+/\@,2~:/\e.&'!<=>'

Try it online!
How it used to work
                        (0 , }. ~:&(e.&'!<=>') }:)

We’re looking for operator boundaries. “Beheaded” and “curtailed” strings are turned into zeroes and ones where 0s are digits, then xored together. Prepend zero to match the length.
                   +/\                      </. ]     Split on boundaries.
              ┌──┬──┬─┬─┬─┬──┬──┐
              │10│>=│5│<│7│!=│20│
              └──┴──┴─┴─┴─┴──┴──┘
         3' && '&;\          Add && to infixes of 3.
              ┌────┬──┬──┬──┐
              │ && │10│>=│5 │
              ├────┼──┼──┼──┤
              │ && │>=│5 │< │
              ├────┼──┼──┼──┤
              │ && │5 │< │7 │
              ├────┼──┼──┼──┤
              │ && │< │7 │!=│
              ├────┼──┼──┼──┤
              │ && │7 │!=│20│
              └────┴──┴──┴──┘
    _2{.\                    Take even numbered rows.
;}.,                         Concatenate after dropping the first box.

Charcoal, 29 bytes
≔ ηＦθ«¿›ι9«Ｆ›η!⁺&&η≔ωη»≔⁺ηιηι
≔ ηＦθ«Ｆ∧›ι9›η!⁺&&η≔⎇›ι9ω⁺ηιηι

Two slightly different formulations of the same basic algorithm. The input string is iterated by character. As digits are found they are collected in a variable. When a boundary between a number and operator is found, an extra "&&" plus the variable is printed and the variable is cleared. The variable is initially initialised to a space so that the first boundary doesn't trigger the extra "&&".

Jelly, 16 bytes
e€ØDŒg⁸ṁṡ3m2j⁾&&

Try it online!
Explanation:
e€ØDŒg⁸ṁṡ3m2j⁾&& Uses Jelly stringification, thus full program only
e€ØD             For each each char, 1 if it's in '0123456789', otherwise 0
    Œg           Split into longest runs of equal elements
      ⁸ṁ         Reshape original input like the list we just made
                 Reshaping will separate numbers from operators
        ṡ3       Get contiguous sublists of length 3
          m2     Keep every second item, starting from the first
                 This will keep every (number operator number) and
                 remove every (operator number operator) substring
            j⁾&& Join with '&&'

Java 8, 46 bytes
s->s.replaceAll("(\\D(\\d+))(?=\\D)","$1&&$2")

Explanation:
Try it here.
s->                       // Method with String as both parameter and return-type
   s.replaceAll("(\\D(\\d+))(?=\\D)",
                "$1&&$2") //  Replace the match of the regex
                          //  with the second String
                          // End of method (implicit / single-line return-statement)

Regex explanation:
(\D(\d+))(?=\D)   # 1) For all matches of this regex
   (\d+)          #  Capture group 2: a number (one or more digits)
(\D \d+ )         #  Capture group 1: anything but a number + the number
                  #   (`\D` will match the `=`, `!`, `<`, or `>`)
         (?=\D)   #  Look-ahead so everything after the match remains as is

 $1&&$2           # 2) Replace it with
 $1               #  Result of capture group 1 (trailing part of the equation + the number)
   &&             #  Literal "&&"
     $2           #  Result of capture group 2 (the number)

Step by step example of the replacements:
Initial:                             10>=5<7!=20
 Match of first replacement:            =5
 Replace with:                          =5&&5
After first replacement:             10>=5&&5<7!=20
 Match of second replacement:                <7
 Replace with:                               <7&&7
After second replacement (result):   10>=5&&5<7&&7!=20

Perl 5, 47 + 1 (-p) = 48 bytes
$\.=$1." && "x(!!$')while s/(\d+\D+(\d+))/$2/}{

Try it online!

Python 2, 60 59 58 57 bytes
lambda s:re.sub(r'(\D(\d+))(?=\D)',r'\1&&\2',s)
import re

Try it online!

re.sub(r'\D(\d+)(?=\D)',r'\g<0>&&\1',s) saves 1 byte.

Ruby, 37 bytes
->s{s.gsub(/\D(\d+)(?=\D)/,'\&&&\1')}

Try it online!

JavaScript (SpiderMonkey), 43 bytes
f=s=>s.replace(/(\W+(\d+))(?!$)/g,"$1&&$2")

Try it online!

Jelly, 15 bytes
e€ØDnƝkṡ3m2j⁾&&

Try it online!
Outputs with no spaces around the &&, but the Footer in the TIO link adds the spaces to make the output easier to read
How it works
e€ØDnƝkṡ3m2j⁾&& - Main link. Takes a string S on the left
e€ØD            - Replace digits with 1, otherwise 0
     Ɲ          - To overlapping pairs [a,b]:
    n           -   a ≠ b
      k         - Split S on truthy elements, grouping digits together
       ṡ3       - Split into overlapping lists of length 3
         m2     - Take every other element
           j⁾&& - Join by "&&"

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Golfing Newton's Method
I have the following code which I've written to emulate Newton's method for deriving the square root of a number:
r=(x,y)=>
  (z=((y=y||x)*y-x)/(2*y)>1e-15)?
r(x,y-(y*y-x)/(2*y)):y

Where r(37) would result in 6.08276253029822 which is great given the limitations of my browser.
I'd like to golf this code further seeing there's some repetition here, not to mention, I'd also like to reduce my error limit (the 1e-15). This is the furthest I've gotten. Can anyone help? If possible I'd love to eliminate the need of the error limit without resulting in a "maximum stack call size exceeded" error...
This is for a blog post I'm working on JavaScript and alternatives to native methods. I'll give a special shout out on the blog post to the persons who can help me out.
Thanks in advance.

Which is more important, golfing it or reducing the error?

@mbomb007 reducing the error is one thing... But If day golfing it is more important. I'm curious to see the answer from both fronts though. I've tried this on various browsers and found that my error was in the 1e-16 range...

Okay, why the down vote?

Idk. Questions about golfing are ON-TOPIC. Someone voted to close, and I think they are wrong.

Without a spec of a problem to golf, it's hard to know what improvements are valid. I'm voting to close as unclear until there's a solid spec.

@xnor, this is a tips question, not a challenge.

I never mentioned this as a challenge, @xnor. I'm asking for help to golf...

@WallyWest Right, but I can't give help to golf without knowing the challenge. Does anything stop you from just writing sqrt(n)? What accuracy is required? The code has a 1e-15 in it -- whether a byte could be saved as a 1e-9 depends on how precise the output must be. "I'd also like to reduce my error limit (the 1e-15)" further confuses it.

@WallyWest Also, it's not clear from the text that you are looking primarily for golfing help. Asking about eliminating the error limit and saying you'll use it for an explanation in a blog rather sounds like seeking programming advice separate from shortening code.

@xnor, the blog post I'm writing is about alternatives to native methods, so, no Math.sqrt(x) is out of the question. I'd prefer to retain as much accuracy as possible, so 1e-9 won't work for me either...

@WallyWest It seems to me that the hypothetical task for this golf is so vague it would be closed, which means I can't know if a suggestion I post would be valid.

Using a fixed epsilon and an absolute difference test guarantees bugginess. Consider that if x is somewhere near the upper bound of a double then 1 ulp relative to the square root is about 1E140.

@PeterTaylor Can you give an example of X near that upper bound level? I'm not sure what classes as a double in this case...?

1E308. Number.MAX_VALUE is the actual upper bound.

Golfed only, -23 bytes
ES6 supports default parameters.

Default function parameters allow formal parameters to be initialized
with default values if no value or undefined is passed.

So, we can replace y=y||x with just r=>(x,y=x).
(y*y-x)/(2*y) can be rewritten as y/2-x/2/y. And since this expression appears twice in the code, we can assign it to a new variable z.
We get:
r=(x,y=x)=>(z=y/2-x/2/y)>1e-15?r(x,y-z):y

As suggested by ETHproductions in the comments, we now can save 2 more bytes by multiplying z by 2:
r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

console.log(r(37))

Alternate version, -26 bytes
To save more bytes, another approach is to just iterate enough times rather than using a test on the result.
That could be done that way:
r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

console.log(r(37))

We start with k = x and divide it by 2 at each iteration. No matter the initial value of x, we will eventually reach 0 because of arithmetic underflow.
The good thing about this method is that the number of iterations doesn't heavily rely on the value of x. For instance, we'll get 1142 iterations for x = 1020 and 1009 iterations for x = 10 -20. In both cases, we iterate far too many times than necessary, without exceeding the default maximum number of iterations of common browsers.
Some more notes:

The error is negligible for x > 10 -215 and quickly grows below this bound.
For the same byte count and less iterations, we can divide by 9 instead. In that case, a safe bound is x > 10 -124.
Unlike Math.sqrt(), this method does not return NaN for negative numbers or ±Infinity (and neither does the original code).

And then you can do r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y to save another two bytes, and perhaps adjust the 2e-15 to get more precision

@ETHproductions Thanks! I thought about such an optimization for a second but overlooked it.

@Arnauld Nice abuse of arithmetic underflow... I had considered it in some of my previous attempts but wasn't sure on the implementation. This is perfect... Thanks!

@WallyWest Glad it helped! Some quick notes: 1) Performance-wise, the alternate version is, of course, very inefficient. 2) Unlike Math.sqrt(), these methods do not return NaN for negative numbers or +/-Infinity.

This is almost similar to "@Arnauld Alternate version" and has same bytes with that, but this can work in x < 1e-215
r=(x,y=k=9)=>k?r(x,(y+x/y)/2,k/=2):y

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Make a Bit Continent
Let's imagine we have a matrix of bits (which contains at least one 1):
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0

We want to set some of the bits in this matrix such that it forms a contiguous blob of 1s, in which every 1 is directly or indirectly connected to every other 1 through orthogonal movement:
0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1 0 1 0
1 1 0 0 1 0 0 1 1 1 1
0 0 0 1 1 1 1 0 0 1 0

(You can see this more clearly by searching for 1 with your browser's "find" feature.)
However, we also want to minimize the number of bits that we set.
The Task
Given a matrix (or array of arrays) of bits or booleans, return the minimum number of bits that need to be set to create a contiguous continent of 1s. It should be possible to get from one set bit in the matrix to another by only traveling in an orthogonal direction to other set bits.
This is code-golf, so the shortest valid submission (measured in bytes) wins.
Test Cases
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
=> 6

1 0 0 0 0 0 1 0 0
1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0
=> 4

0 0 0 1 1 1 0 1 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 1 1 1 0
1 1 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 1 1 0 0 0 0 0
1 1 1 0 0 1 1 1 0
1 1 1 0 1 1 0 1 1
0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0
0 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 1
=> 8

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
=> 0

This needs a bit more explaining. What is a "contiguous blob" in a matrix?

What are the parameters in which we express the complexity?

@xnor What do you mean by this?

@Challenger5 Never mind, I see you added "(in the number of bits in the matrix)" regarding the time complexity.

Since the problem is known to be NP-hard it's not a good problem for [tag:fastest-algorithm].

Is it just me or is this the TSP in disguise

@PeterTaylor This challenge just asks to find how many bits need to be set, not what bits to set. Would that make a difference?

Unlikely in the general case, and no in this case.

@Peter Taylor and esolangingfruit NP-Hardness

In light of Peter Taylor and HyperNeutrino's comments, and the fact that the question currently has no answers, I'm changing the scoring method to [tag:code-golf].

What should we do if there's no 1 in the matrix?

@ColeraSu You don't have to handle that case.

C (gcc), 308 306 bytes
Function f receives (height, width, flattened array, pointer to ans), and returns answer by pointer.
If there's no 1 in the matrix, it will return 0.
#define v A[i]
N,M,K,R,C,T,i,*A;s(x,y){i=x*M+y;if(!(x<0|y<0|x>=N|y>=M|v^1))v=2,s(x,y+1),s(x,y-1),s(x+1,y),s(x-1,y);}g(i){if(C<R){if(i^K){g(i+1);if(!v)C+=v=1,g(i+1),v=0,C--;}else{T=1;for(i=0;i<K&&!v;i++);s(i/M,i%M);for(i=0;i<K;i++)T&=v^1,v=!!v;if(T)R=C;}}}f(n,m,a,b)int*a,*b;{K=R=(N=n)*(M=m),A=a;g(0);*b=R;}

Try it online!
Ungolfed:
N,M,R,C,T,i,*A; // height, width, result, recursion depth

s(x,y)
{ // depth first search: replace all 1 in the same connected component with 2
    i=x*M+y;
    if(!(x<0|y<0|x>=N|y>=M|A[i]^1)) { // check if out of boundary
        A[i]=2;
        s(x, y+1),s(x, y-1),s(x+1, y),s(x-1, y);
    }
}

g(i)
{ // enumerate all posible solutions
    if(C<R) {
        if(i!=N*M) {
            g(i+1);      // nothing change for this entry
            if (!A[i]) { // set the entry to 1
                C++, A[i]=1;
                g(i+1);
                C--, A[i]=0;
            }
        }
        else {
            T=1;
            for (i=0; i<N*M && !A[i]; i++); // find first non-zero entry
            s(i/M, i%M);     // replace the connected component
            for (i=0; i<N*M; i++) {
                T&=A[i]!=1;   // check if no other components
                A[i]=!!A[i]; // change 2s back to 1
            }
            if (T) R=C;      // update answer
        }
    }
}

f(n,m,a,b)int*a,*b;{
    R=(N=n)*(M=m), A=a;
    g(0);
    *b=R;
}

Python 2, 611 bytes
A full program that takes a list of lists through user input. The functions I and d count the number of islands in the array. The for loop at the end enumerates through all possibilities of where you can change 0s to 1s then if there is one island left stores the number of 1s added to the list C. The minimum of that list is the minimum number of bit flips required to connect any islands. It is a very slow algorithm so it doesn't run the test cases given in under 60s (I didn't try longer) but I tried a few smaller (~5x5) test cases and it seems to be working correctly. I got the island counting algorithm from this page.
from itertools import*
def d(g,i,j,v):
 v[i][j],R,C=1,[-1,1,0,0],[0,0,-1,1]
 for k in range(4):
	if len(g)>i+R[k]>=0<=j+C[k]<len(g[0]):
	 if v[i+R[k]][j+C[k]]<1and g[i+R[k]][j+C[k]]:v=d(g,i+R[k],j+C[k],v)
 return v
def I(g):
 w=len(g[0])
 v,c=[w*[0]for r in g],0
 for i in range(len(g)*w):
	if v[i/w][i%w]<1and g[i/w][i%w]>0:v=d(g,i/w,i%w,v);c+=1
 return c
g=input()
C=[]
for p in [list(t)for t in product([0,1],repeat=sum(r.count(0)for r in g))]:
 h,G,x=0,[r[:]for r in g],len(g[0])
 for i in range(x*len(G)):
	if G[i/x][i%x]<1:h+=p[0];G[i/x][i%x]=p[0];del p[0]
 if I(G)<2:
	C.append(h)
print min(C)

Try it online!
Pregolfed version before I optimized a few things:
from itertools import*
def d(g,i,j,v):
    v[i][j]=1
    R=[-1,1,0,0]
    C=[0,0,-1,1]
    for k in range(4):
        if len(g)>i+R[k]>=0<=j+C[k]<len(g[0]):
            if v[i+R[k]][j+C[k]]<1:
                if g[i+R[k]][j+C[k]]:
                    v=d(g,i+R[k],j+C[k],v)
    return v
def I(g):
    w=len(g[0])
    v=[[0]*w for r in g]
    c=0
    for i in range(len(g)):
        for j in range(w):
            if v[i][j]<1and g[i][j]>0:
                v=d(g,i,j,v)
                c+=1
    return c
g=input()
z=sum(r.count(0)for r in g)
f=[list(t)for t in product('01',repeat=z)]
C=[]
for p in f:
    h=0
    G=[r[:]for r in g]
    x=len(G[0])
    for i in range(x*len(G)):
        exec('h+=int(p[0]);G[i/x][i%x]=int(p[0]);del p[0]'*(G[i/x][i%x]<1))
    if I(G)<2:
        C.append(h)
print min(C)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Make a list continuous!
Take an input list L containing positive integers, and insert the least amount of integers into the sequence, so that you make it a continuous one.
Example:
L = 4 2 6 1
Out: 4 3 2 3 4 5 6 5 4 3 2 1

The input and output formats are optional.
Test cases:
L = 1
Out: 1

L = 10 4
Out: 10 9 8 7 6 5 4

L = 13 13
Out: 13 13

L = 3 6
Out: 3 4 5 6

L = 4 4 1 1 4 4
Out: 4 4 3 2 1 1 2 3 4 4

This is code-golf... You know the rules.

I'm almost certain this is a duplicate but I can't find the challenge…

Related

I tried finding a similar one myself, but I couldn't find any. I thought it would make a nice simple challenge. My favorite language is a bit messy when it comes to creating ranges in both ascending and descending order at the same time.

@Fatalize I didn't find that one when I searched. I do feel this is different enough, but I don't know how strict the community is when it comes to similar challenges...? I guess there will be some answers that are easily portable though...

The related one is different enough I feel because the input has the same length as the output, so approaches will be more about substitution rather than insertion.

Test case: [4,4,1,1,4,4]

@Zgarb added :)

Darn, it was a duplicate after all... :/ It was hard to find that challenge though... Not many obvious words to search for...

Builtin
Husk:
…

Try it online!
I bet this builtin exists in more than one language, so I made this a community wiki, just add in more languages where this is a builtin if you know them!

Brachylog, 11 bytes
⊆.s₂ᵇ-ᵐ~ṡᵐ∧

Try it online!
It's long and slow but at least it's declarative…
Explanation
⊆.        ∧       The Input is an ordered subset of the Output
  s₂ᵇ             Take all substring of 2 consecutive elements in the Output
     -ᵐ           Take the subtractions of all those substrings
       ~ṡᵐ        They must all be valid "ṡigns" (i.e 1, 0 or -1)

Mathematica, 72 bytes
Another approach using ReplaceAll.
#//.{(p={a___,b_,c_,d___})/;b>c+1->(f={a,b,b-#,c,d}&)@1,p/;b<c-1->f@-1}&


text:
Recursively concatenated cumulative sums of [N] with M iterations
Take two positive integers N and M and create the concatenated cumulative sums of [N], with M iterations. Output the result of the last iteration.
Definition of the concatenated cumulative sum:

Start with a number N and define a sequence X = [N]
Append to X the cumulative sums of X
Repeat step 2 M times.

The cumulative sum of a vector, X = [x1, x2, x3, x4] is: [x1, x1+x2, x1+x2+x3, x1+x2+x3+x4].
Example with N = 1 and M = 4:
P = the cumulative sum function.
M = 0: [1]
M = 1: [1, 1]                    -  X = [1, P(1)] = [[1], [1]]
M = 2: [1, 1, 1, 2]              -  X = [X, P(X)] = [[1, 1], [1, 2]]
M = 3: [1, 1, 1, 2, 1, 2, 3, 5]  -  X = [X, P(X)] = [[1, 1, 1, 2], [1, 2, 3, 5]]
M = 4: [1, 1, 1, 2, 1, 2, 3, 5, 1, 2, 3, 5, 6, 8, 11, 16]

Note that the first X = [1] is not counted as an iteration. You may choose to take M = 5 for the above example (thus counting X = [1] as one iteration).
This is OEIS A107946

Test cases:
N = 5, M = 1
5, 5

N = 2, M = 3
2, 2, 2, 4, 2, 4, 6, 10

N = 4, M = 6
4, 4, 4, 8, 4, 8, 12, 20, 4, 8, 12, 20, 24, 32, 44, 64, 4, 8, 12, 20, 24, 32, 44, 64, 68, 76, 88, 108, 132, 164, 208, 272, 4, 8, 12, 20, 24, 32, 44, 64, 68, 76, 88, 108, 132, 164, 208, 272, 276, 284, 296, 316, 340, 372, 416, 480, 548, 624, 712, 820, 952, 1116, 1324, 1596

This is code-golf, so shortest code wins. Optional input and output formats.

It's a bit too late now, but does N really add anything to the problem? It's just a constant factor you multiply the result by.

Haskell, 35 bytes
n!m=iterate((++)<*>scanl1(+))[n]!!m

Try it online!
Thanks to H.PWiz for -18 bytes

tail.scanl(+)0 can be scanl1(+)

@H.PWiz Thanks, I always forget about the *1 versions of scan and fold.

45 bytes

35 bytes using iterate

I'm just going to leave off the explanation - too much effort to change it every time :P

In modern Haskell (newer than on TIO) n!m=iterate(id<>scanl1(+))[n]!!m is valid. On TIO it needs import Data.Monoid because <> is not yet in the Prelude.

In older Haskells, f n=n:f(n++scanl1(+)n) followed by n!m=f[n]!!m saves a byte.

05AB1E, 7 bytes
¸IFDηO«

Try it online!
Explanation
¸         # wrap input_1 in a list
 IF       # input_2 times do:
   D      # duplicate the list
    η     # get prefixes of the list
     O    # sum the prefixes
      «   # concatenate to the current list

Husk, 9 8 7 bytes
Thanks to H.PWiz for saving 1 byte.
!¡S+G+;

Try it online!
Uses 1-based M.
Explanation
      ;     Wrap N in a list to get [N].
 ¡          Iterate the following function on this list and collect
            the results in an infinite list.
  S+        Concatenate the current value with...
    G+      ...the cumulative sum. We're not using the cumsum built-in ∫
            because it prepends a zero.
!           Use M as an index into the infinite list.

Was my approach too, I'm not sure if it's golfable. Also, I've already suggested for cumsum not to return a leading 0 (something which would save 2 bytes in this case).

Can ot∫ be G+?

@H.PWiz Hmm...the docs seem to be unclear on that (AFAIK "scan" means "reduce" not "cumulative reduce").

F is reduce G is cumulative reduce

MATL, 6 bytes
:"tYsh

Inputs are M, then N.
Try it online! Or verify all test cases.
Explanation
:"      % Implicitly input M. Do the following M times
  t     %   Implicitly input N the first time. Duplicate
  Ys    %   Cumulative sum
  h     %   Concatenate horizontally
        % Implicitly end loop. Implicitly display stack

Whaaaaat? I'm sure I've tried that 100 times. I even tried going over to Suever's site to make sure it wasn't some strange error on TIO... I don't understand this at all...

I can't stop thinking about this... I'm absolutely sure I've written those exact characters again and again and tried to run it on two different sites, without success. Since that can't be the case, the only explanation left is that I'm going crazy... This really messes with my head!

Mathematica, 34 bytes
Nest[#~Join~Accumulate@#&,{#},#2]&

Try it online!

Python 2, 83 78 75 71 65 63 60 bytes
def f(n,m):r=n,;exec"s=0\nfor c in r:s+=c;r+=s,\n"*m;print r

Try it online!
Saved 6 8 bytes thanks to Rod
Saved 3 bytes thanks to Erik

@Rod More thanks :D

You don't need the [:], r is a tuple.

@EriktheOutgolfer, thanks, it's a leftover from when r was a list

Dyalog APL, 12 bytes
{(⊢,+\)⍣⍺⊢⍵}

Takes N on the right side and M on the left.
TryAPL here!
Explanation:
{(⊢,+\)⍣⍺⊢⍵}
{          } an anonymous function
 (⊢,+\)      a train for a single iteration:
  ⊢           the right argument
   ,          concatenated with
    +\        the cumulative sum
       ⍣     repeated
        ⍺     left argument times
         ⊢⍵  on the right argument

Love the explanation. Very clear what's going on. Hard to understand APL otherwise :P

Java (OpenJDK 8), 194 181 175 163 134 110 bytes
(n,m)->{int a[]=new int[1<<m],c=1,i;for(a[0]=n;m-->0;)for(n=0;2*n<c;c++)for(i=++n;i-->0;a[c]+=a[i]);return a;}

Try it online!

110 bytes: (n,m)->{int a[]=new int[1<<m],c=1,i;for(a[0]=n;m-->0;)for(n=0;2*n<c;c++)for(i=++n;i-->0;a[c]+=a[i]);return a;}

jq, 51 bytes
reduce range(.[1])as$j([.[0]];.+[.[:keys[]+1]|add])

Try it online!
done with some help from the #jq IRC channel at libera.chat.
returns a nice JSON array.
-1 byte from ovs.
-7 bytes from Michael Chatiskatzi.

58 bytes by using slicing and add to calculate the prefix sums

You can use keys[] instead of range(length).

Dyalog APL, 19 bytes
{0=⍺:⍵⋄(⍺-1)∇⍵,+\⍵}

Try it online!
Dyadic function, with N on the right and M on the left.
{
    0=⍺: ⍵         ⍝ if a = 0 return
    (⍺-1) ∇ ⍵,+\⍵  ⍝ recurse with the array
                   ⍝ joined with its cumsum (+\⍵)
}

R, 46 bytes
function(N,M){for(i in 1:M)N=c(N,cumsum(N))
N}

Try it online!

Clojure, 67 bytes
#(loop[c[%]i %2](if(= i 0)c(recur(into c(reductions + c))(dec i))))

Jelly, 5 bytes
;+\$¡

Try it online!
Suggested version by Dennis (returns n instead of [n] for singleton arrays).

W and ⁹ can be removed.

@Dennis I'm afraid the output won't be right then? I thought of it but if I get inputs 1 and 0 I'm afraid I'll be returning 1 instead of [1] if I remove those, and I can't use a full program instead, since its output would still be like that.

1 is how Jelly displays the array [1]. I see no problem with that.

@Dennis Hmm...a little suspicious to that (as I said on the last part of my comment above)...is there any consensus allowing it, or would it count as "standard loophole abusing datatypes"?

Both formats are ok.

Pyth, 12 bytes
L+bsM._byF]E

Try it here.

JavaScript (ES6), 55 54 bytes
Takes input in currying syntax (m)(n).
m=>g=a=>m--?g([...a=+a?[a]:a,...a.map(x=>s+=x,s=0)]):a

Test cases

let f =

m=>g=a=>m--?g([...a=+a?[a]:a,...a.map(x=>s+=x,s=0)]):a

console.log(f(1)(5).join(', '))
console.log(f(3)(2).join(', '))
console.log(f(6)(4).join(', '))

Julia 1.5, 31 bytes
n>m=m<1 ? n : [n;cumsum(n)]>m-1

Try it online!


text:
An expanding array
Given two positive integers p and q, your task is to return the array A created by applying the following algorithm:

Start with A = [p, q] and d = 2
For each pair (x, y) of contiguous numbers in A whose sum is divisible by d, insert (x + y) / d between x and y.
If at least one matching pair was found, increment d and go on with step #2. Otherwise, stop and return A.

Example
Below is the detail of the process for p = 1 and q = 21.
  1  21             | Iteration #1: we start with d = 2 and A = [1, 21]
   \/               |               1 + 21  is divisible by 2 -> we insert 11
 22/2=11            |
                    |
  1  11 21          | Iteration #2: d = 3, A = [1, 11, 21]
   \/               |               1 + 11  is divisible by 3 -> we insert 4
 12/3=4             |
                    |
  1 4 11  21        | Iteration #3: d = 4, A = [1, 4, 11, 21]
        \/          |               11 + 21 is divisible by 4 -> we insert 8
      32/4=8        |
                    |
  1    4    11 8 21 | Iteration #4: d = 5, A = [1, 4, 11, 8, 21]
    \/   \/         |               1 + 4   is divisible by 5 -> we insert 1
  5/5=1 15/5=3      |               4 + 11  is divisible by 5 -> we insert 3
                    |
  1 1 4 3 11 8 21   | Iteration #5: d = 6, A = [1, 1, 4, 3, 11, 8, 21]
                    |               no sum of two contiguous numbers is divisible by 6
                    |               -> we stop here

Hence the expected output: [1, 1, 4, 3, 11, 8, 21]
Clarifications and rules

Input and output can be handled in any reasonable format. The integers p and q are guaranteed to be greater than 0. If that helps, you may assume q ≥ p.
The 2nd step of the algorithm should not be recursively applied to elements that have just been inserted at the same iteration. For instance, A = [1, 1] and d = 2 should lead to [1, 1, 1] (not an infinite list of 1's).
This is code-golf, so the shortest answer in bytes wins!

Test cases
  p |   q | Output
----+-----+-------------------------------------------------------------------------------
  1 |   1 | [1,1,1]
  1 |   2 | [1,2]
  1 |   3 | [1,1,2,3]
  2 |   6 | [2,1,2,1,4,1,2,6]
  3 |  13 | [3,1,8,1,3,1,7,1,2,1,5,1,3,2,13]
  9 |   9 | [9,6,9,6,9]
 60 |  68 | [60,13,1,4,31,2,3,5,2,19,64,7,13,1,2,5,2,27,44,3,4,8,2,1,12,1,5,3,28,2,4,16,1,
    |     |  2,12,1,2,1,10,1,6,68]
144 | 336 | [144,68,3,4,8,1,12,1,4,2,28,13,128,44,17,92,240,58,108,5,17,1,2,5,3,28,3,1,11,
    |     |  60,3,6,2,42,2,4,26,192,54,132,7,1,15,1,3,1,18,1,4,2,30,3,1,12,1,9,78,46,336]

If you'd like to test your code on a slightly bigger test case, here is the expected output for:

p = 12096 (26*33*7)
q = 24192 (27*33*7)

05AB1E, 28 19 18 bytes
[Ðü+NÌ/‚ζ˜ʒ.ï}DŠQ#

Try it online!

eh, can definitely be improved hardcore. still working to refactor.
Probably as good as I'm getting it.
-1 thanks to, who else but, Emigna! For pointing out swap worked better than the registers.

[                   // Infinite loop.
 Ð                  // Triplicate [p, ..., q]
  U                 // Pop 1 of 3 copies into register X.
   ü+               // Pairwise addition.
     NÌ/            // Divide by current iteration + 2 (which is d).
        ‚           // Group original [p, ..., q] with pairwise additives.
         ζ˜         // Transpose together and flatten.
           ʒ.ï}     // Filter out non-integer entities (includes the space added by zip).
               DXQ  // Dupe result, see if equal to original.
                  # // If new array is original array, nothing happened, quit & return.

Debug dump for [p,q] = [1,3]:
Full program: [ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> [  ||  stack: []
ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: []
current >> U  ||  stack: [[1, 3], [1, 3], [1, 3]]
current >> ü  ||  stack: [[1, 3], [1, 3]]
Full program: +
current >> +  ||  stack: [1, 3]
stack > [4]
current >> N  ||  stack: [[1, 3], [4]]
current >> Ì  ||  stack: [[1, 3], [4], 0]
current >> /  ||  stack: [[1, 3], [4], 2]
current >> ‚  ||  stack: [[1, 3], [2.0]]
current >> ζ  ||  stack: [[[1, 3], [2.0]]]
current >> ˜  ||  stack: [[[1, 2.0], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 2.0, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 2.0, 3]]
current >> X  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
current >> Q  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 3]]
current >> #  ||  stack: [[1, 2.0, 3], 0]
stack > [[1, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 2.0, 3]]
current >> U  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 2.0, 3]]
current >> ü  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 2.0]
stack > [3.0]
Full program: +
current >> +  ||  stack: [3.0, 2.0, 3]
stack > [3.0, 5.0]
current >> N  ||  stack: [[1, 2.0, 3], [3.0, 5.0]]
current >> Ì  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 1]
current >> /  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 3]
current >> ‚  ||  stack: [[1, 2.0, 3], [1.0, 1.6666666666666667]]
current >> ζ  ||  stack: [[[1, 2.0, 3], [1.0, 1.6666666666666667]]]
current >> ˜  ||  stack: [[[1, 1.0], [2.0, 1.6666666666666667], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 1.0, 2.0, 1.6666666666666667, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.6666666666666667]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 0]
stack > [[1, 1.0, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 1.0, 2.0, 3]]
current >> U  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> ü  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 1.0]
stack > [2.0]
Full program: +
current >> +  ||  stack: [2.0, 1.0, 2.0]
stack > [2.0, 3.0]
Full program: +
current >> +  ||  stack: [2.0, 3.0, 2.0, 3]
stack > [2.0, 3.0, 5.0]
current >> N  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0]]
current >> Ì  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 2]
current >> /  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 4]
current >> ‚  ||  stack: [[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]
current >> ζ  ||  stack: [[[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]]
current >> ˜  ||  stack: [[[1, 0.5], [1.0, 0.75], [2.0, 1.25], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 0.5, 1.0, 0.75, 2.0, 1.25, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.5]
stack > [0]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.75]
stack > [0]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.25]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 1]
[1, 1.0, 2.0, 3]
stack > [[1, 1.0, 2.0, 3]]

Try it online with debug!

ohh so that's how ü works... this allowed me to improve one of my previous answers :-)

@scottinet [1,2,3,4] ü = [[1,2],[2,3],[3,4]], also if you add "-d" in the arguments when running 05AB1E, it produces the "debug" output that I've attached above. (Added the debug link above too). The reason pairwise is neat is because for the commands that vectorize automatically, it just applies the command pairwise (running ü) on a list shows this well).

I figured that out, it allowed me to save 1 byte on that answer. As for -d... I found about it waaay too late, after "debugging" with ,q to "print and stop". It was painful.

@scottinet I'd been using 05AB1E for a full year before learning about it :(. I used = because it doesn't pop, and just prints the last item pushed to the stack.

If you remove U you can replace X with Š.

@Emigna What in the unholy abomination of the combination of all my 05AB1E sins, how did I not know about Š. That, honestly, was the only thing I was unsure that I needed, I tried using s instead but that was still 2 bytes, same as a stack shift.

Mathematica, 72 64 59 58 bytes
(d=2;#//.x_:>Riffle[x,(x+{##2,}&@@x)/d++]~Cases~_Integer)&

Try it online!
How it works
We take the input as a list {p,q}. The iteration step is reformulated as:

Insert (a+b)/d between every two elements a and b: (x+{##2,}&@@x) computes the sequence of a+b's, with an a+Null at the end. We divide by d, and Riffle inserts each (a+b)/d between a and b. Increment d.
Pick out the Integer elements of the resulting list. (This gets rid of the Null introduced by {##2,}, too.)

This is repeated until the result doesn't change (which can only happen because we removed all the new elements, because none of them were integers).
-8 bytes thanks to @MartinEnder from using //. instead of FixedPoint (and from taking input as a list).
-6 more because ListConvolve actually isn't that great

//. trumps FixedPoint, and I'd just take input as a pair of integers instead of two separate integers: (d=2;#//.x_:>x~Riffle~ListConvolve[{1,1}/d++,x]~Cases~_Integer)&

Thanks! I keep forgetting to replace //. with FixedPoint, because I really really like FixedPoint.

It's only 64 bytes. Looks like you inserted two unprintables inside Integer.

Thanks again! I had no idea why my code kept failing after the change, and would go back to working when I did things that really shouldn't make a difference.

The code snippets in comments sometimes have these unprintable characters, especially when the code snippet has a linebreak. Not sure why SE inserts them.

Ruby, 80 bytes
->a,d=2{*b=a[0];a.each_cons 2{|x,y|z=x+y;b+=z%d>0?[y]:[z/d,y]};b==a ?a:f[b,d+1]}

Try it online!
Recursive function f taking input as the array [p, q].

Haskell, 85 81 bytes
(a:b:c)#d=a:[div(a+b)d|mod(a+b)d<1]++(b:c)#d
l#d=l
l%d|l==l#d=l|e<-d+1=l#d%e
(%2)

Try it online!
The input is taken as a list, e.g. [1,2].
Edit: -4 bytes thanks to @Laikoni.

Save two bytes with l%d|l==l#d=l|e<-d+1=l#d%e.

@Laikoni: actually it's four bytes. Thanks!

Python 2, 112 110 108 105 103 bytes
-2 bytes thanks to Jonathan Frech
-5 bytes thanks to Erik the Outgolfer

y=input()
x=d=1
while x!=y:
 d+=1;x=y;y=x[:1]
 for a,b in zip(x,x[1:]):c=a+b;y+=[c/d,b][c%d>0:]
print x

Try it online!

Is not y+=[...]*(...);y+=b, equivalent to y+=[...]*(...)+[b]?

@JonathanFrech yes

103 bytes

@EriktheOutgolfer i was trying to do this, but was on 110b @.@

Python 2, 98 bytes
f=lambda A,B=0,d=2:A*(A==B)or f(sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1]),A,d+1)

Invoke as f([p,q]). Try it online!
Jonathan Allan saved 12 bytes. Thanks~!
Explanation
f is a recursive function: f(A, B, d) evalutes to f(next_A, A, d+1), unless A == B, in which case it returns A. (This is handled by A*(A==B)or …: if A ≠ B, A*(A==B) is the empty list, which is false-y, so the … part is evaluated; if A = B then A*(A==B) is A, which is non-empty and thus truthy, and it gets returned.)
next_A is computed as:
sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])

This is best explained by example. When e.g. d = 5  and A = [1, 4, 11, 8, 21]:
  sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])
= sum([[(1+4)/d, 4], [(4+11)/d, 11], [8], [21]], [1])
= [1] + [1, 4] + [3, 11] + [8] + [21]
= [1, 1, 4, 3, 11, 8, 21]

Save 8 bytes using a zip in place of the enumerate and using [A[0]] as the sum's initial value.

Save another 4 using a recursive function

@JonathanAllan Nice! I saved another byte replacing [A[0]] with A[:1] :)

And now I’m leading by 3 bytes thanks to A*(A==B).

Husk, 22 bytes
→UG`λf£NΣẊṠeo/⁰+:.)⁰tN

Takes a 2-element list, returns list of integers and floats.
Try it online!
Explanation
→UG`λf£NΣẊṠeo/⁰+:.)⁰tN  Input is a list L.
  G                 tN  Cumulative reduce over the list [2,3,4..
                   ⁰    with initial value L
   `λ             )     using flipped version of this function:
     f£NΣẊṠeo/⁰+:.       Arguments are a list, say K=[1,3,3], and a number, say d=4.
                :.       Prepend 0.5: [0.5,1,2,3]
         Ẋ               For each adjacent pair,
               +         take their sum,
            o/⁰          divide by d,
          Ṡe             and pair it with the right number in the pair: [[0.375,1],[1.0,3],[1.5,3]]
        Σ                Concatenate: [0.375,1,1.0,3,1.5,3]
     f£N                 Remove non-integers: [1,1.0,3,3]
                        Now we have an infinite list of L threaded through 2,3,4.. using the expansion operation.
 U                      Take longest prefix of unique elements,
→                       then last element of that.

Python 2, 111 bytes
A=input()
m=d=1
while m:
 m=o=0;d+=1
 while A[o+1:]:
	o+=1;s=A[o-1]+A[o]
	if s%d<1:A[o:o]=s/d,;m=1;o+=1
print A

Try it online!
-8 thanks to Rod.
-2 thanks to Lynn.

you don't need i and a[x:x] is shorter than a.insert

@Rod Nice (ab)use of o :p

Forgo zip and save two bytes!

An alternative 111: replace the whole for loop by while A[o+1:]:o+=1;s=A[o-1]+A[o];b=s%d<1;A[o:o]=[s/d]*b;m|=b;o+=b

Röda, 90 bytes
f a,d=2{A=[a()|slide 2|[_,(_1+_)/d]if[(_1+_2)%d=0]else[_1]]+a[-1]f A,d=d+1 if[a!=A]else A}

Try it online!

Java 8, 180 bytes
import java.util.*;p->q->{List<Integer>r=new Stack();r.add(p);r.add(q);for(int d=1,f=d,i;f==d++;)for(i=1;i<r.size();i++)if((q=r.get(i)+r.get(i-1))%d<1)r.add(i++,q/(f=d));return r;}

Explanation:
Try it here.
import java.util.*;           // Required import for List and Stack

p->q->{                       // Method with two integer parameters and List return-type
  List<Integer>r=new Stack(); //  Result-list
  r.add(p);r.add(q);          //  Add the two input-integers to the List
  for(int d=1,                //  Divisible integer (starting at 1)
          f=d,                //  Temp integer (starting at `d` / also 1)
          i;                  //  Index-integer
      f==d++;)                //  Loop (1) as long as `f` and `d` are equal
                              //  (and raise `d` by 1 so it starts at 2 inside the loop)
    for(i=1;                  //   Reset index-integer to 1
        i<r.size();i++)       //   Inner loop (2) over the List
      if((q=r.get(i)+r.get(i-1))
                              //    If the current + previous items (stored in `q`)
         %d<1)                //    are divisible by `d`:
        r.add(i++,q/(f=d));   //     Insert `q` divided by `d` to the List at index `i`
                              //     (and raise `i` by 1 and set `f` to `d` in the process)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-List
}                             // End of method

C#, 280 bytes
using System.Linq;class A{static void Main(string[] p){var l=new System.Collections.Generic.List<int>(p.Select(int.Parse));int r,d=2,c;do{c=0;for(int i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);l.ForEach(v=>System.Console.Write((v+" ")));}}

First attempt at code golf, which is the whole program.
Test It
Attempt 2, 159 bytes
Taking away the scaffolding, since the task is to provide a function that can take a pair of numbers (an array works) and returns an array.
Given that a Func<int[],int[]> F can be used to satisfy the requirements, just define F:
F=v=>{var l=new List<int>(v);int i,r,d=2,c;do{c=0;for(i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);return l.ToArray();};

Test Full Program Here
This could be smaller if a generic List is considered a valid output (drop the .ToArray() to save 10 bytes).
If the input can also be modified, then passing in a List<int> instead of an array removes the need to initialize the output (comes out at 126 bytes).
Taking this a step further, there doesn't really need to be a return value in this case. Using an Action instead removes the 9 bytes used by the return statement.

Welcome to PPCG! Nice first answer.

Perl 5, 92 + 1 (-a) = 93 bytes
do{$c=0;@n=shift@F;$.++;push@n,($t=$_+$n[-1])%$.?$_:($c=$t/$.,$_)for@F;@F=@n}while$c;say"@F"

Try it online!

JavaScript (ES6), 89 87 82 bytes
Thanks @Arnauld for -2 bytes and for helping save 5 more bytes.
f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

Takes input as an array: f([p,q]).
Test Cases

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

;[[1,1],[1,2],[1,3],[2,6],[3,13],[9,9],[60,68],[144,336],[12096,24192]]
.forEach(test=>O.innerText+=JSON.stringify(test)+" -> "+JSON.stringify(f(test))+"\n")

I think you can update v (v+=b[++i]) instead of using s to save 1 byte. You may save another byte with |r instead of &&r (I think it's safe but I didn't double-check).

@Arnauld Thanks! Using |r indeed passed all the test cases.

Here is a 85-byte variant using push().

@Arnauld Nice, I originally thought of using push just once instead of twice; after revisiting that idea I came to this for 86 bytes. Maybe that can be improved?

You can do push(v,...) and then use v+= again for 84 bytes.

@Arnauld There we go! I managed to save another 2 by initializing i as i=b=[] and removing the index argument, since i'm already incrementing i. Thanks!

Retina, 111 bytes
\d+
$*1;
^
11@
{+`(1+); (1+);
$1; $1$2 $2;
(?<=(?=(1+)).*) (\1)+
 a$#2$*1;
 1+

.*a
1$&
)`a

1+@

1+
$.&
;

Try it online!
Takes the input as space separated numbers. Quite naively follows the given algorithm, with the only notable technique being to use a marker symbol, a, to note when any of the numbers had been kept. This is used to work with Retina's somewhat limited looping capabilities, which only allows you to loop until a set of stages makes no overall change to the input to those stages.
Explanation:
This will use the same example as in the question.
\d+
$*1;

We change the input array of numbers into a semicolon separated unary array, so we'd have:
1; 111111111111111111111;

^
11@

Put d into our code at the beginning, giving us:
11@1; 111111111111111111111;

{+`(1+); (1+);
$1; $1$2 $2;

This is slightly more complicated. { starts a group of stages that will be executed until they reach a fixed point. Then, + indicates that this stage itself should be executed until a fixed point. This stage adds each pair of adjacent numbers but inserts them without the additional semicolon. Now we'd have:
11@1; 1111111111111111111111 111111111111111111111;

(?<=(?=(1+)).*) (\1)+
 a$#2$*1;

The other tricky stage, this one accumulates our divisor in the first capture group, and replaces any number in our list without a trailing semicolon with that number divided by d. We also add a leading a to these numbers, to indicate that something was kept, along with the ; to indicate it should be permanently part of the array. Now we'd have:
11@1; a11111111111; 111111111111111111111;

 1+

This deletes numbers that were not divisible by d nor in the array before this round. This makes no changes in our example.
.*a
1&$

This greedily matches from the beginning of the string to the last letter a in the input. This means there can be at most one match. If we made any changes, we add one to d, otherwise leaving it the same so we can exit the loop.
111@1; a11111111111; 111111111111111111111;

)`a

The ) closes the loop started by { (don't question it!) and otherwise this stage just removes the markers we put down earlier. Since this is the end of the loop, we would repeat the above stages many times, however I'm just going to continue as though I had forgotten the loop, since it makes the example more continuous.
111@1; 11111111111; 111111111111111111111;

1+@

This stage removes from our output:
1; 11111111111; 111111111111111111111;

1+
$.&

This stage replaces the unary numbers with decimal numbers:
1; 11; 21;

;

The final stage gets rid of the semicolons:
1 11 21

Obviously, skipping out on the loop makes us have an incorrect result here, but hopefully that isn't too confusing.

My markup preview looks rather different from the output I'm seeing - anyone have any ideas? Particularly a bunch of code blocks are joining together when I don't think they should be.

Jelly, 19 bytes
®‘©‘÷@+2\⁸żFfṀR$µÐL

Try it online!


text:
Those annoying grasshoppers
The problem #6 of IMO 2009 reads:

Let a 1, a 2, a 3, ..., a n,  be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n,   A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths a 1, a 2, a 3, ..., a n in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in T.

Your task is to replicate it.

Input
Two sets S, T positive  integers, with:

S  having n distinct elements
T having n-1 elements not containing the sum of the numbers in S

Output
A montonically increasing sequence of positive integers J = b1, b 2, b 3, ..., b n,  such that:

The numbers b1, b 2-b 1, , b 3-b 2, ..., b n-b n-1 are permutation of the elements of S
J and T are disjoint

Your code should use O(P(t)) search time, where P(t) is a polynomial with degree <4
This is a code golf, so shortest maintaining the rule wins.

Good luck golfing ! Thanks to @MartinEnder for the suggestion !

I think the complexity bound is intended to be O(t^3) as opposed to o(t^4), but the non-standard way it's worded makes me reluctant to claim certainty. Could you clarify that?

@PeterTaylor TBH I don't know what O(something) means, but you can see the discussion here (For the original question) to see that you can construct a good sequence within c*n^2 searches, where c is a constant.

So you should read Wikipedia or some other resources. Having said that, what you have said means O(t^3), not o(t^4). And (if you didn't know) you can use the Sandbox to avoid generating unnecessary comments asking for clarification. | What is the parameter t?

I edited what you wrote to the standard way of expressing that. You should check if you agree, and if you did not just mean O(n^3). Right now, algorithms that run in O(n^3.9) are also allowed, which may or may not be what you want.

@Sanchises, I've rolled back your edit because it required at least quartic complexity, which definitely isn't what OP wants.

@PeterTaylor Whoops, yeah, my bad. Do you agree with just "The algorithm must run in O(n^k) with k<4"? As it stands, it makes zero sense (the OP obviously meant n rather than t, and O(P(n)) by definition equals O(n^k) with k the degree of P)

@Sanchises, your point about n rather than t is well taken, but I still don't know whether OP wants O(n^3) or o(n^4) and it seems that OP doesn't either. Since O(n^2) is apparently possible, O(n^3) should allow at least some room for golfing at the expense of complexity.

@PeterTaylor Fair enough. VTC as unclear until fixed.

What does t means in the formula O(P(t))?

@Sanchises It seems that "The algorithm must run in O(n^k) with k<4" has no difference from "The algorithm must run in O(n^4)". Did I understand correctly?

@tsh No. An algorithm that runs in O(n⁴) is disqualified, but an algorithm that runs in O(n^3.9) is valid by that rule. But it seems unlikely that a golfing answer would have a time complexity with a non-integer k, so perhaps the OP just meant O(n⁴) (if they don't know the difference between smaller than and strictly smaller than) or O(n^3) (if they are unaware that algorithms may have a complexity with O(n^k) with k a non-integer). Until they come back, we can only guess.