回归数：其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数。

回归数的猜想

解答

回归数的猜想

【回归数猜想】

英国大数学家哈代(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

*注： 1^3代表1的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

像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数?

1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.

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

An=a1a2a3...an=a1n+a2n+...+ann (其中 0<=a1,a2,...an<=9)

从而 10n-1<=An<=n9n 即 n 必须满足 n9n>10n-1 也就是 (10/9)n<10n ⑴

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

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

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

由此可知,使⑴式成立的自然数 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 ,能有多少个回归数?最大的回归数是多少?

解答

现在有一C语言题目：要求输入整数m n.(0<m<n<70000000)求出m到n之间所有的回归数。我编了一个，但算法不够科学，以3.8G的赛扬D来跑，算到24678051以后就等很久很久都出不了下一个结果。悬赏求更优的算法。我的代码及运算结果如下。#include<stdio.h>main(){long m,n,i,j,l,s; int a,b,c,d=0; do {printf("\Please Input the m n:(10<m<n<70000000)\"); scanf("%ld %ld",&m,&n); }while(m<=0||n<=0||m>=70000000||n>=70000000||m>=n); printf("\The Answer is:\"); for(i=m;i<n;i++) {j=i;c=0;s=0; while(j>0) {j=j/10;c++;} j=i; while(j>0) {a=j%10;j=j/10;l=1; for(b=0;b<c;b++) l=l*a; s+=l; } if(s==i) {printf("%ld\\t",i); d++; if(d%4==0) printf("\"); } } printf("\Press Any Key to Exit.");getch();