25

“自恋数字”是 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);
    }
}
4

9 回答 9

22

由于总共只有 88 个自恋数字，您可以将它们存储在查找表中并对其进行迭代： http: //mathworld.wolfram.com/NarcissisticNumber.html

于 2013-01-03T14:45:38.150 回答
14

从另一端开始。迭代所有非递减d数字序列的集合，计算d-th 次方的总和，并检查它是否产生（排序后）您开始使用的序列。

既然有

9×10^(d-1)

d- 数字，但仅限于

(10+d-1) `choose` d

非递减数字序列d，将搜索空间减少了接近d!.

于 2013-01-03T14:47:39.673 回答
5

下面的代码实现了@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;
}
于 2013-02-06T06:46:27.143 回答
2

我在 Lua 中编写了一个程序，它在 30829.642 秒内找到了所有自恋数字。该程序的基础是递归数字值计数数组生成器函数，它在为所有数字值生成数字值计数时调用检查函数。每个嵌套循环迭代：

FROM i= 0 和 a+x*d^o+(sx)*(d-1)^o >= 10^(o-1) 的解中的较大者，其中 - 'a' 是到目前为止的数字幂， - 'd' 是当前数字值（0-9 为基数 10）， - 'o' 是总位数（数字值计数数组的总和必须加起来), - 's' 表示在数组添加到 'o' 之前剩余的可用插槽

UP TO i<= 's' 中的较小者以及对于具有相同变量的 x 的 a+x*d^o < 10^o 的解。

这可确保检查的数字始终具有与“o”相同的位数，因此更有可能自恋，同时避免不必要的计算。

在循环中，它执行递归调用，递减数字值 'd' 添加当前数字值的贡献 (a=a+i*d^o) 并从 ' 中取出已用完的 i 个数字槽s'。

我写的要点是：

local function search(o,d,s,a,...) --Original number of digits, digit-value, remaining digits, accumulative sum, number of each digit-value in descending order (such as 5 nines)
    if d>0 then
        local d0,d1=d^o,(d-1)^o
        local dd=d0-d1
        --a+x*d^o+(s-x)*(d-1)^o >= 10^(o-1) , a+x*d^o < 10^o
        for i=max(0,floor((10^(o-1)-s*d1-a)/dd)),min(s,ceil((10^o-a)/dd)-1) do
            search(o,d-1,s-i,a+i*d0,i,...) --The digit counts are passed down as extra arguments.
        end
    else
        --Check, with the count of zeroes set to 's', if the sum 'a' has the same count of each digit-value as the list specifies, and if so, add it to a list of narcissists.
    end
end

local digits=1 --Skip the trivial single digit narcissistic numbers.
while #found<89 do
    digits=digits+1
    search(digits,9,digits,0)
end

编辑：我忘了提到我的程序找到了 89 个自恋数字！这些是它发现的：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21897142587612075, 35641594208964132, 35875699062250035, 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826, 63105425988599693916, 128468643043731391252,449177399146038697307, 21887696841122916288858, 27879694893054074471405, 27907865009977052567814, 28361281321319229463398, 35452590104031691935943, 174088005938065293023722, 188451485447897896036875, 239313664430041569350093, 1550475334214501539088894, 1553242162893771850669378, 3706907995955475988644380, 3706907995955475988644381, 4422095118095899619457938, 121204998563613372405438066, 121270696006801314328439376, 128851796696487777842012787, 174650464499531377631639254, 177265453171792792366489765, 14607640612971980372614873089, 19008174136254279995012734740, 19008174136254279995012734741, 23866716435523975980390369295, 1145037275765491025924292050346, 1927890457142960697580636236639, 2309092682616190307509695338915, 17333509997782249308725103962772, 186709961001538790100634132976990, 186709961001538790100634132976991, 1122763285329372541592822900204593, 12639369517103790328947807201478392, 12679937780272278566303885594196922, 1219167219625434121569735803609966019, 12815792078366059955099770545296129367, 115132219018763992565095597973971522400, 115132219018763992565095597973971522401
于 2013-07-22T23:39:02.980 回答
2

