如何更快地生成自恋数字？

Question

"自恋数字"是n位数字,其数字的所有n次方的总和等于数字.

所以,这153是一个自恋的数字,因为1^3 + 5^3 + 3^3 = 153.

现在给定N,找到N个数字长度的所有自恋数字？

我的方法:迭代所有数字做数字的幂和

并检查是否有相同的数字,我计算了权力.

但这还不够好,有没有更快的方法？!

更新: 在自然界中只有88个自恋数字,最大的是39位数字,但我只需要长度为12或更短的数字.

我的代码:

long long int powers[11][12];
// powers[x][y] is x^y. and its already calculated

bool isNarcissistic(long long int x,int n){
    long long int r = x;
    long long int sum = 0;

    for(int i=0; i<n ; ++i){
        sum += powers[x%10][n];
        if(sum > r)
            return false;
        x /= 10;
    }
    return (sum == r);
}

void find(int n,vector<long long int> &vv){
    long long int start = powers[10][n-1];
    long long int end = powers[10][n];

    for(long long int i=start ; i<end ; ++i){
        if(isNarcissistic(i,n))
            vv.push_back(i);
    }
}

Answer 1

由于总共只有88个narcisstic数字,你可以将它们存储在一个查找表中并迭代它:http://mathworld.wolfram.com/NarcissisticNumber.html

Answer 2

从另一端开始.迭代所有非递减d数字序列的集合,计算d-th幂的总和,并检查是否产生(排序后)您开始的序列.

既然有

9×10 ^(d-1)

d-digit数字,但仅限

(10+d-1) `choose` d

非递减的d数字序列,将搜索空间减少一个因子接近d!.

Answer 3

下面的代码实现了@Daniel Fischer的想法。它复制了在Mathworld引用的表，然后打印出几个11位数字，并确认有没有与12位的说明这里。

实际上，生成所有非递增数字字符串的可能直方图而不是字符串本身会更简单，并且可能更快一些。直方图是指索引为0-9的各个数字的频率的表。这些可以直接比较而不进行排序。但是下面的代码运行时间不到1秒，因此我不会实现直方图的想法。

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

#define MAX_DIGITS 12

// pwr[d][n] is d^n
long long pwr[10][MAX_DIGITS + 1];

// Digits and final index of number being considered.
int digits[MAX_DIGITS];
int m;

// Fill pwr.
void fill_tbls(void)
{
  for (int d = 0; d < 10; d++) {
    pwr[d][0] = 1;
    for (int p = 1; p <= MAX_DIGITS; p++) 
      pwr[d][p] = pwr[d][p-1] * d;
  }
}

// qsort comparison for integers descending
int cmp_ints_desc(const void *vpa, const void *vpb)
{
  const int *pa = vpa, *pb = vpb;
  return *pb - *pa;
}

// Test current number and print if narcissistic.
void test(void)
{
  long long sum = 0;
  for (int i = 0; i <= m; i++)
    sum += pwr[digits[i]][m + 1];
  int sum_digits[MAX_DIGITS * 2];
  int n = 0;
  for (long long s = sum; s; s /= 10)
    sum_digits[n++] = s % 10;
  if (n == m + 1) {
    qsort(sum_digits, n, sizeof(int), cmp_ints_desc);
    if (memcmp(sum_digits, digits, n * sizeof(int)) == 0) 
      printf("%lld\n", sum);
  }
}

// Recursive generator of non-increasing digit strings.
// Calls test when a string is complete.
void gen(int i, int min, int max)
{
  if (i > m) 
    test();
  else {
    for (int d = min; d <= max; d++) {
      digits[i] = d;
      gen(i + 1, 0, d); 
    }
  }
}

// Fill tables and generate.
int main(void)
{
  fill_tbls();
  for (m = 0; m < MAX_DIGITS; m++)
    gen(0, 1, 9);
  return 0;
}