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

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.

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.

Received:
Accepted:
Published online:
DOI: 10.5802/jtnb.1025
Classification: 11B37, 11B85, 11A99
Keywords: Lucas sequence, Fibonacci numbers, $p$-adic valuation, $k$-regular sequence, automatic sequence
Murru, Nadir 1; Sanna, Carlo 1

1 Università degli Studi di Torino Department of Mathematics Via Carlo Alberto 10 10123 Torino, Italy
@article{JTNB_2018__30_1_227_0,
     author = {Murru, Nadir and Sanna, Carlo},
     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},
     mrnumber = {3809718},
     zbl = {1446.11024},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.1025/}
}
TY  - JOUR
AU  - Murru, Nadir
AU  - Sanna, Carlo
TI  - On the $k$-regularity of the $k$-adic valuation of Lucas sequences
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2018
SP  - 227
EP  - 237
VL  - 30
IS  - 1
PB  - Société Arithmétique de Bordeaux
UR  - http://www.numdam.org/articles/10.5802/jtnb.1025/
DO  - 10.5802/jtnb.1025
LA  - en
ID  - JTNB_2018__30_1_227_0
ER  - 
%0 Journal Article
%A Murru, Nadir
%A Sanna, Carlo
%T On the $k$-regularity of the $k$-adic valuation of Lucas sequences
%J Journal de théorie des nombres de Bordeaux
%D 2018
%P 227-237
%V 30
%N 1
%I Société Arithmétique de Bordeaux
%U http://www.numdam.org/articles/10.5802/jtnb.1025/
%R 10.5802/jtnb.1025
%G en
%F JTNB_2018__30_1_227_0
Murru, Nadir; Sanna, Carlo. On the $k$-regularity of the $k$-adic valuation of Lucas sequences. Journal de théorie des nombres de Bordeaux, Volume 30 (2018) no. 1, pp. 227-237. doi : 10.5802/jtnb.1025. http://www.numdam.org/articles/10.5802/jtnb.1025/

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

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

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

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

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

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

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

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

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

[10] Marques, Diego; Lengyel, Tamás 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) | MR | Zbl

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

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

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

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

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

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

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

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

Cited by Sources: