On the k-regularity of the k-adic valuation of Lucas sequences
Journal de Théorie des Nombres de Bordeaux, Tome 30 (2018) no. 1, pp. 227-237.

Pour tous entiers k2 et n0, soit ν k (n) le plus grand entier positif e tel que k e divise n. De plus, soit (u n ) n0 une suite de Lucas non dégénérée telle que u 0 =0, u 1 =1 et u n+2 =au n+1 +bu n , pour certains entiers a et b. Shu et Yao ont montré que, pour tout nombre premier p, la suite ν p (u n+1 ) n0 est p-régulière. Medina et Rowland ont déterminé le rang de ν p (F n+1 ) n0 , où F n est le n-ième nombre de Fibonacci.

Nous montrons que si k et b sont premiers entre eux, alors ν k (u n+1 ) n0 est une suite k-régulière. Si de plus k est un nombre premier, nous déterminons aussi le rang de cette suite. En outre, nous donnons des formules explicites pour ν k (u n ), généralisant un théorème précédent de Sanna concernant les valuations p-adiques des suites de Lucas.

For integers k2 and n0, let ν k (n) denote the greatest nonnegative integer e such that k e divides n. Moreover, let (u n ) n0 be a nondegenerate Lucas sequence satisfying u 0 =0, u 1 =1, and u n+2 =au n+1 +bu n , for some integers a and b. Shu and Yao showed that for any prime number p the sequence ν p (u n+1 ) n0 is p-regular, while Medina and Rowland found the rank of ν p (F n+1 ) n0 , where F n is the n-th Fibonacci number.

We prove that if k and b are relatively prime then ν k (u n+1 ) n0 is a k-regular sequence, and for k a prime number we also determine its rank. Furthermore, as an intermediate result, we give explicit formulas for ν k (u n ), generalizing a previous theorem of Sanna concerning p-adic valuations of Lucas sequences.

Reçu le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.1025
Classification : 11B37,  11B85,  11A99
Mots clés : Lucas sequence, Fibonacci numbers, p-adic valuation, k-regular sequence, automatic sequence
@article{JTNB_2018__30_1_227_0,
     author = {Nadir Murru and Carlo Sanna},
     title = {On the $k$-regularity of the $k$-adic valuation of {Lucas} sequences},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {227--237},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {30},
     number = {1},
     year = {2018},
     doi = {10.5802/jtnb.1025},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1025/}
}
Nadir Murru; Carlo Sanna. On the $k$-regularity of the $k$-adic valuation of Lucas sequences. Journal de Théorie des Nombres de Bordeaux, Tome 30 (2018) no. 1, pp. 227-237. doi : 10.5802/jtnb.1025. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1025/

[1] Jean-Paul Allouche; Jeffrey Shallit The ring of k-regular sequences, Theor. Comput. Sci., Volume 98 (1992) no. 2, pp. 163-197 | Article

[2] Jean-Paul Allouche; Jeffrey Shallit Automatic sequences: Theory, applications, generalizations, Cambridge University Press, 2003, xvi+571 pages

[3] Jean-Paul Allouche; Jeffrey Shallit The ring of k-regular sequences. II, Theor. Comput. Sci., Volume 207 (2003) no. 1, pp. 3-29 | Article

[4] Tewodros Amdeberhan; Dante Manna; Victor H. Moll The 2-adic valuation of Stirling numbers, Exp. Math., Volume 17 (2008) no. 1, pp. 69-82 | Article

[5] Jason P. Bell p-adic valuations and k-regular sequences, Discrete Math., Volume 307 (2007) no. 23, pp. 3070-3075 | Article

[6] Henry Cohn 2-adic behavior of numbers of domino tilings, Electron. J. Comb., Volume 6 (1999) no. 2 (7 pp. (electronic))

[7] Shaofang Hong; Jianrong Zhao; Wei Zhao The 2-adic valuations of Stirling numbers of the second kind, Int. J. Number Theory, Volume 8 (2012) no. 4, pp. 1057-1066 | Article

[8] Tamás Lengyel The order of the Fibonacci and Lucas numbers, Fibonacci Q., Volume 33 (1995) no. 3, pp. 234-239

[9] Tamás Lengyel Exact p-adic orders for differences of Motzkin numbers, Int. J. Number Theory, Volume 10 (2014) no. 3, pp. 653-667 | Article

[10] Diego Marques; Tamás Lengyel The 2-adic order of the Tribonacci numbers and the equation T n =m!, J. Integer Seq., Volume 17 (2014) no. 10 (8 pp. (electronic))

[11] Luis A. Medina; Eric Rowland p-regularity of the p-adic valuation of the Fibonacci sequence, Fibonacci Q., Volume 53 (2015) no. 3, pp. 265-271

[12] Alexander Postnikov; Bruce E. Sagan What power of two divides a weighted Catalan number?, J. Comb. Theory,, Volume 114 (2007) no. 5, pp. 970-977 | Article

[13] Marc Renault The period, rank, and order of the (a,b)-Fibonacci sequence mod m, Math. Mag., Volume 86 (2013) no. 5, pp. 372-380 | Article

[14] Carlo Sanna On the p-adic valuation of harmonic numbers, J. Number Theory, Volume 166 (2016), pp. 41-46 | Article

[15] Carlo Sanna The p-adic valuation of Lucas sequences, Fibonacci Q., Volume 54 (2016), pp. 118-224

[16] Zhang Shu; Jiayan Yao Analytic functions over p and p-regular sequences, C. R., Math., Acad. Sci. Paris, Volume 349 (2011) no. 17-18, pp. 947-952 | Article

[17] Lawrence Somer The divisibility properties of primary Lucas recurrences with respect to primes, Fibonacci Q., Volume 18 (1980), pp. 316-334

[18] Xinyu Sun; Victor H. Moll The p-adic valuations of sequences counting alternating sign matrices, J. Integer Seq., Volume 12 (2009) no. 3 (24 pp. (electronic))