百科问答小站 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的正因子个数d(n)有没有上界公式? 
  如何评价这篇关于「学习数学不需要做题」的文章的观点? 
  今年复活节应该是3月28号,网上怎么都说是4月4号的呢?春分后第一月圆后的第一礼拜天,怎么是4月4号? 
  关于算法导论定理3.1,为什么感觉快速排序的时间复杂度不满足这个定理? 
  整个宇宙是不是都比不上一个葛立恒数? 
  数学建模到底是个啥? 
  实变函数鲁津定理的疑问? 
  用分离变量法来解 PDE 的合理性何在? 
  请各位大神来看一下,我写的这份实数连续性的新证明是否有错漏? 
  为什么中国人数理化学科成绩似乎秒杀外国人,但世界相关的(出名的)顶级的科学家几乎全是外国的? 

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





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