69
$\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?

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ It even seems to give all odd primes, with some repetition. $\endgroup$
    – Henri Cohen
    Commented Mar 15, 2022 at 19:40
  • 7
    $\begingroup$ @HenriCohen Surely, if $2n-1$ is prime, then $a(n-1,n)=2n-1$. $\endgroup$
    – Ilya Bogdanov
    Commented Mar 16, 2022 at 10:22
  • 13
    $\begingroup$ I can't understand why there are two close votes (as of this writing). $\endgroup$
    – Timothy Chow
    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$
    – Sean Eberhard
    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$
    – John Omielan
    Commented Mar 17, 2022 at 10:46

2 Answers 2

Reset to default
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]]]

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ What is the (approximate) slope of that line? $\endgroup$
    – André Henriques
    Commented Mar 22, 2022 at 11:06
  • 2
    $\begingroup$ the slope is close to 2 $\endgroup$
    – Carlo Beenakker
    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$
    – Carlo Beenakker
    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
28
$\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.

Improve this answer
$\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$
    – Joachim König
    Commented Mar 16, 2022 at 23:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .