El Proyecto Euler: Problema 1

18/05/2008

El Proyecto Euler es una serie de problemas de programación, si quieres enterarte de que va esto, lee la introducción.

Problema 1

Si listamos todos los números naturales debajo de 10 que son múltiplos de 3 o 5, tenemos 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Encuentra la suma de todos los múltiplos de 3 o 5 debajo de 1000.

Este problema lo he visto como de los ‘recomendados’ para poner en las entrevistas para trabajo, simple y rápido, te dice claramente las 3 condiciones a evaluar.

El operador % regresa el residuo de una división, por lo que podemos iterar de uno en uno hasta el límite superior (1000) y verificar si cada número es perfectamente divisible (el residuo es 0) entre 3 o 5, entonces lo podemos almacenar.

Resuelto en C.

#include <stdio.h>
 
main()
{
    int sum = 0, i;
    for ( i = 1; i < 1000; i++ )
    {
        if ( (i % 3 == 0) || (i % 5 == 0) ) {
            sum += i;
        }
    }
 
    printf("El resultado es: %d", sum);
}

Conclusión

Comparando con resultados del Proyecto Euler, si bien la solución de fuerza bruta que hice no esta mal, si la pregunta exigiera un limite con cantidades grandes no es eficiente hacer un loop comparando resultado por resultado, sino que es mejor calcular las operaciones por separado.

La suma de números divisibles por 3, la suma de números divisibles por 5 y restando finalmente los números divisibles por 15 que sino tendríamos los divisibles comunes de 3 y 5 contados 2 veces. Se puede evadir por completo cualquier loop si utilizamos progresiones aritméticas.

Para poner un poco en contraste, haciendo benchmark (utilizando gprof) de mi solución para el limite de 1 billón (si si, un uno seguido de 9 ceros), este laptop tarda 15.68 segundos.

En cambio la siguiente versión (versión de sandippal en el foro) que utiliza este principio, tarda menos de .01 segundo, ¿bastante no?.

#include <stdio.h>
#define NUM 999999999
 
main()
{
  unsigned long long mult3  = NUM / 3;
  unsigned long long mult5  = NUM / 5;
  unsigned long long mult15 = NUM / 15;
  unsigned long long sum3, sum5, sum15;
 
  sum3 = 3  * mult3  * (mult3 + 1) / 2;
  sum5 = 5  * mult5  * (mult5 + 1) / 2;
  sum15 = 15 * mult15 * (mult15 + 1) / 2;
 
  printf("resultado: %lld\n", sum3 + sum5 - sum15);
}

Gracias en especial al comentario de Xiam, grande su explicación.

«Anterior | Siguiente»

Hay 16 comentarios:

18/05/2008Michoacano dice:

