1

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\}$

it's a hire car baby
  • 9,243

3 Answers3

3

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}.$

Somos
  • 35,251
  • 3
  • 30
  • 76
  • Thanks, so if I understand correctly the closed form would be $n(y) = \sum_{k\geq0} \frac{y^{4^k}}{1-y^{4^k}}$ – it's a hire car baby Jul 13 '17 at 20:37
  • No. I tried to gently suggest that the answer depends on what you allow in "closed form". See the OES entry for more info. – Somos Jul 13 '17 at 20:39
  • I can allow 2-adic numbers if we need to sum to infinity – it's a hire car baby Jul 13 '17 at 20:40
  • The simplest answer is in Joerg Arndt formula. So you want $1 +$ the 4-adic valuation of $3n+1$. – Somos Jul 13 '17 at 20:43
  • The Joerg Arndt format I already knew! In fact that was the step which came before finding the closed form for $4x+1$. Have I understood the Frank Ruskey form correctly in my first comment on your answer? I think you're saying I need to take every 3rd value in this series. – it's a hire car baby Jul 13 '17 at 20:52
  • Yes, that is why I wrote $a(3n)$. So what are you still missing? – Somos Jul 13 '17 at 20:57
  • Nothing, I'm just a bit slow and I like to be sure I've understood correctly. – it's a hire car baby Jul 14 '17 at 02:53
  • Thank-you for this very helpful answer. If you edit it (or permit me to do so) to state that $n(y) = \sum_{k\geq0} \frac{(3y)^{4^k}}{1-(3y)^{4^k}}$, assuming I have interpreted correctly, then I can accept. – it's a hire car baby Jul 14 '17 at 13:18
  • $n(1)=0$ because from $1$ you cannot subtract $1$ and divide by $4$ without leaving the odd integers, but your function diverges. $n(5)=1$ because you can take $1$ step (i.e. from $5$ to $1$) before you can go no further. $n(21)=2$ because you can subtract by $1$ and divide by $4$ twice before leaving the integers, taking you from $21$ to $5$ to $1$ but your function of $5$ and $21$ takes on negative values for these: http://www.wolframalpha.com/input/?i=%5Csum_%7Bk%3D0%7D%5E%5Cinfty+5%5E%7B(4%5Ek-1)%2F3%7D%2F(1-5%5E%7B4%5Ek%7D) Have u perhaps not included the subtraction by $1$ in iteration? – it's a hire car baby Jul 18 '17 at 17:19
  • I have modified my summation to address your comment. – Somos Jul 18 '17 at 18:14
  • I'm not going to accept my answer but it was too long for a comment. I get that. Does that equate to what you put, or has one of us made an error? I put some values into your formula in wolfram alpha and got negative fractions again. Not sure though if that's wolfram's inability to resolve the series. – it's a hire car baby Jul 19 '17 at 08:29
2

Taking the OGS (ordinary generating series) gives $$ \sum_{n\geq 0}(4^n.x+\frac{4^n−1}{3})z^n=(x+\frac{1}{3})\sum_{n\geq 0}(4^n)z^n-\frac{1}{3}\sum_{n\geq 0}z^n=\frac{x+\frac{1}{3}}{1-4z}+\frac{1}{3(1-z)} $$ from the singularities, you see that $f^n(x)\sim_{+\infty}4^n(x+\frac{1}{3})$ and, in fact, $$ f^n(x)+\frac{1}{3}=4^n(x+\frac{1}{3}) $$ so, you get $n$ from $y$ by $$ n=log_4(\frac{y+\frac{1}{3}}{x+\frac{1}{3}})=\frac{1}{log(4)}log(\frac{y+\frac{1}{3}}{x+\frac{1}{3}}) $$

Is it what you wanted ?

Duchamp Gérard H. E.
  • 3,564
  • Thanks. This looks incredibly useful but I'm not familiar with generating functions so I will take a bit of time to digest, plug in a few values and most likely accept in due course. – it's a hire car baby Feb 19 '18 at 11:15
  • 1
    @RobertFrost You can skip the OGF part. I just wanted to give my progression, how I came to this simple result, but logically speaking, it can be withdrawn. Just begin at $$ f^n(x)+\frac{1}{3}=4^n(x+\frac{1}{3}) $$ – Duchamp Gérard H. E. Feb 19 '18 at 13:38
0

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)$

it's a hire car baby
  • 9,243