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:
PDFAbstract
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).