Let $(u_n)_{n \geq 0}$ be an integer-valued linear recurrence of order $k \geq 1$. Precisely, $$u_n = a_1 u_{n-1} + \cdots + a_k u_{n - k} \quad \forall n \geq k ,$$ for some $a_1, \ldots, a_k \in \mathbb{Z}$.

Given a prime number $p$, I wonder: **How much is known about the $p$-adic valuation $\upsilon_p(u_n)$? Are there some "explicit" formulas?**

$\bullet$ For $k=1$, we have simply a geometric progression and clearly it holds $$\upsilon_p(u_n) = \upsilon_p(a_1)^n + \upsilon_p(u_0).$$

$\bullet$ For $k=2$, the problem was studied (in the more general setting of linear recurrences in the field of $p$-adic numbers) by Ward [1], who gave formulas for $\upsilon_p(u_n)$. However, those formulas rely on the computation of a $p$-adic number $v$ (see Theorem 10.1) which is essential as much as difficult as the computation of $\upsilon_p(u_n)$, so they do not seem to give really useful information on $\upsilon_p(u_n)$ (see Vesselin Dimitrov comments).

The particular case of the Fibonacci sequence $(F_n)_{n \geq 0}$ was also studied by Lengyel [2], who gave practical closed expressions for $\upsilon_p(F_n)$, in terms of $\upsilon_p(n)$, $z(p) := \min\{n > 0 : p \mid F_n\}$, and $e(p) := \upsilon_p(F_{z(p)})$.

$\bullet$ For $k\geq 3$ it seems to me that nothing general is known. I found only another article of Lengyel [3] about the $2$-adic valuation of the Tribonacci numbers $(T_n)_{n \geq 0}$.

Surely, without loss of generality, it can be assumed that: $(u_n)_{n \geq 0}$ is not degenerate; it has at least one zero modulo $p$ (and that can be effectively checked since $(u_n)_{n \geq 0}$ is periodic modulo $p$ and the period length is less than $p^k$); $u_0 \equiv 0 \bmod p$, eventually by shifting $(u_n)_{n \geq 0}$.

Thank you in advance for possible ideas and references!

[1] *M. Ward. The linear p-adic recurrence of order two. Illinois J. Math. (6) 40--52, 1962.*

[2] *T. Lengyel. The order of the Fibonacci and Lucas numbers. The
Fibonacci Quarterly, (33) 234--239, 1995.*

[3] *T. Lengyel. The 2-adic Order of the Tribonacci Numbers and the Equation $T_n = m!$. Journal of Integer Sequences Vol. 17, 2014.*

7more comments