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?

6more comments