求助大佬 , 关于 Powerful number
  • 板块学术版
  • 楼主arfa
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/7/27 07:25
  • 上次更新2023/11/6 22:10:18
查看原帖
求助大佬 , 关于 Powerful number
77760
arfa楼主2020/7/27 07:25

算了一下 n=6n=6 时的 f\sum f , f(pk)=p xor kf(p^k)=p \text{ xor } k
其中 f=hgf=h*g , gg 构造为 ϕ\phi
按照 PN\text{PN} 和杜教筛的逻辑 , 根据 i=1nf(i)=d=1nh(d)i=1ndf(i)\sum\limits^n_{i=1} f(i)=\sum\limits^n_{d=1} h(d)\sum\limits^{\left\lfloor\frac{n}{d}\right\rfloor}_{i=1}f(i) , 得出: i=16f(i)=h(1)(i=16ϕ(i))+h(22)ϕ(1)=i=16ϕ(i)+h(22)\sum\limits^6_{i=1} f(i)=h(1)(\sum\limits^{6}_{i=1} \phi(i))+h(2^2)\phi(1)=\sum\limits^{6}_{i=1} \phi(i)+h(2^2)

其中 i=16ϕ(i)=12\sum\limits^{6}_{i=1} \phi(i)=12
因为有 h(20)=1,h(21)=0,ϕ(20)=ϕ(21)=1,ϕ(22)=2h(2^0)=1 , h(2^1)=0,\phi(2^0)=\phi(2^1)=1,\phi(2^2)=2
又因为 f=hgf=h*g , 所以 h(pk)=f(pk)d=0k1h(pd)g(pkd)h(p^k)=f(p^k)-\sum\limits^{k-1}_{d=0}h(p^d)g(p^{k-d}) , 代入 p=2p=2 , k=2k=2
h(22)=f(22)h(20)ϕ(22)h(21)ϕ(21)=2 xor 220=2h(2^2)=f(2^2)-h(2^0)\phi(2^2)-h(2^1)\phi(2^1)=2 \text{ xor } 2-2-0=-2

而原本期望的 h(22)h(2^2) 应该为 44 。。。。

2020/7/27 07:25
加载中...