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 $k\ge 2$ et $n\ne 0$, soit ${\nu }_{k}\left(n\right)$ le plus grand entier positif $e$ tel que ${k}^{e}$ divise $n$. De plus, soit ${\left({u}_{n}\right)}_{n\ge 0}$ une suite de Lucas non dégénérée telle que ${u}_{0}=0$, ${u}_{1}=1$ et ${u}_{n+2}=a{u}_{n+1}+b{u}_{n}$, pour certains entiers $a$ et $b$. Shu et Yao ont montré que, pour tout nombre premier $p$, la suite ${\nu }_{p}{\left({u}_{n+1}\right)}_{n\ge 0}$ est $p$-régulière. Medina et Rowland ont déterminé le rang de ${\nu }_{p}{\left({F}_{n+1}\right)}_{n\ge 0}$, où ${F}_{n}$ est le $n$-ième nombre de Fibonacci.

Nous montrons que si $k$ et $b$ sont premiers entre eux, alors ${\nu }_{k}{\left({u}_{n+1}\right)}_{n\ge 0}$ 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 ${\nu }_{k}\left({u}_{n}\right)$, généralisant un théorème précédent de Sanna concernant les valuations $p$-adiques des suites de Lucas.

For integers $k\ge 2$ and $n\ne 0$, let ${\nu }_{k}\left(n\right)$ denote the greatest nonnegative integer $e$ such that ${k}^{e}$ divides $n$. Moreover, let ${\left({u}_{n}\right)}_{n\ge 0}$ be a nondegenerate Lucas sequence satisfying ${u}_{0}=0$, ${u}_{1}=1$, and ${u}_{n+2}=a{u}_{n+1}+b{u}_{n}$, for some integers $a$ and $b$. Shu and Yao showed that for any prime number $p$ the sequence ${\nu }_{p}{\left({u}_{n+1}\right)}_{n\ge 0}$ is $p$-regular, while Medina and Rowland found the rank of ${\nu }_{p}{\left({F}_{n+1}\right)}_{n\ge 0}$, where ${F}_{n}$ is the $n$-th Fibonacci number.

We prove that if $k$ and $b$ are relatively prime then ${\nu }_{k}{\left({u}_{n+1}\right)}_{n\ge 0}$ 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 ${\nu }_{k}\left({u}_{n}\right)$, 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 $\left(a,b\right)$-Fibonacci sequence $\mathrm{mod}\phantom{\rule{0.166667em}{0ex}}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))