67

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?

Glorfindel
  • 2,743
Notamathematician
  • 3,358
  • 3
    It even seems to give all odd primes, with some repetition. – Henri Cohen Mar 15 '22 at 19:40
  • 1
    Unless I made a mistake, it suffices to show the following for all positive integers $n,d \ge 1$ (it is vacuously true if no such $r$ exists). If $r$ is the largest thing at most $d+1$ that has non-1 gcd with $n+d$, then either $n+d+r-1$ is prime or there's something at most $r$ with non-1 gcd with $n+d+r-1$. – mathworker21 Mar 15 '22 at 22:54
  • 7
    @HenriCohen Surely, if $2n-1$ is prime, then $a(n-1,n)=2n-1$. – Ilya Bogdanov Mar 16 '22 at 10:22
  • 13
    I can't understand why there are two close votes (as of this writing). – Timothy Chow Mar 16 '22 at 13:50
  • 1
    @TimothyChow: I hope moderators could intervene in these kinds of matters. Sadly, there are some users who jump to "close votes", prematurely. It appears like a pessimistic impulse. – T. Amdeberhan Mar 16 '22 at 17:25
  • 1
    @IlyaBogdanov Could you please elaborate on your comment? – Timothy Chow Mar 16 '22 at 17:41
  • 3
    @TimothyChow If $2n-1$ is prime then $a(m, n) = n + m$ for all $m$. – Sean Eberhard Mar 16 '22 at 18:30
  • 3
    @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. – John Omielan Mar 17 '22 at 10:46
  • 3
    @JohnOmielan I don't know for sure of course, but I don't think there will be counterexamples, and exactly because of the "erratic" (i.e. "random") behavior. Indeed, for reasonably large n, the termination of the iteration (i.e. first prime hit) comes so incredibly early (like, less then 1% of the total range when $n>10^6$) that a counterexample (i.e. no prime hit all the way through) would have to be more than just a bit weird, see also my comment on Sean's answer. – Joachim König Mar 17 '22 at 12:48
  • 1
    The sequence overlaps next_prime(n), for n=1,...,15. – Sebastien Palcoux Mar 24 '22 at 20:46
  • Observation in Sagemath: https://sagecell.sagemath.org/?z=eJylj80OwiAQhO9N-g57hJSa2sSLCb6I8UDkJwRYG6zvL2C11VQvzomdBeYbqTQIQQJDuq8rSLIa8MD7aZqcwHm3cLKiGm8RAWdX-atav5QT2m3KaMxZktfEsA10flBXMtF4_w8NO-LpJ5EQzDngJaZAvK9NWj0YP-CynNuIYVAoiaFfejYmfb-stHbSlwgIFiEKNIr0bNc9-w7R4kgSHBY4egcuoVn5&lang=sage&interacts=eJyLjgUAARUAuQ== – mathoverflowUser Jun 22 '23 at 06:20

2 Answers2

31

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

Carlo Beenakker
  • 177,695
27

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.

Sean Eberhard
  • 9,195
  • 5
    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. – Joachim König Mar 16 '22 at 23:57