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 )