Solve $f^n(x)=4^nx+\frac{4^n-1}{3}$ for $n$.

Question

Solve $y=4^nx+\frac{4^n-1}{3}$ for $n$, where

$n\in\mathbb{N_{\geq0}},$

$y\in2\mathbb{N}_{\geq0}+1$ and

$x\in2\mathbb{N}_{\geq0}+1\setminus(4\mathbb{N}_{\geq0}+1\setminus8\mathbb{N}_{\geq0}+1)$.

In clearer language the process is to start with some odd integer and subtract one and divide by $4$ repeatedly until you hit some number which would take you out of the odd integers if you continued further.

The question asks you to find for any $y$, the closed form for the number of steps $n$ which can be taken.

The end-point of any sequence corresponds with $n=0$ and here $x=y$. An example is the sequence $\{\ldots213,53,13,3\}$

Answer 1

The OEIS sequence A115362 essentially gives the answer. Closed form is in the eye of the beholder. The generating function you want is $$ N(y) = \sum_{k=2}^\infty y^{(4^k-1)/3}/(1-y^{2^{2k-1}}) = y^5 + y^{13} + 2y^{21} + y^{29} + y^{37} + y^{45} + 2y^{53} + \dots$$ where the coefficents are the values you want and is essentially equivalent to your $4^nx+\frac{4^n-1}{3}.$

Answer 2

A115362 gives 1+ the 4-adic valuation of x+1, i.e:

$a(x)=v_4(x+1)+1$

The question asks for $n(y)$, the 4-adic valuation of $3y+1$

$n(y)=v_4(3y+1)$

Substituting to give $n(y)$:

$v_4(3y+1)=a(3y-2)-1$

By OEIS A115362, $a(x)=\sum_{k\geq0}x^{4^k}/(1-x^{4^k})$, therefore:

$$n(y)=\left(\sum_{k=0}^{\infty}\frac{\left(3y-2\right)^{4^k}}{1-\left(3y-2\right)^{4^k}}\right)-1$$

EDIT: The above is a generating function for $n(y)$