algorithm - numeros - Suma de todos los números escritos con dígitos particulares en un rango dado

numeros en letras del 200 al 300

Question

Mi objetivo es encontrar la suma de todos los números del 4 al 666554 que consta de solo 4,5,6.

SUM = 4+5+6+44+45+46+54+55+56+64+65+66+.....................+666554.

El método simple es ejecutar un bucle y sumar los números compuestos de 4,5 y 6 solamente.

long long sum = 0;
for(int i=4;i <=666554;i++){
   /*check if number contains only 4,5 and 6.
     if condition is true then add the number to the sum*/
}

Pero parece ser ineficiente. Comprobar que el número se compone de 4,5 y 6 llevará tiempo. ¿Hay alguna manera de aumentar la eficiencia. He intentado mucho pero no he encontrado un nuevo enfoque. Por favor, ayuda.

Answer 1

"Comience con un problema más simple". —Polya

Suma los números de n dígitos que consisten en los dígitos 4,5,6 solamente

Como Yu Hao explica anteriormente, hay 3**n números y su promedio por simetría es, por ejemplo. 555555, por lo que la suma es 3**n * (10**n-1)*5/9 5/9. Pero si no lo viste, aquí es cómo puedes resolver el problema de otra manera.

El problema tiene una construcción recursiva, así que probemos una solución recursiva. Sea g (n) la suma de todos los 456 números de exactamente n dígitos. Entonces tenemos la relación de recurrencia :

g(n) = (4+5+6)*10**(n-1)*3**(n-1) + 3*g(n-1)

Para ver esto, separe el primer dígito de cada número en la suma (por ejemplo, para n = 3, la columna de cientos). Eso da el primer término. El segundo término es la suma de los dígitos restantes, una cuenta de g (n-1) para cada prefijo de 4,5,6.

Si aún no está claro, escriba la suma n = 2 y separe las decenas de unidades:

g(2) = 44+45+46 + 54+55+56 + 64+65+66
     = (40+50+60)*3 + 3*(4+5+6)
     = (4+5+6)*10*3 + 3*g(n-1)

Guay. En este punto, al lector entusiasta le gustaría comprobar que la fórmula de Yu Hao para g (n) satisface nuestra relación de recurrencia.

Para resolver el problema de OP, la suma de los 456 números del 4 al 666666 es g(1) + g(2) + g(3) + g(4) + g(5) + g(6) . En Python, con programación dinámica:

def sum456(n):
    """Find the sum of all numbers at most n digits which consist of 4,5,6 only"""
    g = [0] * (n+1)
    for i in range(1,n+1):
        g[i] = 15*10**(i-1)*3**(i-1) + 3*g[i-1]
    print(g) # show the array of partial solutions
    return sum(g)

Para n = 6

>>> sum456(6)
[0, 15, 495, 14985, 449955, 13499865, 404999595]
418964910

Edición: observo que OP truncó su suma en 666554 por lo que no se ajusta al patrón general. Serán menos los últimos términos.

>>> sum456(6) - (666555 + 666556 + 666564 + 666565 + 666566 + 666644 + 666645 + 666646 + 666654 + 666655 + 666656 + + 666664 + 666665 + 666666)
409632209

Answer 2

Implemente un contador en la base 3 (número de valores de dígitos), por ejemplo, 0,1,2,10,11,12,20,21,22,100 .... y luego traduzca el número de base-3 a un decimal con los dígitos 4 , 5,6 (0-> 4, 1-> 5, 2-> 6), y sumar al total acumulado. Repetir hasta el límite.

def compute_sum(digits, max_val):

  def _next_val(cur_val):
    for pos in range(len(cur_val)):
      cur_val[pos]+=1
      if cur_val[pos]<len(digits):
        return
      cur_val[pos]=0
    cur_val.append(0)

  def _get_val(cur_val):
    digit_val=1
    num_val=0
    for x in cur_val:
      num_val+=digits[x]*digit_val
      digit_val*=10
    return num_val

  cur_val=[]
  sum=0
  while(True):
    _next_val(cur_val)
    num_val=_get_val(cur_val)
    if num_val>max_val:
      break
    sum+=num_val
  return sum

def main():
  digits=[4,5,6]
  max_val=666554
  print(digits, max_val)
  print(compute_sum(digits, max_val))

Answer 3

La suma de 4 a 666666 es:

total = sum([15*(3**i)*int(''1''*(i+1)) for i in range(6)])
>>> 418964910

La suma de los pocos números entre 666554 y 666666 es:

rest = 666555+666556+666564+666565+666566+
666644+666645+666646+
666654+666655+666656+
666664+666665+666666
>>> 9332701

total - rest
>>> 409632209

Answer 4

Las matemáticas son buenas, pero no todos los problemas son trivialmente "compresibles", por lo que vale la pena saber cómo tratarlos sin matemáticas.

En este problema, la suma es trivial, la dificultad es enumerar de manera eficiente los números que se deben agregar, a primera vista.

La ruta del "filtro" es una posibilidad: generar todos los números posibles, incrementalmente, y filtrar aquellos que no coinciden; Sin embargo, también es bastante ineficiente (en general):

• la condición puede no ser trivial para coincidir: en este caso, la forma más fácil es una conversión a cadena (bastante pesada en divisiones y pruebas) seguida de la coincidencia de cadena
• la proporción de filtrado no es tan mala como para comenzar con un 30% por dígito, pero se escala muy mal como lo comentaron los : para un número de 4 dígitos es de 1%, o generar y verificar 100 números para obtener solo 1 out de ellos.

Por lo tanto, recomendaría un enfoque "generacional": solo genera números que coincidan con la condición (y todos ellos).

Me gustaría señalar que generar todos los números compuestos de 4, 5 y 6 es como contar (en ternario):

• comienza desde el 4
• 45 se convierte en 46 (cuidado con los remanentes)
• 66 se convierte en 444 (arrastre extremo)

Vamos, en Python, como generador:

def generator():
    def convert(array):
        i = 0
        for e in array:
            i *= 10
            i += e
        return i

    def increment(array):
        result = []
        carry = True

        for e in array[::-1]:
            if carry:
                e += 1
                carry = False
            if e > 6:
                e = 4
                carry = True
            result = [e,] + result

        if carry:
            result = [4,] + result

        return result

    array = [4]
    while True:
        num = convert(array)
        if num > 666554: break

        yield num
        array = increment(array)

Su resultado se puede imprimir con sum(generator()) :

$ time python example.py
409632209
python example.py  0.03s user 0.00s system 82% cpu 0.043 total

Y aquí es lo mismo en C ++ .

Answer 5

Para números de 1 dígito, tenga en cuenta que

4 + 5 + 6 == 5 * 3

Para números de 2 dígitos:

(44 + 45 + 46) + (54 + 55 + 56) + (64 + 65 + 66)
== 45 * 3 + 55 * 3 + 65 * 3
== 55 * 9

y así.

En general, para los números de n dígitos, hay 3 ⁿ de ellos consisten en 4 , 5 , 6 solamente, su valor promedio es exactamente 5...5 ( n dígitos). Usando el código, la suma de ellos es (''5'' * n).to_i * 3 ** n (Ruby), o int(''5'' * n) * 3 ** n (Python).

666555 números de hasta 6 dígitos y luego restas la suma de 666555 a 666666 .

PD: para números pequeños como 666554 , usar la coincidencia de patrones es lo suficientemente rápido. ( example )