２進展開

数学

非負整数関数f(x)を考えます。
xは２進数で表せます。
\displaystyle x=\sum_{k=0}^{\infty}{2^ka_k}
a_0=x mod 2\\b_0=x\\b_n=\frac{b_{n-1}-a_{n-1}}{2}\\a_n=b_n mod 2
x\leftrightarrow(a_0\;,a_1\;,\cdots)

ここで、0\leq x\leq3に対して、
f(x)=F(0)+F(1)a_0+F(2)a_1+F(3)a_0a_1
とおくと、
f(0)=F(0)\\ f(1)=F(0)+F(1)\\ f(2)=F(0)+F(2)\\ f(3)=F(0)+F(1)+F(2)+F(3)
となり、
F(0)=f(0)\\ F(1)=f(1)-f(0)\\ F(2)=f(2)-f(0)\\ F(3)=f(3)-(f(2)+f(1))+f(0)
と、F(x)が一意に決まります。

これを一般化すると、0\leq x\leq2^{n+1}-1の時、
\displaystyle f(x)=\sum_{S\subset X}F\left(\sum_{a_k\in S}2^k\right)\prod_{a_k\in S}a_k\\ F\left(\sum_{a_k\in S}2^k\right)=\sum_{T\subset S}(-1)^{|S-T|}f\left(\sum_{a_k\in T}2^k\right)
X=\left\{a_0\;,a_1\;,\cdots\;,a_n\right\}
となります。nが無限でも、成り立つと思います。

フーリエ級数の整数関数版とも言うべきでしょうか？

\displaystyle F\left(\sum_{a_k\in S}2^k\right)=\left\{1\quad(|S|=1)\\0\quad(|S|\not=1)\right.
だと、
\displaystyle f(x)=\sum_{k=0}^{\infty}a_k
となり、Digit sum関数と呼ばれてるみたいです。