百科问答小站 logo
百科问答小站 font logo



如何证明一个数 n 的因子之和是 O(n) 的? 第1页

  

user avatar   travorlzh 网友的相关建议: 
      

第一步:渐近上界

根据题主定义,有 ,因此f是积性函数,所以我们只需要通过考虑n为素数幂的情况来得到更具体的计算公式。当p为素数 时

于是根据算术基本定理,我们得到:

现在进行放缩,得:

其中M满足 ,在确定M前我们可以考虑先代入Mertens公式:

[1]

第二步:确定M[2]

设 满足当 表示第j个素数时 ,则 且:

对两侧同时除以 ,得:

现在利用素数定理,我们得知以下两个结论:

其中第二个式子意味着 ,所以根据夹逼定理我们得知 。而根据 的定义,我们可以设 ,回代至(2)我们就得到了:

而(4)意味着以下不等式成立:

第三步:(5)的取等条件

虽然(5)意味着 但这不足以说明 。此时设 则根据(1),有:

其中最后一个等号利用了zeta函数的欧拉乘积和Mertens公式。再根据 和(3),我们有:

对两侧同时取对数,便有:

最后利用 我们就发现 是(5)的取等条件。综上所述我们得到了因子和的渐近上确界(Gronwall定理)

这预示着题主的猜想是错误的,因子和的阶不是O(n)而是O(nloglogn)。

参考

  1. ^当数论遇上分析(6)——Mertens定理与素数定理 - 知乎 https://zhuanlan.zhihu.com/p/338578631
  2. ^ Gronwall, T. H. (1913). Some asymptotic expressions in the theory of numbers. Transactions of the American Mathematical Society, 14(1), 113–122.



  

相关话题

  数学大牛是怎么看待悖论和无穷的? 
  100 万和 50% 的机会拿到 1 亿,你会选哪个? 
  如果让你来编排义务教育阶段至高中的数学课本,你会怎么编排? 
  做学术需要搞清楚高级计量经济学里全部的数学原理吗? 
  如何看待网传字节跳动 28 岁图像算法工程师心梗猝死?还有 30 年房贷没还完,可以退房退款吗? 
  如何比较这两个数的大小? 
  为什么有很多学者认为以往至今的数学理念、数学方法、数学语言不足以描述复杂系统? 
  对任意无理数,都存在有理数列趋近于这个无理数,为什么,怎么找这个有理数列? 
  有哪些令人为之惊叹的数学题目? 
  阅读丘成桐自传《我的几何人生》有什么感悟? 

前一个讨论
如何证明Osgood定理?
下一个讨论
以后会不会出现抗日神剧披着二次元的皮借壳上市的情况?





© 2025-04-26 - tinynew.org. All Rights Reserved.
© 2025-04-26 - tinynew.org. 保留所有权利