Function that produces primes For any $n\geq 2$ consider the recursion
\begin{align*}
a(0,n)&=n;\\
a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1. 
\end{align*}
I conjecture that $a(n-1,n)$ is always prime.
To verify it one may use this simple PARI prog:
a(n)=my(A=n, B); for(i=1, n-1, B=n-i; A+=gcd(A,B)); A;

The sequence begins
$$3, 5, 7, 11, 11, 13, 17, 17, 19, 23, 23, 29, 29, 29, 31, 41, 53, 37, 41, 41$$
The sequence is not in the OEIS.
Is there a way to prove it?
 A: For the record (not an answer), the function $a(n-1,n)$ for $n$ up to $10^4$ contains 2264 distinct primes, the largest being equal to 20369. I checked that no primes are missing. The growth rate of the primes is close to linear in $n$, see plot.

I also note the similarity with a known prime generating algorithm described by Rowland in A natural prime-generating recurrence:
$$b(n)=b(n-1)+\text{gcd}\,(b(n-1),n),$$
For small starting values $b(1)$ the difference $b(n)-b(n-1)$ is either 1 or prime. Further reading: Pumping the Primes.

 Mathematica code
out=Table[{t=RecurrenceTable[{a[m]==a[m-1]+GCD[a[m-1],n-m],a[0]==n},a,{m, 1,n-1}];{n,t[[n-1]],PrimeQ[t[[n-1]]]}},{n,2,10000}]; And @@ out[[All,1,3]]     ListPlot[out[[All,1,2]]]

A: Extended comment, generalizing @IlyaBogdanov's comment about $2n-1$. Fix $n$ and let $$x_m = a(m, n) + n - m - 1.$$ Then $(x_m)$ obeys the similar recurrence
$$
  x_m = x_{m-1} + \gcd(x_{m-1}, n-m) - 1.
$$
Also $x_0 = 2n-1$ and $x_{n-1} = a(n-1, n)$.
Now from the recurrence it is clear that if $x_m$ is prime for any value of $m < n$ then $x_{n-1} = x_m$. While $x_m$ is not prime it is increasing slowly and erratically, so it has plenty of chances to hit a prime.
