How to find the n'th number in this sequence

Question

The first numbers of the sequence are {2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2}.

I.e. the even indexed elements are 1. Removing those yields a new sequence where the odd indexed elements are 2. Removing those yields a new sequence where the odd indexed elements are 3. Etc.

In fact what I need is the sum of the first $n$ elements for all $n\in\mathbb{N}$. I tried to use the binary digit counts of $n$ but I haven't find something useful.

Answer 1

The n-th term is equal to the largest power of 2 which divides (n+1), plus 1.

In other words if $n+1=2^lm$ in which l is non-negative and m is odd, then $a_n=l+1$.

(For example the 11-th term is equal to 2+1,since $2^2$ divides 12 but not $2^3$, the 23-th term is equal to 3+1, because $2^3$ is the greatest power which divides 24).

Also we have $a_1+a_2+...+a_n=$ {the largest power of 2 which divides $(n+1)!$ }+n.

---

In a more formal language

$a_n=v_2(n+1)+1$.

Sum of the first n elements$=n+v_2((n+1)!)$

$v_2(t)$ stands for the largest power of 2 which divides t.

Answer 2

Notice that we have that every 2 terms is a 1, every 4 terms is a 2, every 8 terms is a 3. In general, every $2^n $ terms we have the term $n $ for $n>0$. To make this easier we will append a 1 to the beginning of the sequence. Hence the sum of the first $N $ terms is $$S'=\sum_{n=1}^{\infty}\left(1+\left\lfloor\frac {N-2^{n-1}}{2^n}\right\rfloor\right) n$$ Things get a little weird because we have to account for when the first number, say for example $5$ starts occurring. Notice how every number $n$ makes its first appearance on the $2^{n-1}$ term rather than the $2^n$ after we append a 1 to the beginning.
Moreover we sum to infinity however at some point the terms become zero and we can stop summing. To see when this is, notice that the argument inside the floor function is strictly decreasing as $n\to\infty$ so we check when $$\frac{N-2^{n-1}}{2^n}=1$$ Which solving for $n$ tells us that this occurs when $$n=\log_2\left(\frac{2N}{3}\right)$$ But because we are dealing with integer values of $n$ (because it is an index in our summation) we only need to sum up to the index $$n=P=\left\lfloor \log_2\left(\frac{2N}{3}\right) \right\rfloor$$ So really if we call the sequence $\{ a_n \} $ (this being the original sequence with a one appended), then $$S'=\sum_{n=1}^N a_n=\sum_{n=1}^{P}\left(1+\left\lfloor\frac {N-2^{n-1}}{2^n}\right\rfloor\right) n$$ Which finally accounting for the 1 we appended, we can get the sum for the original sequence by subtracting 1 from the sum and setting $N\to N-1$.

Answer 3

The $n^\text{th}$ number in the sequence is $1$ more than the number of consecutive $1$'s at the end of the binary representation of $n.$ $$ $$ For any $n \ge 1,$ the sum of the first $n$ members in the sequence is:

$2n$ minus the number of $1$'s in the binary representation of $n$ that are not in a final consecutive block of $1$'s at the rightmost end of the number.

$$ $$

For example:

If $n \ge 2$ is a power of $2,$ then the sum of the first $n$ numbers in the sequence is $2n-1$ (since there's a single $1$ in the binary representation of $n$ and it's not at the far right).

If $n$ is any even number, then the sum of the first $n$ numbers in the sequence is $2n$ minus the total number of $1$'s in the binary representation of $n$ (since none of those $1$'s are at the far right).

If $n$ is $1$ less than a power of $2,$ then the sum of the first $n$ numbers in the sequence is $2n$ (since all the $1$'s in the binary representation of $n$ are in the final consecutive block at the far right).