Does this sum go infinity? Consider a map $F:\Bbb N\to\{\pm 1\}$ such that


*

*when $x$ is odd, 
$
F(x):=(-1)^{(\frac{x-1}{2})};
$

*when $x$ is even, $F(x):=F(y)$, where $y$ is the odd number obtained after dividing $x$ by $2$ until it is odd.


Does $S_n = \sum_{p=1}^n F(p)$ have an explicit formula?
And if $n$ tends to $\infty$ does the sum alternates or will it lie between an interval or does it tend to $\pm \infty$ ?
 A: Let $T(n) = \sum_{k\text{ is odd, } k\le n}F(k)$. We can easily see that $T(0)=0$, $T(1)=1$, $T(2)=1$, $T(3)=0$, and $T(n+4)=T(n)$ for all $n\ge 0$. This is $1$ if the last two bits of $n$ (when expressed in binary) are different, and $0$ if they are the same.
Then, $T(\lfloor n/2\rfloor) = \sum_{k\text{ is odd, } k\le \lfloor n/2\rfloor}F(k)=\sum_{k\text{ is odd, } 2k\le n}F(2k)$, $T(\lfloor n/4\rfloor) = \sum_{k\text{ is odd, } 4k\le n}F(4k)$, and so on. Every nonzero integer is equal to $2^m k$ for some nonnegative $m$ and odd $k$. As such, we can take a sum, and get
$$S_n = T(n)+T(\lfloor n/2\rfloor)+T(\lfloor n/4\rfloor)+\cdots = \sum_{m=0}^{\lfloor \log_2 n\rfloor}T(\lfloor n/2^m\rfloor)$$
Each term is $1$ if two particular adjacent bits of $n$ are different and zero if they're equal - the $1$ bit and the $2$ bit for $T(n)$, the $2$ bit and the $4$ bit for $T(\lfloor n/2\rfloor)$, the $4$ bit and the $8$ bit for $T(\lfloor n/4\rfloor)$, and so on.
Sum them up, and $S_n$ is the number of times the sequence of bits switches between $0$ and $1$. Among $m$-bit numbers, this can be as low as $1$ for $n=2^m-1$ (the first switch, from $0$ in the $2^m$ place to $1$ in the $2^{m-1}$ place, is always there) or as high as $m$ for $n=\lfloor 2^{m+1}/3\rfloor$.
So, there it is - an explicit form for $S_n$, and a sequence $1,2,5,10,21,42,85,\dots$ for which $S_n$ goes to $\infty$.
