自缚数

无心人

Prelude> let ff6 n m = [(n,nnn)|a<-[1..m],b<-[0..m],c<-[0..m],d<-[0..m],e<-[0..m
],f<-[0..m],let nnn=10^5*a+10^4*b+10^3*c+10^2*d+10*e+f,n^a+n^b+n^c+n^d+n^e+n^f==
nnn]
Prelude> filter (\l -> l /= []) (map (\n -> ff6 n 1) [10000..99999])

无心人

七位
(5, 3909511)
(16, 1053202)
(33, 1224103)
(100, 1010203)
(858, 2210210)
(250027 , 1000111)
(250252 , 1001011)
(252502, 1010011)
(275002, 1100011)
(499998, 1000001)
(999994, 1000000)

无心人

八位
(7, 13177388), (19, 52135640), (1587300, 11111101),
(2502774, 10011100),(2525274, 10101100),
(2527524, 10110100),(2527749, 10111000),
(2750274, 11001100),(2752524, 11010100),
(2752749, 11011000),(2775024, 11100100),
(2775249, 11101000),(2777499, 11110000),
(5000002, 10000010),(5000047, 10000100),
(5000497, 10001000),(5004997, 10010000),
(5049997, 10100000),(5499997, 11000000),
(9999993, 10000000),

无心人

九位

(40, 102531321),(12345679, 111111111),(14301587, 100111111),(14444444, 101111110),(15730157, 110
111101),(15858587, 111010111),(15873014, 111111100),(16668518, 100011111),(16683
518, 100101111),(16685018, 100110111),(16685168, 100111011),(16685183, 100111101
),(16833518, 101001111),(16835018, 101010111),(16835168, 101011011),(16835183, 1
01011101),(16850018, 101100111),(16850168, 101101011),(16850183, 101101101),(168
51668, 101110011),(16851683, 101110101),(16851833, 101111001),(18333518, 1100011
11),(18335018, 110010111),(18335168, 110011011),(18335183, 110011101),(18350018,
110100111),(18350168, 110101011),(18350183, 110101101),(18351668, 110110011),(1
8351683, 110110101),(18351833, 110111001),(18500018, 111000111),(18500168, 11100
1011),(18500183, 111001101),(18501668, 111010011),(18501683, 111010101),(1850183
3, 111011001),(18516668, 111100011),(18516683, 111100101),(18516833, 111101001),
(18518333, 111110001),(25000274, 100001101),(25002524, 100010101),(25002749, 100
011001),(25025024, 100100101),(25025249, 100101001),(25027499, 100110001),(25250
024, 101000101),(25250249, 101001001),(25252499, 101010001),(25274999, 101100001
),(27500024, 110000101),(27500249, 110001001),(27502499, 110010001),(27524999, 1
10100001),(27749999, 111000001),(33333335, 100000011),(33333365, 100000101),(333
33368, 100000110),(33333665, 100001001),(33333668, 100001010),(33333698, 1000011
00),(33336665, 100010001),(33336668, 100010010),(33336698, 100010100),(33336998,
100011000),(33366665, 100100001),(33366668, 100100010),(33366698, 100100100),(3
3366998, 100101000),(33369998, 100110000),(33666665, 101000001),(33666668, 10100
0010),(33666698, 101000100),(33666998, 101001000),(33669998, 101010000),(3369999
8, 101100000),(36666665, 110000001),(36666668, 110000010),(36666698, 110000100),
(36666998, 110001000),(36669998, 110010000),(36699998, 110100000),(36999998, 111
000000),(49999997, 100000001),(99999992, 100000000)

无心人

#include <stdlib.h>
#include <stdio.h>

void resultFind7(int n, int m)
{
  int p[10];
  int i;
  int i1, i2, i3, i4, i5, i6, i7, i8, i9, pp;
  p[0] = 1;
  for (i=1; i <= m; i ++)
    p[i] = p[i-1]*n;

  for (i1 = 1; i1 <= m; i1 ++)
  for (i2 = 0; i2 <= m; i2 ++)
  for (i3 = 0; i3 <= m; i3 ++)
  for (i4 = 0; i4 <= m; i4 ++)
  for (i5 = 0; i5 <= m; i5 ++)
  for (i6 = 0; i6 <= m; i6 ++)
  for (i7 = 0; i7 <= m; i7 ++)
  for (i8 = 0; i8 <= m; i8 ++)
  for (i9 = 0; i9 <= m; i9 ++)
  {
    pp = 100000000*i1 + 10000000*i2 + 1000000*i3 + 100000*i4 + 10000*i5 + 1000*i6 + 100*i7 + 10*i8 + i9;
    if (p[i1] + p[i2] + p[i3] + p[i4] + p[i5] + p[i6] + p[i7] + p[i8] + p[i9] == pp)   
      printf("(%d, %d),", n, pp);
  }  
}

int main(void)
{
  int N1, N2, M, i;
  printf("N1(low): ");
  scanf("%d", &N1);
  printf("N2(hi): ");
  scanf("%d", &N2);
  printf("M: ");
  scanf("%d", &M);
  for (i = N1; i <= N2; i++)
    resultFind7(i, M);
}

无心人

10位以上结果涉及到了64位整数

不好做了
或许有64位机器能在30分钟内解决10位的
32位机器难说

无心人

对于10位以上的
假设最大数字是1， 则可转换成求一个一次方程
同样最大是2，转化成二次方程
最大是3，转化成三次方程
比如16位，最大数字是3的数有4^15*3是很少的

而对最大数字比较大的
可以考虑对数字排序，得到递减序列
对长度为n，最大数字是m的递减序列
其总数量是很少的
然后循环测试是否满足特定的B
假设测试B = 29的，针对序列9875321
可得到29^9 + 29^8 ....，对幂和的结果N各位数字排序，再和9875321比较
如果相等，则找到一个结果(29, N)
此时对16位以下的序列， B < 10000

无心人

比如一个最大数字是1的整数N
1的个数是a个，0的个数是b个
则如果(N - b) / a是整数
则(B = (N - b) / a, N)是一组解

无心人

假如一个最大数字是2的整数N
2的个数是a, 1的个数是b， 0的个数是c
根据1#定义如果有
aB^2 + bB + c = N
即aB^2 + bB + c - N = 0
显然b^2 - 4a(c-N)必须是平方数，且大于等于0
由此可得到结果

medie2005

改一下，约束一下B，只求满足$10^{(k-1)/9}/k^{1/9}<=B<2*10^{(k-1)/9}/k^{1/9}$的B。

[ 本帖最后由 medie2005 于 2008-12-24 12:40 编辑 ]