Как быстрее генерировать нарциссические числа?

Ответ 1

В приведенном ниже коде реализована идея @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;
}

Ответ 2

Поскольку всего всего 88 нарцистических чисел, вы можете просто сохранить их в таблице поиска и перебрать по ней: http://mathworld.wolfram.com/NarcissisticNumber.html

Ответ 3

Начните с другого конца. Итерации по множеству всех неубывающих последовательностей цифр d, вычислите сумму d -th powers и проверьте, производит ли (после сортировки) последовательность, с которой вы начали.

Так как существуют

9 × 10 ^ (д-1)

d -digit numbers, но только

(10+d-1) `choose` d

неубывающие последовательности цифр d, что уменьшает пространство поиска на коэффициент, близкий к d!.

Ответ 4

Я написал программу в Lua, которая обнаружила все нарциссические числа за 30829,642 секунды. Основой программы является рекурсивная функция генератора счетчиков цифровых значений, которая вызывает функцию проверки, когда она генерирует счетчик цифр для всех значений цифр. Каждый вложенный цикл выполняет итерацию:

FROM я = Чем больше 0 и решение a + x * d ^ o + (s-x) * (d-1) ^ o >= 10 ^ (o-1) для x где  - "a" - это сумма накопленных сумм цифр до сих пор,  - 'd' - текущее значение разряда (0-9 для базы 10),  - 'o' - общее количество цифр (сумма суммы массива счетчиков цифр должна складываться),  - 's' представляет оставшиеся слоты, доступные до тех пор, пока массив не добавит 'o'

UP TO я < = Меньшее из 's' и решение a + x * d ^ o < 10 ^ o для x с одинаковыми переменными.

Это гарантирует, что проверенные числа будут ВСЕГДА иметь такое же количество цифр, что и "o", и поэтому с большей вероятностью будут нарциссическими, избегая ненужных вычислений.

В цикле он рекурсивный вызов, для которого он уменьшает значение цифры 'd', добавляет текущий вклад в цифровую величину (a = a + я * 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

EDIT: Я забыл упомянуть, что моя программа набирает 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

Ответ 5

Для потомков;-) Это наиболее похоже на подход @Krakow10, рекурсивно генерирующий мешки цифр, начиная с 9, затем 8, затем от 7... до 0.

Это код Python3 и находит все решения base-10 с 1 по 61 цифрой (первая "явно невозможная" ширина) менее чем за 10 минут (на моем ящике). Это самый быстрый код, который я когда-либо слышал об этой проблеме. Какой трюк? Никакой трюк - просто скука;-) Как мы идем, частичная сумма до сих пор дает мир ограничений на возможные продолжения. Код просто обращает на них внимание, и поэтому он может сократить ранние поисковые запросы.

Примечание: это не находит 0. Мне все равно. Хотя все ссылки говорят, что существует 88 решений, их таблицы имеют 89 записей. Некоторый нетерпеливый редактор должен добавить "0" позже, а затем все остальные бездумно скопировали его; -)

EDIT Новая версия работает в два раза быстрее, используя некоторые ограничения частичной суммы ранее в поиске - теперь заканчивается чуть более 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 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)

Ответ 6

Я думаю, что идея состоит в том, чтобы генерировать подобные числа. Например, 61 похож на 16, поскольку вы просто суммируете

6 ^ n + 1 ^ n

так

6 ^ п + 1 ^ п = 1 ^ п + 6 ^ п

Таким образом, вы можете уменьшить значительное количество чисел. Например, в сценарии с тремя цифрами,

121 == 112 == 211,

вы поняли суть. Сначала вам нужно сгенерировать эти числа. И вам нужно сгенерировать эти числа без фактического повторения с 0-n.

Ответ 7

Версия 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)

Проверка нарциссического числа В базовой версии при проверке того, что число соответствует цифрам, мы повторяем каждый тип цифр, чтобы обеспечить одинаковое количество каждого типа. В этой версии мы добавили, что оптимизация проверки длины цифры правильная, прежде чем выполнять полную проверку.

Я ожидал, что это повлияет на длину небольшого числа, поскольку по мере увеличения длины номера в середине распределения будет больше чисел. Это было несколько подтверждено результатами:

• n = 16: 11.5% улучшение
• 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

Ответ 8

Я думаю, вы могли бы использовать многочленную теорему для некоторой оптимизации cheacking, если это нарциссическое число.
вы можете вычислить (a + b + c +..) ^ n-сумму значений не n-й степени
например, для n = 2 вам следует сравнить x и (a + b) ^ 2-2 * a * b, где a и b - цифры числа x

Ответ 9

'''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'