2
$\begingroup$

Does some nontrivial Lucas sequence contain infinitely many primes?

The Mersenne numbers $M_n=2^n-1:n$ not necessarily prime are a Lucas sequence with recurrence relation $x_{n+1}=2x_n+1$.

It's an open problem how many Mersenne numbers are prime and we know neither whether $0\%$ or $100\%$ are prime (asymptotically speaking).

There are also similar sequences of repunits base $n$ with some nice maths surrounding them.

There are Lucas sequences having primes up to some point and then no more primes, such as the sequence with the relation $x_{n+1}=4x_n+1$ given by $1,5,21,85,341,\ldots$ for which it can be shown that there are no more primes beyond $5$.

We can also find sequences having no primes at all such as the sequence with the same relation but starting at $8$, given by $8,33,133,533,\ldots$ - and in fact it is true for any sequence for which $3x_0+1$ is a square that it has no primes - so we can say there are infinitely many Lucas sequences having no primes.

The obvious case to ask is whether infinitely many of the Fibonacci numbers are prime - and this is another open problem.

Is it known, or is it possible to show, that there is some (nontrivial) Lucas sequence (identifiable or otherwise), having infinitely many primes, or that there is none?

$\endgroup$
  • $\begingroup$ @vadim123 I could've sworn I put "nontrivial" in the question! I must've edited it out - I've put it back in, sorry. $\endgroup$ – samerivertwice Nov 3 '18 at 19:21
  • $\begingroup$ Also, Lucas sequences are normally (a) second-order; and (b) nonhomogeneous. Neither of the two examples given satisfy those criteria. $\endgroup$ – vadim123 Nov 3 '18 at 19:22
  • $\begingroup$ @vadim123 I can't find any reference of what you mean there. By 2nd order does this mean expressing $U_{n+2}$ in terms of $U_n$ and $U_{n-1}$ as done here: math.stackexchange.com/questions/2705983 rather than expressing $U_{n+1}$? $\endgroup$ – samerivertwice Nov 4 '18 at 12:07
  • $\begingroup$ Lucas sequence, homogeneous, order. $\endgroup$ – vadim123 Nov 4 '18 at 22:15
  • $\begingroup$ @vadim123 thanks, plenty to digest there, I'll work through it. I'd come across characteristic polynomials before and wanted to understand better too. It's a long shot but do you know of some obvious link between these characteristic polynomials and the Cantor pairing function? My particular interest is whether a certain form of power series may be the limit of polynomial pairing (tuple) functions as the degree approaches infinity. $\endgroup$ – samerivertwice Nov 4 '18 at 22:32
1
$\begingroup$

Although it has been conjectured, and may be widely believed that most Lucas sequences contain infinitely many primes, we have yet to find even one that does. There are, however, nontrivial such sequences that that have been shown to contain no primes at all! Richard Guy gives several examples in section A3 of his 2nd edition of ``Unsolved Problems in Number Theory.''

The Lehmer and companion Lehmer sequences are generalizations of the Lucas and companion Lucas sequences (of which, respectively, the sequence of Fibonacci numbers and the sequence of Lucas numbers are members of) are not currently known to have produced a sequence where it has been shown to contain infinitely many primes, albeit the conjecture seems to be many if not most do according to Richard Guy who uses the term ``Lucas-Lehmer sequences'' though his book is the only place I recall where that term is specifically used.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ interesting you say it's widely believed that most do contain infinitely many primes, as based on my experience I'd be more inclined to come down on the the side of few or none containing infinitely many primes! Every linear combination of increasing sequences has a least element within the positive integers, and the "infinitely many primes" property seems to belong to these elements which index the linear combinations of sequences, rather than to the elements within the sequences. At least that's the way it appears to me. $\endgroup$ – samerivertwice Jun 27 '19 at 9:32
  • 1
    $\begingroup$ @user334732 That's the impression I was left with from R. K. Guy's book. $\endgroup$ – mlchristians Jun 27 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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