对于后代 ;-) 这与@Krakow10 的方法最相似，递归地生成数字包，从 9 开始，然后是 8，然后是 7 ... 到 0。

它是 Python3 代码，可以在不到 10 分钟的时间内（在我的盒子上）找到所有 1 到 61 位（第一个“显然不可能”的宽度）的 base-10 解决方案。这是迄今为止我听说过的最快的解决这个问题的代码。有什么诀窍？没有技巧 - 只是乏味;-) 随着我们的进行，到目前为止，部分总和产生了对可行延续的限制。该代码只关注那些，因此能够尽早切断大量搜索。

注意：这找不到 0。我不在乎。虽然所有参考文献都说有 88 个解决方案，但他们的表都有 89 个条目。一定是某个急切的编辑后来添加了“0”，然后其他人都盲目地复制了它;-)

编辑通过在搜索早期利用一些部分和约束，新版本的速度是原来的两倍多——现在在我的盒子上完成了 4 分钟多一点。

def nar(width):
    from decimal import Decimal as D
    import decimal
    decimal.getcontext().prec = width + 10
    if width * 9**width < 10**(width - 1):
        raise ValueError("impossible at %d" % width)
    pows = [D(i) ** width for i in range(10)]
    mintotal, maxtotal = D(10)**(width - 1), D(10)**width - 1

    def extend(d, todo, total):
        # assert d > 0
        powd = pows[d]
        d1 = d-1
        powd1 = pows[d1]
        L = total + powd1 * todo # largest possible taking no d's
        dL = powd - powd1  # the change to L when i goes up 1
        for i in range(todo + 1):
            if i:
                total += powd
                todo -= 1
                L += dL
                digitcount[d] += 1
            if total > maxtotal:
                break
            if L < mintotal:
                continue
            if total < mintotal or L > maxtotal:
                yield from extend(d1, todo, total)
                continue
            # assert mintotal <= total <= L <= maxtotal
            t1 = total.as_tuple().digits
            t2 = L.as_tuple().digits
            # assert len(t1) == len(t2) == width
            # Every possible continuation has sum between total and
            # L, and has a full-width sum.  So if total and L have
            # some identical leading digits, a solution must include
            # all such leading digits.  Count them.
            c = [0] * 10
            for a, b in zip(t1, t2):
                if a == b:
                    c[a] += 1
                else:
                    break
            else:  # the tuples are identical
                # assert d == 1 or todo == 0
                # assert total == L
                # This is the only sum we can get - no point to
                # recursing.  It's a solution iff each digit has been
                # picked exactly as many times as it appears in the
                # sum.
                # If todo is 0, we've picked all the digits.
                # Else todo > 0, and d must be 1:  all remaining
                # digits must be 0.
                digitcount[0] += todo
                # assert sum(c) == sum(digitcount) == width
                if digitcount == c:
                    yield total
                digitcount[0] -= todo
                continue
            # The tuples aren't identical, but may have leading digits
            # in common.  If, e.g., "9892" is a common prefix, then to
            # get a solution we must pick at least one 8, at least two
            # 9s, and at least one 2.
            if any(digitcount[j] < c[j] for j in range(d, 10)):
                # we're done picking digits >= d, but don't have
                # enough of them
                continue
            # for digits < d, force as many as we need for the prefix
            newtodo, newtotal = todo, total
            added = []
            for j in range(d):
                need = c[j] - digitcount[j]
                # assert need >= 0
                if need:
                    newtodo -= need
                    added.append((j, need))
            if newtodo < 0:
                continue
            for j, need in added:
                newtotal += pows[j] * need
                digitcount[j] += need
            yield from extend(d1, newtodo, newtotal)
            for j, need in added:
                digitcount[j] -= need
        digitcount[d] -= i

    digitcount = [0] * 10
    yield from extend(9, width, D(0))
    assert all(i == 0 for i in digitcount)

