superabundant问题的数学及算法描述

mathe

问题转自 http://topic.csdn.net/u/20080103 ... html?seed=157425768
The abundance of an integer n is the sum of the divisors of n (including n itself), divided
by n. Integer n is k-abundant if its abundance is at least k.

For example, the sum of the divisors of 6 is 6+3+2+1=12, and 12/6=2, so 6 is 2-abundant.
As another example, the sum of the divisors of 120 is

120+60+40+30+24+20+15+12+10+8+6+5+4+3+2+1=360

so 120 is 3-abundant. It happens that 6 is the smallest 2-abundant number and 120 is the smallest
3-abundant number. They happen to be exactly 2- and 3-abundant, respectively, but it is generally
possible that the smallest k-abundant number has abundance greater than k.

The task is to write a program that finds the smallest k-abundant number for k=1,2,..
How high can you go?

附件中是我给的相关数学分析以及算法描述 abundance.zip (64.43 KB, 下载次数: 6)

2008-1-9 15:52 上传

点击文件名下载附件
superabundant

mathe

一个更新版本，修改了一些错误，
并且删除了使用拉格朗日极值法求极值，而是使用琴生不等式
abundance.zip (70.46 KB, 下载次数: 25)

2008-1-9 17:32 上传

点击文件名下载附件
superabundant问题(更新版本)

gxqcn

可以对原贴直接进行编辑，附件也是可以重新上传更新的（必要时提醒网友重新下载即可）。
这个论坛功能够强吧

上传附件时，最好在“描述”栏中写些摘要或说明；
如果附件是图片，则有可能被首页自动调用显示，具体见：关于“首页调用”图片的几点说明

mathe

CSDN中的yaos提出了一个相关的问题，就是如何找出一些abundance是整数的数，当然是越多越好。
http://topic.csdn.net/u/20080204 ... 3-90ce2d8f2c8d.html
这个问题我们可以描述为给定一个整数K,请找出尽量多的大整数使得它的abundance正好是K.
关于这个问题，我有一些想法，觉得使用以后用计算机应该可以将搜索范围裁剪得很小，但是没有真正试验过。

游客，如果您要查看本帖隐藏内容请回复

无心人

很难很难

至今还无法想到如何做
关键是起始方幂无法确定
一旦错误, 就得不到结果
而且2, 3, 5, 7的幂都是基本关联的
大的2 ^ n不会对应小的3 ^ m

估计试探法对高次幂成功概率不会超过1/10

mathe

1/10对于计算机来说是个很大的概率了。
比如计算一个素数的原根，通常就用试探法，而理论上试探成功率下限大概在$1/log(p)$,但是算法已经非常有效了。

winxos

一个更新版本，修改了一些错误，
并且删除了使用拉格朗日极值法求极值，而是使用琴生不等式
15
mathe 发表于 2008-1-9 17:32

下载链接失效了。

zc19860419

同一个问题，就是下载链接失效了，另外就是想请教下mathe
  一个数的重数公式：

p1-p1^(-a1)        pt - pt^(-at)
-----------      *...* --------------           是如推导得出的
  p1-1                 pt - 1

无心人

其实这个问题还有个难点在于要在程序里集成椭圆曲线跟二次筛整数分解算法

当然可以用现成的库