Articles to appear in a forthcoming issue | Previous | Next

Nadir Murru; Carlo Sanna
On the $k$-regularity of the $k$-adic valuation of Lucas sequences, to appear, online on 13 December 2017, 11 p.
Article: PDF

Abstract

For integers $k \ge 2$ and $n \ne 0$, let $\nu _k(n)$ denote the greatest nonnegative integer $e$ such that $k^e$ divides $n$. Moreover, let $(u_n)_{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(u_{n + 1})_{n \ge 0}$ is $p$-regular, while Medina and Rowland found the rank of $\nu _p(F_{n + 1})_{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(u_{n + 1})_{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(u_n)$, generalizing a previous theorem of Sanna concerning $p$-adic valuations of Lucas sequences.

References

[1] J.-P. Allouche & J. Shallit, « The ring of $k$-regular sequences », Theor. Comput. Sci. 98 (1992), no. 2, p. 163-197.
[2] —, Automatic sequences: Theory, applications, generalizations, Cambridge University Press, 2003, xvi+571 pages.
[3] —, « The ring of $k$-regular sequences. II », Theor. Comput. Sci. 207 (2003), no. 1, p. 3-29.
[4] T. Amdeberhan, D. Manna & V. H. Moll, « The 2-adic valuation of Stirling numbers », Exp. Math. 17 (2008), no. 1, p. 69-82.
[5] J. P. Bell, « $p$-adic valuations and $k$-regular sequences », Discrete Math. 307 (2007), no. 23, p. 3070-3075.
[6] H. Cohn, « $2$-adic behavior of numbers of domino tilings », Electron. J. Comb. 6 (1999), no. 2, 7 pp. (electronic).
[7] S. Hong, J. Zhao & W. Zhao, « The 2-adic valuations of Stirling numbers of the second kind », Int. J. Number Theory 8 (2012), no. 4, p. 1057-1066.
[8] T. Lengyel, « The order of the Fibonacci and Lucas numbers », Fibonacci Q. 33 (1995), no. 3, p. 234-239.
[9] —, « Exact $p$-adic orders for differences of Motzkin numbers », Int. J. Number Theory 10 (2014), no. 3, p. 653-667.
[10] D. Marques & T. Lengyel, « The 2-adic order of the Tribonacci numbers and the equation $T_n=m!$ », J. Integer Seq. 17 (2014), no. 10, 8 pp. (electronic).
[11] L. A. Medina & E. Rowland, « $p$-regularity of the $p$-adic valuation of the Fibonacci sequence », Fibonacci Q. 53 (2015), no. 3, p. 265-271.
[12] A. Postnikov & B. E. Sagan, « What power of two divides a weighted Catalan number? », J. Comb. Theory, 114 (2007), no. 5, p. 970-977.
[13] M. Renault, « The period, rank, and order of the $(a,b)$-Fibonacci sequence ${\rm mod}\, m$ », Math. Mag. 86 (2013), no. 5, p. 372-380.
[14] C. Sanna, « On the $p$-adic valuation of harmonic numbers », J. Number Theory 166 (2016), p. 41-46.
[15] —, « The $p$-adic valuation of Lucas sequences », Fibonacci Q. 54 (2016), p. 118-224.
[16] Z. Shu & J. Yao, « Analytic functions over $\mathbb{Z}_p$ and $p$-regular sequences », C. R., Math., Acad. Sci. Paris 349 (2011), no. 17-18, p. 947-952.
[17] L. Somer, « The divisibility properties of primary Lucas recurrences with respect to primes », Fibonacci Q. 18 (1980), p. 316-334.
[18] X. Sun & V. H. Moll, « The $p$-adic valuations of sequences counting alternating sign matrices », J. Integer Seq. 12 (2009), no. 3, 24 pp. (electronic).