sum of odious numbers to the power of k

Question

In number theory, an odious number is a positive integer that has an odd number of $1$s in its binary expansion.

The first odious numbers are:

$1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38...$

Let $a$ denote the increasing sequence of odious numbers where $a_0=1$, $a_1=2$, etc.

Whats the summatory function of the sequence $b$ where $b_i=a_i^k$?

Also: this is useful; but it didn't give out the actual function. Please help.

Answer 1

I think there is no simple formula here, although we can get some recurrence relations and related identities for generating functions as explained below.

---

Similarly to odious numbers, we have evil numbers that contain even number of 1s in their binary representation.

Let $S^o_k(n)$ and $S^e_k(n)$ denote the sum of $k$-th powers of all odious and evil numbers $\leq n$, respectively.

It can be easily seen that each odious number has one of the two forms: $2m$ where $m$ is an odious number, or $2m+1$ where $m$ is an evil number. It follows that for $n\geq 1$ $$S^o_k(n) = S^o_k(\lfloor\tfrac{n}2\rfloor)2^k + \sum_{i=0}^k \binom{k}{i} S^e_i(\lfloor\tfrac{n-1}2\rfloor) 2^i$$ and similarly $$S^e_k(n) = S^e_k(\lfloor\tfrac{n}2\rfloor)2^k + \sum_{i=0}^k \binom{k}{i} S^o_i(\lfloor\tfrac{n-1}2\rfloor) 2^i.$$ We also have $S^o_k(0)=S^e_k(0)=0$ for all $k\geq 1$, and $S^o_0(0)=0$ and $S^e_0(0)=1$.

---

In terms of generating functions $F^o(x,y):=\sum_{n,k\geq 0} S^o_k(n) x^n \frac{y^k}{k!}$ and $F^e(x,y):=\sum_{n,k\geq 0} S^e_k(n) x^n \frac{y^k}{k!}$, we have $$F^o(x,y) = (1+x)F^o(x^2,2y) + (x+x^2) F^e(x^2,2y) e^y,$$ $$F^e(x,y) = (1+x)F^e(x^2,2y) + (x+x^2) F^o(x^2,2y) e^y.$$ Defining $G(x,y):=F^e(x,y) - F^o(x,y)$, we have $$G(x,y) = (1+x)(1 - x e^y)G(x^2,2y).$$ Also, it is easy to get $$F^e(x,y) + F^o(x,y) = \frac{1}{(1-x)(1-xe^y)}.$$

Since $G(x,y) = \frac{1}{(1-x)(1-xe^y)} - 2F^o(x,y)$, we a standalong functional equation for $F^o$: $$F^o(x,y) = (1+x)(1 - x e^y)F^o(x^2,2y) + \frac{xe^y}{(1-x)(1-x^2e^{2y})}.$$

Answer 2

Too big to comment: If we take the sequence of Gray code numbers to be $\{ g(m) \}_{m=0}^{\infty}$ then the $m$-th Odious number $Q(m)$ ($Q(0)=1,Q(1)=2...$) is the $g(m)$-th number of in the sequence of $g(2k+1), k=0,1,2,...,$

Hence, $Q(m)=g(2g(m)+1)$.

A formula for $m$-th Gray number is $$g(m)=\sum_{k=0} \sigma_i(m)2^{k-1}$$ where $\sigma_i(m)=\lfloor{\frac{|r_i(m)|}{2^k}}\rfloor$.

And, $r_i(m)=m-(\lfloor{\frac{m}{2^k}}\rfloor -(-1)^{\lfloor{\frac{m}{2^k}}\rfloor})2^k$.