Prime divisors of the Lagarias sequence
Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 1, p. 241-251

We solve a 1985 challenge problem posed by Lagarias [5] by determining, under GRH, the density of the set of prime numbers that occur as divisor of some term of the sequence x n n=1 defined by the linear recurrence x n+1 =x n +x n-1 and the initial values x 0 =3 and x 1 =1. This is the first example of a ænon-torsionÆ second order recurrent sequence with irreducible recurrence relation for which we can determine the associated density of prime divisors.

Nous donnons une solution à un problème posé par Lagarias [5] en 1985, en déterminant sous GRH la densité de l’ensemble des nombres premiers qui sont des diviseurs de termes de la suite x n n=1 définie par x 0 =3,x 1 =1 et la relation de récurrence x n+1 =x n +x n-1 . Cela donne le premier exemple d’une suite de récurrence d’ordre 2 qui n’est pas æà torsionÆ pour laquelle on sait déterminer la densité associée des diviseurs premiers.

@article{JTNB_2001__13_1_241_0,
     author = {Moree, Pieter and Stevenhagen, Peter},
     title = {Prime divisors of the Lagarias sequence},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {13},
     number = {1},
     year = {2001},
     pages = {241-251},
     zbl = {1064.11013},
     mrnumber = {1838084},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2001__13_1_241_0}
}
Moree, Pieter; Stevenhagen, Peter. Prime divisors of the Lagarias sequence. Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 1, pp. 241-251. http://www.numdam.org/item/JTNB_2001__13_1_241_0/

[1] C. Ballot, Density of prime divisors of linear recurrent sequences. Mem. of the AMS 551, 1995. | Zbl 0827.11006

[2] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene rationale Zahl a ≠ 0 von durch eine vorgegebene Primzahl l ≠ 2 teilbarer bzw. unteilbarer Ordnung mod p ist. Math. Ann. 162 (1965), 74-76. | MR 186653 | Zbl 0135.10203

[3] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a ≠ 0 von gerader bzw. ungerader Ordnung mod p ist. Math. Ann. 166 (1966), 19-23. | MR 205975 | Zbl 0139.27501

[4] C. Hooley, On Artin's conjecture. J. Reine Angew. Math. 225 (1967), 209-220. | MR 207630 | Zbl 0221.10048

[5] J.C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3. Pacific J. Math. 118 (1985), 449-461; Errata Ibid. 162 (1994), 393-397. | MR 789184 | Zbl 0569.10003

[6] S. Lang, Algebra, 3rd edition. Addison-Wesley, 1993. | MR 197234 | Zbl 0848.13001

[7] H.W. Lenstra, JR, On Artin's conjecture and Euclid's algorithm in global fields. Inv. Math. 42 (1977), 201-224. | MR 480413 | Zbl 0362.12012

[8] P. Moree, P. Stevenhagen, Prime divisors of Lucas sequences. Acta Arith. 82 (1997), 403-410. | MR 1483692 | Zbl 0913.11048

[9] P. Moree, P. Stevenhagen, A two variable Artin conjecture. J. Number Theory 85 (2000), 291-304. | MR 1802718 | Zbl 0966.11042

[10] P.J. Stephens, Prime divisors of second order linear recurrences. J. Number Theory 8 (1976), 313-332. | MR 417081 | Zbl 0334.10018

[11] P. Stevenhagen, Prime densities for second order torsion sequences. preprint (2000).