莫比乌斯

aimisiyou

`f(1)=1, 2f(n)=f(1)+……f(d)+……+f(n)`,(`d` 跑遍 `n` 的约数), 则`f(n)=?`

`\D f(n)=\sum_{d|n,d<n}f(d)`

hujunhua

`f(p^k)=2^{k-1}`, (`p`为素数，`k>0` 时）
`\D f(n)=h(k)=\sum_{r=0}^{k-1}C_k^rh(r),h(0)=1`. 当 `n` 是 `k` 个不同素数之积时。

1. h[n_] :=
   
2. Module[{a},
   
3.   a[0] = 1;
   
4.   a[i_] := a[i] =Sum[Binomial[i, r] a[r],{r,0,i-1}];
   
5.   a[n]
   
6. ]
   
7. Table[h[i], {i, 0, 10}]

复制代码

h(k)的前10项：

1. {1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563}

复制代码

据此在OEIS搜得此序列为A000670

aimisiyou

hujunhua 发表于 2016-3-29 12:02
`f(p^k)=2^{k-1}`, (`p`为素数，`k>0` 时）
`f(n)=h(k)=\sum_0^{k-1}C_k^rh(r),h(0)=1`. 当 `n` 是 `k` 个 ...

\(f(n)=f(p_1^{k1}p_2^{k2}……p_i^{ki})=?\)

hujunhua

`f(n)=f(p_1^{k1}p_2^{k2}……p_i^{ki})=g(k_1,k_2,\cdots,k_i)`

这个函数的显式难解。先看看`g(1,k)`吧。
`\D g(1,k)=\sum_{i=0}^kg(0,i)+\sum_{i=0}^{k-1}g(1,i)`
记`\D s(1,k)=\sum_{i=0}^kg(1,i)`,则`g(1,k)=s(1,k)-s(1,k-1)`,代入上式得到关于`s(1,k)`的递推公式
`s(1,k)=2^k+2s(1,k-1)`
两边同时除以`2^k`，并记`t(1,k)=s(1,k)/2^k`代入得
`t(1,k)=1+t(1,k-1）`，易得`t(1,k)=k+t(1,0)=k+1`，故`s(1,k)=(k+1)\cdot2^k`
所以 `g(1,k)=s(1,k)-s(1,k-1)=(k+2)\cdot2^{k-1}`

hujunhua

仿上易得`g(2,k)=s(0,k)+s(1,k)+s(2,k-1)`
所以`s(2,k)=s(0,k)+s(1,k)+2s(2,k-1)`
                    `=2^k+(k+1)2^k+2s(2,k-1)`
                    `=(k+2)2^k+2s(2,k-1)`
两边除以`2^k`可得`t(2,k)=k+2+t(2,k-1),t(2,0)=2`,
易得 `\D t(2,k)=\frac{k(k+1)}2+2k+t(2,0)=\frac{(k+1)(k+4)}2`
所以 `\D s(2,k)=\frac{(k+1)(k+4)}2\cdot2^k`
终得 `\D g(2,k)=s(2,k)-s(2,k-1)=\frac{k^2+7k+8}2\cdot2^{k-1}`

hujunhua

`\D s(3,k)=s(0,k)+s(1,k)+s(2,k)+2s(3,k-1)`
            `\D =2^k+(k+1)\cdot2^k+\frac{k^2+7k+8}2\cdot2^k+2s(3,k-1)`
            `\D =\frac{(k+4)(k^2+11k+6)}6\cdot2^k`
`\D g(3,k)=s(3,k)-s(3,k-1)=\frac{(k+3)(k^2+9k-4)}6\cdot2^{k-1}`
------------------------------------更正----------------------------------------------------------
`\D s(3,k)=s(0,k)+s(1,k)+s(2,k)+2s(3,k-1)`
            `\D =2^k+(k+1)\cdot2^k+\frac{(k+1)(k+4)}2\cdot2^k+2s(3,k-1)`
两边除以`2^k`得 `\D t(3,k)=\frac{k^2+7k+8}2+t(3,k-1)`,`(*t(3,0)=2^{3-1}=4*)`
                                    `\D =C_k^2+4k+4+t(3,k-1)`

递加可得         `\D t(3,k)=C_{k+1}^3+4C_{k+1}^2+4k+t(3,0)=\frac{(k+1)(k+3)(k+8)}6`
即得                `\D s(3,k)=\frac{(k+1)(k+3)(k+8)}6\cdot2^k`
终得                `\D g(3,k)=s(3,k)-s(3,k-1)=\frac{(k+4)(k^2+11k+12)}6\cdot2^{k-1}`

aimisiyou

hujunhua 发表于 2016-3-30 11:50
`\D s(3,k)=s(0,k)+s(1,k)+s(2,k)+2s(3,k-1)`
            `\D =2^k+(k+1)\cdot2^k+\frac{k^2+7k+8}2\cdot ...

\(根据对称性可知g(i,j)=g(j,i),但根据你的计算g(1,3)=20 , g（3,1)=4\)

hujunhua

`\D t(r,k)-t(r,k-1)=\sum_{i=0}^{r-1}t(i,k)`
由上式递加可得`\D t(r,k)=t(r,0)+\sum_{j=1}^k\sum_{i=0}^{r-1}t(i,j)`，`(* t(r,0)=2^{r-1}*)`

hujunhua

取`r=4`代入楼上公式
`\D t(4,k)=t(4,0)+\sum_{j=1}^k\sum_{i=0}^3t(i,j)`
         `\D =t(4,0)+\sum_{j=1}^k\left(t(0,j)+t(1,j)+t(2,j)+t(3,j)\right)`
         `\D =t(4,0)+\sum_{j=1}^k\left(1+(1+j)+\frac{(j+1)(j+4)}2+\frac{(j+1)(j+3)(j+8)}6\right)`
         `\D =\frac{(k+1)(k+6)(k^2+15k+32)}{4!}`
所以`g(4,k)=s(4,k)-s(4,k-1)=(2t(4,k)-t(4,k-1))\cdot2^{k-1}`
                                     `\D =\frac{k^4+26k^3+203k^2+538k+384}{4!}\cdot2^{k-1}`

hujunhua

这个用M10编程是简单的事，直接就有一个因子和函数。

1. f[n_] :=
   
2. Module[{f},
   
3. a [1] = 1;
   
4.   a[i_] := a[i] = DivisorSum[i, a, # < i &];
   
5.   a[n]
   
6.   ]
   
7. Table[fn[i], {i, 90}]

复制代码

输出的前90项结果为
{1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, \
20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, \
8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, \
13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, \
3, 20, 1, 44}

在OEIS上搜到编号为A002033,A074206
该网站没有给出显式公式，应该是比较难解的，即使有也会十分复杂。

能通过`g(0,k), g(1,k), g(2,k), g(3,k), g(4,k)，...`表达式序列找到`g(j,k)`的通式吗？