読者です 読者をやめる 読者になる 読者になる

2進展開

非負整数関数f(x)を考えます。
xは2進数で表せます。
\displaystyle x=\sum_{k=0}^{\infty}{2^ka_k}\qquad

a_0=x\mod 2\qquad b_0=x\qquad b_n=\frac{b_{n-1}-a_{n-1}}{2}\qquad a_n=b_n\mod 2

x\quad\leftrightarrow\quad(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)
だと、
\displaystyle f(x)=\sum_{k=0}^{\infty}a_k
となり、Digit sum関数と呼ばれてるみたいです。