方幂圈问题

无心人

在我一个被水浸湿的笔记上
等我找下
似乎不是很大的一个数字
保证不超过8位数

mathe

嗯，这个数值应该是$C_29^21=4292145$不算大。所以还好

mathe

题目可以采用如下算法:
i)将$x0+x1+...+x9=21$中每个解给出唯一编号（0到4292144）并且采用hash表保存解到编号之间的映射
ii)制作图，图中有4292145个点。
iii)事先计算$0^21,1^21,....,9^21$
iv)对于$x0+x1+...+x9=21$中每个解 (编号为k1)
计算$x0*0^21+x1*1^21+...+x9*9^21$用十进制表示，并且将这个十进制数看成21位数（前面补0），统计0,1,2,...,9的数目分别为y0,y1,...,y9. 假设(y0,y1,...,y9)的编号为k2.在图中作出有向边<k1,k2>.
v)找出图中所有强连通分支。
  那么每个强连通分支都对应一个所求的圈。

无心人

运算量很小

另外我在考虑这个问题
像32次幂有没有可能在小于32位数上产生圈和终结点？

mathe

32次幂后产生的数最多31位，对应方程总共只有273438880个解。
2.7G对于现在计算机来说不算很大的数字，用现在个人计算完全可以解决这个问题。
可以使用一个长度为2.7G的比特位(341.8M)，每个比特位用来标志一个解(x0,x1,...,x9)是否已经被处理，其中
x0+x1+...+x9=31
我们可以事先计算出所有组合数$C_n^k$,其中$n<=40$,利用这个可以方便的转化解到编号或编号到解。

无心人

超过20的会产生9^n << 10^n现象
所以问n = 32的情况

无心人

media2005提到了
回归数
似乎是这个问题的一个说法

来这里讨论吧
先考虑下用笨方法求出10以下的幂的所有环和数？

要用到Hash方法，而且还要设计一个比较好的搜寻法
似乎我在别处有说这个搜寻

无心人

查阅了相关的资料
这个回归数定义比我的定义严格
========================================
回归数


英国大数学家哈代(g.h.hardy,1877-1947)曾经发现过一种有趣的现象:

153=1^3+5^3+3^3

371=3^3+7^3+1^3

370=3^3+7^3+0^3

407=4^3+0^3+7^3

他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:

1634=1^4+6^4+3^4+4^4

54748=5^5+4^5+7^5+4^5+8^5

548834=5^6+4^6+8^6+8^6+3^6+4^6

注:3位3次幂回归数又称位“水仙花数”

像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数? 1986年美国的一位数学教师安东尼.迪拉那(anthony diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.

设 an 是这样的回归数,即:

an=a1a2a3...an=a1^n+a2^n+...+an^n (其中 0<=a1,a2,...an<=9)

从而 10^n-1<=an<=n9^n 即 n 必须满足 n9^n>10^n-1 也就是 (10/9)^n<10n (1)

随着自然数 n 的不断增大,(10/9)^n 值的增加越来越快,很快就会使得(1) 式不成立,因此,满足(1)的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:

(10/9)^60=556.4798...<10*60=600 (10/9)^61=618.3109...>10*61=610

对于 n>=61,便有 (10/9)^n>10n

由此可知,使(1)式成立的自然数 n<=60.故这种回归数最多是60位数.迪拉那说,他的学生们早在1975年借助于[[哥伦比亚大学]]的计算机得到下列回归数:

一位回归数:1,2,3,4,5,6,7,8,9

二位回归数:不存在

三位回归数:153,370,371,407

四位回归数:1634,8208,9474

五位回归数:54748,92727,93084

六位回归数:548834

七位回归数:1741725,4210818,9800817

八位回归数:24678050,24678051

但是此后对于哪一个自然数 n (<=60)还有回归数?对于已经给定的 n ,能有多少个回归数?最大的回归数是多少?

3 153 370 371 407

4 1634 8208 9474

5 54748 92727 93084

6 548834

7 1741725 4210818 9800817 9926315

8 24678050 24678051 88593477

9 146511208 472335975 534494836 912985153

10 4679307774

11 82693916578 44708635679 94204591914 32164049651 42678290603 40028394225 32164049650 49388550606

12 无解

13 无解 0564240140138(只有广义解一组)

14 28116440335967

15 无解

16 4338281769391371 4338281769391370 17 35641594208964132 21897142587612075 35875699062250035 233411150132317(广义解)

18 无解

19 4498128791164624869 4929273885928088826 3289582984443187032 1517841543307505039

20 14543398311484532713 63105425988599693916

21 128468643043731391252 449177399146038697307

22 无解

23 21887696841122916288858 28361281321319229463398、27879694893054074471405 35452590104031691935943 27907865009977052567814

24 188451485447897896036875 239313664430041569350093、174088005938065293023722、

25 1553242162893771850669378 3706907995955475988644381 4422095118095899619457938 3706907995955475988644380 1550475334214501539088894

38 12815792078366059955099770545296129367

39 115132219018763992565095597973971522401 115132219018763992565095597973971522400

无心人

http://www.mathoe.com/dispbbs.as ... ID=10638&page=2

这里有media2005说的全部回归数

无心人

打算做这个题目了
写了个适合8次方以下的程序
做完了生成表
分析代码还没写
powerDigit.c (1.52 KB, 下载次数: 1)

2008-12-26 22:38 上传

点击文件名下载附件