# 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?

• It even seems to give all odd primes, with some repetition. Commented Mar 15, 2022 at 19:40
• @HenriCohen Surely, if $2n-1$ is prime, then $a(n-1,n)=2n-1$. Commented Mar 16, 2022 at 10:22
• I can't understand why there are two close votes (as of this writing). Commented Mar 16, 2022 at 13:50
• @TimothyChow If $2n-1$ is prime then $a(m, n) = n + m$ for all $m$. Commented Mar 16, 2022 at 18:30
• @Notamathematician FYI, I wrote & ran (for over $13$ hours!) a relatively optimized C++ program. The main optimization is that, similar to what's explained in Sean's answer, if $b = a(m-1,n) + n - m$ is prime, then $a(n-1,n) = b$, so can skip the remaining iterations. I have checked some of my results against PARI/GP output using code similar to yours to help verify my program worked properly. Anyway, no counter-examples up to $5 \times 10^8$ were found. Nonetheless, I suspect there'll be a few eventually due to the "erratic" aspect of the increases stated in Sean's answer. Commented Mar 17, 2022 at 10:46

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

• What is the (approximate) slope of that line? Commented Mar 22, 2022 at 11:06
• the slope is close to 2 Commented Mar 22, 2022 at 11:10
• Carlo, are you able to modify your M code above as per the answer below so as to make it "almost instantaneous", as Joachim remarks, to check this up to 10¨6? I am not sure I can. It would be nice to check this beyond that. Many conjectures about primes fail at very large numbers ...
– EGME
Commented Aug 1, 2022 at 15:27
• I will try, later in August, when I’m back from vacation and have access to Mathematica. Commented Aug 1, 2022 at 15:38
• Hi Carlo, did you ever try to do this? I would be interested in looking at it if you did
– EGME
Commented Oct 30, 2022 at 18:33

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.

• Very useful observation, both for sake of computation (almost instantly verifiable that the conjecture holds beyond $10^6$) and heuristic argument: if $x_m$ above remains composite, a jump should occur at least around $\sqrt{n}$ times (and probably indeed much for frequently), whereas if things behave randomly, a prime would tend to come up after around $\log(n)$ jumps. Commented Mar 16, 2022 at 23:57