百科问答小站 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.



  

相关话题

  为什么人人都说数学有用/很重要, 但似乎大多数人(非数学专业)并不会去证明他们用到的数学? 
  内心随便想一个正整数,让别人来猜,猜对的机率是多少? 
  我们在数学中为什么要引入复数? 
  面试题:一个长度为n的数组,其中数组中每个元素的值都不大于n,如何用O(n)的算法判断数组中是否存在重复元素? 
  如何看待软件工程师觉得学习算法没用? 
  计算机视觉(CV)的算法有哪些,具体都有哪些特点? 
  如何从代数和几何的角度分别理解矩阵? 
  这个级数是怎么得到的? 
  为什么中国学生在国际奥林匹克数学竞赛中经常拿金牌,但却没有获得菲尔兹奖呢? 
  为什么国内一流高校的理工科专业的学生大多对民科充满反感和鄙夷? 

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





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