Se me hace mucho trabajo para este problema. Si me preguntas a mi, yo lo haria con una simple formula… bueno dos xDDD(Pero nadie me pregunto=.

Pero si lo que quieren es iterar, es mas fácil ir sumando de cinco en cinco, y de tres en tres, hasta que se llegue a 1000. Te ahorras mucho CPU.

18/05/2008dmind dice:

#!/usr/bin/env python
suma, i = 0, 1
while i &lt; 1000:
    if((i%3==0) or (i%5==0)):
        suma += i
    i+=1
print suma

yo adoro Python XD

18/05/2008christian dice:

hola estaba viendo planeta linux y me tope con tu proyecto personal se ve interesante y pues que chido que te retes a ti mismo para mejoras, lei la solucion que propones pues como primera rspueta esta bien pero si lo que quieres es mejorar el desempeño de tu programa, recuerda que si puedes evitar las iteraciones en lo mayor posible es mejor
y para este problema si analisas un poco como es funcion (la suma continua de un factor por una sucesion de numeros) pues te daras cuentas de que queda muy reducida y no vas a nesecitar iterar nada y la respuesta pues hasta puede quedar en muy pocas lineas bueno es solo recomendacion yo tambien estoy aprendiendo a ser mas habil con eso de programar y tienes razon solo practicando se puede mejorar nos vemos
18/05/2008xiam dice:
Creo que el problema está mal planteado por que es ambiguo, por ejemplo, con el caso del 15 ya sabemos que es divisible entre 3 o 5, pero tengamos en cuenta que el ‘o lógico’ no es exclusivo, es decir, la suma de múltiplos de 3 o 5 menores de 20 podría ser:

+ 3 + 6 + 9 + 12 + 15 + 18 (los de 3)
+ 5 + 10 + 15 (los de 5)

Donde el 15 estaría siendo sumado dos veces, la suma de dos 15 no alteraría las restricciones del problema ya que el ‘ó’ sigue siendo verdadero y la proposición se sigue cumpliendo.

Suponiendo que ésta solución es válida también se puede resolver de ésta forma:
1 2 3 4 5 6 7 8 9
#include <stdio.h> #define SUM(n) (n*(n+1)/2) #define TOP 1000 int main() { printf("%d\n", 3*SUM((TOP-1)/3) + 5*SUM((TOP-1)/5)); return 0; }
Pero suponiendo la otra parte, es decir, que el ‘ó’ es en realidad un ‘ó’ exclusivo, se requeriría restar al resultado anterior los números que son múltiplos de 3 y 5, pero todos los números que son múltiplos de 3 y 5 son múltiplos de 3*5 = 15, entonces:
1 2 3 4 5 6 7 8 9
#include <stdio.h> #define SUM(n) (n*(n+1)/2) #define TOP 1000 int main() { printf("%d\n", 3*SUM((TOP-1)/3) + 5*SUM((TOP-1)/5) - 15*SUM((TOP-1)/15)); return 0; }
Y ese montón de cosas raras las baso en la siguiente demostración nerdosa:

A y B números naturales.

Se requiere la suma de todos los múltiplos de A menores a B.

El mayor número natural menor que B es C = B – 1, entonces, los múltiplos de A pueden ser menores o iguales a C sin alterar el resultado, es decir

A <= C < B

Según el problema, la suma que buscamos se puede escribir como:

A*1 + A*2 + A*3 + … + A*D

Donde D es el número de los múltiplos de A menor o iguales a C, es decir, la parte entera de C / A, D = [[C/A]], donde [[]] es la función mayor entero (básicamente un floor())

A*1 + A*2 + A*3 + … + A*D = A(1 + 2 + 3 + … + D)

Pero sabemos que (1 + 2 + … + n) = n(n+1)/2, entonces

A*1 + A*2 + A*3 + … + A*D = A(1 + 2 + 3 + … + D) = A(D(D+1)/2).

La suma que estamos buscando es equivalente a

A(D(D+1)/2)

En el problema simplemente cambiamos las variables por las constantes apropiadas, y como en C, el número 5.8 necesariamente se trunca a 5 para seguir siendo int, no nos hace falta implementar una función [[]].
18/05/2008xiam dice:

Bien, el #include debería ser a stdio.h pero wordpress me lo borró.
19/05/2008Michoacano dice:

A eso me refería cuando dije que en una formula, pero creo que si esto fuera un concurso no aceptarían esa forma.
19/05/2008Yeru dice:

@_@ No sabia de este proyecto Euler… La verdad que no, se ve bien interesante.. seguire viendo los problemas que publiques, notese que dije viendo y no resolviendo jajaja… Saludos.
*a Yeru le da flojera programar asuntos matematicos por mas simple que sean…

A ver a ver.. Cual es el otro problema que resolveras? Este estaba un poco facil… :)
21/05/2008Jesús dice:

mira tú, que interesante, me pondré a resolverlos… pero este ya no vale porque ya lo resolviste así que mejor lo copypasteo ñ_ñ
21/05/2008pablasso dice:

@Michoacano Tienes mucha razón, se itera mucho menos haciéndolo por partes y en rangos grandes si que valdrá la pena. A la próxima no te guardes la formula, en los concursos todo se vale mientras llegues al resultado ;-)

@dmind Gracias! siempre es interesante verlo en otros lenguajes

@xiam Me gusto mucho tu forma de resolver el problema y mucho mas tu forma de explicarlo, gracias por tomarte el tiempo

@Yeru Fáciles y difíciles, ahí vamos de uno en uno :-)

@Jesús .. Webón ¬¬
21/05/2008RalPh dice:

jajaja, acaso apenas vas empesando con C++?
Eso es de rutina prima semanal
21/05/2008pablasso dice:

Es C no C++.

No hay necesidad de ponerse como anónimo, precisamente esa es una de las motivaciones, desde clases en el TSU (unos 6 años) que no toco C y ese es uno de los propósitos, que se me quite lo wey. No me ofendo shinga :-)
13/06/2008Geranio Bigotes dice:
Otra respuesta al problema en python, usando comprensión de listas, espero que les resulte interesante tb.
```
sum([n for n in range(1,1000) if n % 3 == 0 or n % 5 == 0])
```
Eso es todo :P, bien cortito… Saludos!
15/06/2008pablasso dice:

