67
$\begingroup$

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?

$\endgroup$
11
  • 3
    $\begingroup$ It even seems to give all odd primes, with some repetition. $\endgroup$ Commented Mar 15, 2022 at 19:40
  • 7
    $\begingroup$ @HenriCohen Surely, if $2n-1$ is prime, then $a(n-1,n)=2n-1$. $\endgroup$ Commented Mar 16, 2022 at 10:22
  • 13
    $\begingroup$ I can't understand why there are two close votes (as of this writing). $\endgroup$ Commented Mar 16, 2022 at 13:50
  • 3
    $\begingroup$ @TimothyChow If $2n-1$ is prime then $a(m, n) = n + m$ for all $m$. $\endgroup$ Commented Mar 16, 2022 at 18:30
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Mar 17, 2022 at 10:46

2 Answers 2

31
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ What is the (approximate) slope of that line? $\endgroup$ Commented Mar 22, 2022 at 11:06
  • 2
    $\begingroup$ the slope is close to 2 $\endgroup$ Commented Mar 22, 2022 at 11:10
  • $\begingroup$ 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 ... $\endgroup$
    – EGME
    Commented Aug 1, 2022 at 15:27
  • $\begingroup$ I will try, later in August, when I’m back from vacation and have access to Mathematica. $\endgroup$ Commented Aug 1, 2022 at 15:38
  • $\begingroup$ Hi Carlo, did you ever try to do this? I would be interested in looking at it if you did $\endgroup$
    – EGME
    Commented Oct 30, 2022 at 18:33
27
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Mar 16, 2022 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.