c++ - cubos - numeros narcisistas

¿Cómo generar números narcisistas más rápido?

Question

Los "números narcisistas" son números de n dígitos donde la suma de todas las potencias n. ° de sus dígitos es igual al número.

Entonces, 153 es un número narcisista porque 1^3 + 5^3 + 3^3 = 153 .

¿Ahora dado N, encuentra todos los números narcisistas que tienen la longitud de N dígitos?

Mi enfoque: era iterar sobre todos los números haciendo sumas de potencias de dígitos

y verifique si es el mismo número o no, y yo calculé las potencias.

pero eso no es lo suficientemente bueno, entonces, ¿hay alguna manera más rápida?

Actualización: En la naturaleza solo hay 88 números narcisistas, y el más grande tiene 39 dígitos, pero solo necesito números con una longitud de 12 o menos.

Mi código :

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

Comenzar desde el otro extremo. Iterar sobre el conjunto de todas las secuencias no decrecientes de d dígitos, calcular la suma de las d -th potencias y verificar si eso produce (después de ordenar) la secuencia con la que comenzó.

Puesto que hay

9 × 10 ^ (d-1)

d -digit numeros, pero solo

(10+d-1) `choose` d

Secuencias no decrecientes de d dígitos, que reducen el espacio de búsqueda en un factor cercano a d! .

Answer 2

Como solo hay 88 números narcisicos en total, puede almacenarlos en una tabla de consulta e iterar sobre ellos: http://mathworld.wolfram.com/NarcissisticNumber.html

Answer 3

Creo que la idea es generar números similares. Por ejemplo, 61 es similar a 16 ya que solo estás sumando

6 ^ n + 1 ^ n

asi que

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

De esta manera puede reducir una cantidad significativa de números. Por ejemplo, en el escenario de 3 dígitos,

121 == 112 == 211,

tú entiendes. Necesitas generar esos números primero. Y necesitas generar esos números sin iterar realmente de 0-n.

Answer 4

Creo que podrías usar el teorema de Multinomial para alguna optimización de descontado si es un número narcisista.
puede calcular (a + b + c + ..) ^ n- suma de valores de potencias no n-th
por ejemplo para n = 2 debes comparar x y (a + b) ^ 2-2 * a * b donde a y b son dígitos del número x

Answer 5

El siguiente código implementa la idea de @Daniel Fischer. Duplica la tabla a la que se hace referencia en Mathworld y luego imprime algunos números más de 11 dígitos y verifica que no haya ninguno con 12 dígitos como se indica here .

En realidad, sería más simple y probablemente un poco más rápido generar todos los histogramas posibles de cadenas de dígitos no crecientes en lugar de las cadenas en sí. Por un histograma me refiero a una tabla indexada 0-9 de frecuencias del dígito respectivo. Estos se pueden comparar directamente sin clasificar. Pero el siguiente código se ejecuta en <1 seg, así que no voy a implementar la idea del histograma.

#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;
}

Answer 6

Escribí un programa en Lua que encontró todos los números narcisistas en 30829.642 segundos. La base del programa es una función de generador de matriz de recuento de valores de dígitos recursivos que llama a una función de verificación cuando se genera el conteo de valores de dígitos para todos los valores de dígitos. Cada bucle anidado itera:

FROM i = El mayor de 0 y la solución a a + x * d ^ o + (sx) * (d-1) ^ o> = 10 ^ (o-1) para x donde - ''a'' es la suma acumulativa de potencias de dígitos hasta ahora, - ''d'' es el valor de dígitos actual (0-9 para la base 10), - ''o'' es el número total de dígitos (que la suma de la matriz de conteo de valores de dígitos debe sumar hasta ), - ''s'' representa las ranuras restantes disponibles hasta que la matriz se agregue a ''o''

HASTA i <= El menor de ''s'' y la solución para a + x * d ^ o <10 ^ o para x con las mismas variables.

Esto asegura que los números verificados SIEMPRE tengan el mismo número de dígitos que ''o'', y por lo tanto es más probable que sean narcisistas y eviten cálculos innecesarios.

En el bucle, realiza la llamada recursiva por la cual disminuye el valor del dígito ''d'' agrega la contribución del valor del dígito actual (a = a + i * d ^ o) y quita las i ranuras de dígitos utilizadas '' s ''.

La esencia de lo que escribí es:

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: ¡Olvidé mencionar que mi programa encuentra 89 números narcisistas! Estos son los que encuentra:

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

Answer 7

Para la posteridad ;-) Esto es más similar al enfoque de @Krakow10, generando bolsas de dígitos de forma recursiva, comenzando con 9, luego 8, luego 7 ... hasta 0.

Es el código Python3 y encuentra todas las soluciones de base 10 con 1 a 61 dígitos (el primer ancho "obviamente imposible") en menos de 10 minutos (en mi caja). Es, con mucho, el código más rápido que he escuchado para este problema. ¿Cuál es el truco? No hay truco, solo tedio ;-) A medida que avanzamos, la suma parcial hasta el momento produce un mundo de restricciones sobre continuaciones factibles. El código solo les presta atención y, por lo tanto, puede eliminar grandes cantidades de búsquedas desde el principio.

Nota: esto no encuentra 0. No me importa. Si bien todas las referencias dicen que hay 88 soluciones, todas sus tablas tienen 89 entradas. Algún editor entusiasta debe haber agregado "0" más tarde, y luego todos los demás lo copiaron sin pensar ;-)

EDITAR La nueva versión es dos veces más rápida, al explotar algunas restricciones de suma parcial al principio de la búsqueda, ahora termina en un poco más de 4 minutos en mi caja.

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)

Answer 8

La versión de Python es:

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

Solución recursiva:

En esta solución, cada recursión maneja un solo dígito de la matriz de dígitos que se está utilizando e intenta todas las combinaciones apropiadas de ese dígito.

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)

Verificación de números narcisistas En la versión base, al verificar que un número coincidía con los dígitos, iteramos a través de cada tipo de dígito, para asegurarnos de que había el mismo número de cada tipo. En esta versión, hemos agregado la optimización de la verificación de que la longitud de los dígitos es correcta antes de realizar la verificación completa.

Esperaba que esto tuviera más efecto en las longitudes de números pequeños, porque a medida que aumenta la longitud de los números, tenderá a haber más números en la mitad de la distribución. Esto fue algo confirmado por los resultados:

1. n = 16: 11.5% de mejora
2. n = 19: 9.8% de mejora

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

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