Gracias Geranio!
19/02/2009Victor Braco dice:

Si bien creo que las progresiones aritmeticas esas son geniales, para varias un poco las “formas” de calcularlo, aca tengo otra:
http://www.vbracco.com.ar/archivo/2009/02/19/proyecto-euler-problema-1/
30/06/2009ramiro dice:

mandenme los resultados que les salio de los problemas 11,21,34
por favor quiero comprovar mis resultados..

16/05/2010fitorec dice:

Bueno creo que este problema ya quedo solucionado, una forma de mejorar la solución tal ves sea replanteando lo que se tiene:

Problema principal es:

Encuentra la suma de todos los múltiplos de 3 o 5 debajo de 1000.

Observaciones la solución de Xiam: q por cierto se me hace muy buena, pues el tiempo de ejecución(Cota superior/inferior) es costante.

Sea X la suma de los elementos múltiplos de A en un rango de N entonces esto es:

X = (A+2A+..+N) = A(1+2+…+N/A)
Donde (1+2+…+N/A) Se puede ver como la sucesión 1+2+3+..n = n(n+1)/2 esto es:

1+2+…+N/A = N/A* (N/A + 1) /2 por lo tanto:

X = A(N/A* (N/A + 1) /2 ) = N (N/A + 1) /2

Dado el enunciado nos conviene hacer N=999 entonces para el caso de la suma de los elementos de 3 (A=3) son:
N (N/A + 1) /2
Si hacemos B=5 entonces la suma de los elementos de la susesion (5+10+…+995) es.
N ([[N/B]] + 1) /2

Donde como bien lo dice Xiam [[]] debería ser la parte entere de la razón N/B.
Entonces la solución al problema planteado seria:
N ([[N/A]] + 1) /2 + N ([[N/B]] + 1) /2 = N/2 * ([[N/A]] + [[N/B]] + 2)

Respecto al ‘o’ es excluyente, esto es:
La suma de los elementos 3 o 5 en el rango de [1-999] menos los elementos repetidos(sus multiplos) esto es si hacemos C=15:

N/2 * ([[N/A]] + [[N/B]] + 2) – N ([[N/C]] + 1) /2 = N/2 * ([[N/A]] + [[N/B]] – [[N/C]] +1)

La otra solución la basada en iteraciones la observación del Michoacano es acertada en el hecho que si se realiza la suma de 3 en 3 y de 5 en 5, se reducen las iteraciones.

Si analizamos un intervalo menor a 20.
En el caso en el cual la ‘o’ no es excluyente la para la suma de los valores serian:
3 + 6 + 9 + 12 + 15 + 18 (los de 3) + 5 + 10 + 15 (los de 5) = 93
Para el otro caso en donde la o es excluyente esto seria:
3 + 6 + 9 + 12 + 15 + 18 (los de 3) + 5 + 10 (los de 5 dnd excluimos el 15) = 78

Entonces la cuestión se reduce a sumar los múltiplos de 3 y 5 en el intervalo deseado y posteriormente restarlo los elementos que son múltiplos de ambos esto en C seria:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include 
#define TOP 1000
int main(void){
        int i,j,k,suma = 0;
        //la suma de los elementos multiplos de 3
        for(i=0; i<TOP; i+=3)
                suma +=i;
        //la suma de los elementos multiplos de 5
        for(j=0; j<TOP; j+=5)
                suma +=j;
        //la resta de los elementos multiplos de 3 y 5
        for(k=0; k<TOP; k+=15)
                suma -=k;
        printf("%d\n",suma);
        return 0;
}
Esta implementación al comparar el rendimiento con el programa ‘time’ mostro un cambio significativo, sin embargo el tiempo de ejecución esta en función de la constante TOP a diferencia de la solución basada en las sucesiones de Xiam.

Respecto al ‘o’ exclusivo bastara con eliminar las lineas 12,13,14 para incluir los múltiplos de 3, 5 lo cual tmb reduce el tiempo de ejecución del programa resultante.
1
2
3
        //la resta de los elementos multiplos de 3 y 5
        for(k=0; k<TOP; k+=15)
                suma -=k;

Escribe tu comentario:

Los mas frikis pueden suscribirse a los comentarios por RSS.