Prime divisors of the Lagarias sequence

Moree, Pieter ; Stevenhagen, Peter 

Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 1, pp. 241-251

Abstract (VO)

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 ${\left\{x_n\right\}}_{n=1}^{\infty }$ 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.

Résumé

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 ${\left\{x_n\right\}}_{n=1}^{\infty }$ 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.