if __name__ == "__main__":
    from datetime import datetime
    start_t = datetime.now()
    width = total = 0
    while True:
        this_t = datetime.now()
        width += 1
        print("\nwidth", width)
        for t in nar(width):
            print("   ", t)
            total += 1
        end_t = datetime.now()
        print(end_t - this_t, end_t - start_t, total)
于 2013-11-09T03:00:16.587 回答
1

我认为这个想法是产生相似的数字。例如， 61 与 16 相似，因为您只是求和

6^n +1^n

所以

6^n+1^n=1^n+6^n

通过这种方式，您可以减少大量的数字。例如在 3 位数字场景中，

121==112==211,

你明白了。您需要先生成这些数字。而且您需要生成这些数字，而无需实际从 0-n 迭代。

于 2013-01-03T15:05:52.093 回答
1

Python版本是：

def generate_power_list(power):
return [i**power for i in range(0,10)]


def find_narcissistic_numbers_naive(min_length, max_length):
for number_length in range(min_length, max_length):

    power_dict = generate_power_dictionary(number_length)

    max_number = 10 ** number_length
    number = 10** (number_length -1)
    while number < max_number:

        value = 0
        for digit in str(number):
            value += power_dict[digit]

        if value == number:
            logging.debug('narcissistic %s ' % number)

        number += 1

递归解决方案：

在此解决方案中，每个递归处理正在使用的数字数组中的单个数字，并尝试该数字的所有适当组合

def execute_recursive(digits, number_length):
index = len(digits)
if digits:
    number = digits[-1]
else:
    number = 0
results = []
digits.append(number)    

if len(digits) < number_length:
    while number < 10:
        results += execute_recursive(digits[:], number_length)
        number += 1
        digits[index] = number

else:
    while number < 10:
        digit_value = sum_digits(digits)
        if check_numbers_match_group(digit_value, digits):
            results.append(digit_value)
            logging.debug(digit_value)

        number += 1
        digits[index] = number

return results


def find_narcissistic_numbers(min_length, max_length):
for number_length in range(min_length, max_length):
    digits = []
    t_start = time.clock()
    results = execute_recursive(digits, number_length)
    print 'duration: %s for number length: %s' %(time.clock() - t_start, number_length)

自恋数字检查 在基础版本中，当检查数字是否与数字匹配时，我们会遍历每个数字类型，以确保每种类型的数字相同。在这个版本中，我们添加了在进行全面检查之前检查数字长度是否正确的优化。

我预计这会对较小的数字长度产生更大的影响，因为随着数字长度的增加，分布中间往往会有更多的数字。结果在一定程度上支持了这一点：

  1. n=16：提高 11.5%
  2. n=19：提高 9.8%
def check_numbers_match_group(number, digits):
number_search = str(number)

# new in v1.3
if len(number_search) != len(digits):
    return False

for digit in digit_list:
    if number_search.count(digit[0]) != digits.count(digit[1]):
        return False

return True
于 2013-02-06T16:06:42.913 回答
0

如果它是自恋数，我认为您可以使用多项式定理对检查进行一些优化。
您可以计算 (a+b+c+..)^n- 非 n 次幂值
的总和，例如对于 n=2 您应该比较 x 和 (a+b)^2-2*a*b 其中 a 和b 是数字 x 的位数

于 2013-01-03T14:55:35.557 回答
-2 
'''We can use Nar() function to calculate the Narcissitic Number.'''

import math
def Nar(num):
   sum=0
   n=len(str(num))
   while n>0:
     temp=num%10
     sum=sum+math.pow(temp,n)
     num=num/10
   return sum
x=input()
y=Nar(x)
if x==y:
  print x,' is a Narcissistic number'
else:
 print x,' is not a Narcissistic number'
于 2016-07-29T16:29:54.377 回答