Calculating the density of solutions of equations related to the P\'olya-Ostrowski group through Markov chains

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$arefixedintegers,$\theta_u,\theta_w,\theta_2,\theta_1,\theta_0$areparametersand$u_q$and$w_q$arefunctionsrelatedtothe$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\mathrm{\mid }q$ or $d$ and $q$ are coprime.