  Motivated by a problem in the theory of integer-valued polynomials, we
investigate the natural density of the solutions of equations of the form
$\theta_uu_q(n)+\theta_ww_q(n)+\theta_2\frac{n(n+1)}{2}+\theta_1n+\theta_0\equiv
0\bmod d$, where $d,q\geq 2$ are fixed integers,
$\theta_u,\theta_w,\theta_2,\theta_1,\theta_0$ are parameters and $u_q$ and
$w_q$ are functions related to the $q$-adic valuations of the numbers between 1
and $n$. We show that the number of solutions of this equation in $[0,N)$
satisfies a recurrence relation, with which we can associate to any pair
$(d,q)$ a stochastic matrix and a Markov chain. Using this interpretation, we
calculate the density for the case $\theta_u=\theta_2=0$ and for the case
$\theta_u=1$, $\theta_w=\theta_2=\theta_1=0$ and either $d|q$ or $d$ and $q$
are coprime.
