在我一个被水浸湿的笔记上
等我找下
似乎不是很大的一个数字
保证不超过8位数
嗯，这个数值应该是$C_29^21=4292145$不算大。所以还好
题目可以采用如下算法:
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位数上产生圈和终结点？
32次幂后产生的数最多31位，对应方程总共只有273438880个解。
2.7G对于现在计算机来说不算很大的数字，用现在个人计算完全可以解决这个问题。
可以使用一个长度为2.7G的比特位(341.8M)，每个比特位用来标志一个解(x0,x1,...,x9)是否已经被处理，其中
x0+x1+...+x9=31
我们可以事先计算出所有组合数$C_n^k$,其中$n<=40$,利用这个可以方便的转化解到编号或编号到解。
;P
超过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.asp?boardID=14&ID=10638&page=2
这里有media2005说的全部回归数
打算做这个题目了
写了个适合8次方以下的程序
做完了生成表
分析代码还没写