GilgaLab

Project Euler – Problema 1

Ao perguntar a um amigo no IRC sobre uma recomendação de hobby, ele me respondeu 'Matemática!'. Eu tinha em mente um hobby onde não precisasse pensar muito, mas matemática já havia me passado pela mente diversas vezes.
Acabei por arranjar um hobby onde não é preciso pensar muito e resolvi também adicionar a matemática como um hobby. Esse post é para falar sobre este último :)
Faz algum tempo fui apresentado ao 'Project Euler', um site com desafios matemáticos que podem ser resolvidos com ou sem o auxílio de um computador. Decidi que vou tentar resolver os problemas, inicialmente sem o auxílio de um computador (quando possível), e então implementarei uma solução utilizando programação.

O Problema

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Em português:

Se nós listarmos todos os números naturais abaixo de 10 que sejam múltiplos de 3 ou 5, teremos 3, 5, 6 e 9. A soma desses múltiplos é 23.
Encontre a soma de todos os multiplos de 3 ou 5 abaixo de 1000.

A Solução Matemática

A primeira idéia para resolver esse problema é dar uma olhada em parte dos conjuntos formados pelos números menores que 1000 e múltiplos de 3 e de 5

M3 terá um total de 333 elementos (999 / 3)
M5 terá um total de 199 elementos (999 / 5)

Algo para se notar é que em ambos os conjuntos existem números repetidos, como por exemplo {15, 30, 45, 60, ...}, logo se realizarmos a soma dos dois conjuntos teremos duplicidade desses números nos dando a resposta incorreta.
Para eliminar esses números de um dos dois conjuntos, precisamos simplesmente subtrair a soma de todos eles do resultado final e para isso precisamos descobrir quais são todos os números múltiplos de 3 E 5 e aplicar o mesmo procedimento de somatória.
Como descobrir esses números então? Simples! Calcula-se o M.M.C. (mínimo múltiplo comum) de 3 e 5, e encontra-se o conjunto dos múltiplos desse valor encontrado para todos os valores abaixo de 1000.

Temos então o novo conjunto M15:



M15 terá um total de 66 elementos (999 / 15)

M15 então é um subconjunto de M3 e também um subconjunto de M5. (Pode-se dizer que M15 está contido em M3 e em M5).

O problema propõe a soma de todos os números múltiplos de 3 OU 5, então precisamos remover o subconjunto M15 de um dos dois conjuntos (M3 ou M5).
Por quê?

Imagine que o problema pedisse a soma de todos os múltiplos de 3 ou 5 abaixo de 20. Teriamos os seguintes conjuntos:

Se realizarmos a somatória de todos os elementos de M3 e M5 a resposta estará incorreta, pois o valor 15 foi somado duas vezes a resposta final, uma vez na somatória dos elementos de M3 e uma vez na somatória de M5.
A solução então é somar M3 a M5 e subtrair M15, fazendo com que o subconjunto M15 seja removido de um dos dois conjuntos.
Então a equação para resolução do problema é:



Não é muito prático realizarmos essa soma na mão, já que ela é composta de muitos números. Olhando bem para as fórmulas, podemos descrever os conjuntos da seguinte maneira:

• O conjunto M3 é a somatória dos primeiros 333 números múltiplos de 3.
• O conjunto M5 é a somatória dos primeiros 199 números múltiplos de 5.
• O conjunto M15 é a somatória dos primeiros 66 números múltiplos de 15.

Em termos matemáticos:







Se expandirmos a primeira equação, teremos algo como:



Todos os elementos estão sendo multiplicados por 3, logo, pode-se colocar o 3 em evidência e teremos:



Que pode ser representado por:

Esse é um resultado bastante interessante pois foi postulado por Gauss (e várias demonstrações do porque podem ser encontradas aqui) que a somatória dos n primeiros números pode ser escrita da seguinte maneira:



Logo, temos a seguinte equação:



Que pode ser escrita da seguinte maneira:

Isso resulta em: 233168

E está ai então a resolução matemática.

A solução com programação

Solução onde não se usam os conceitos matemáticos apresentados acima:

 
#include <stdio.h>
 
int main(int argc, char **argv)
{
    int i;
    int resultado = 0;
    for(i = 1; i < 1000; i++)
    {
        if((i%3 == 0) || (i%5 == 0))
            resultado += i;
    }
 
    printf("Resultado: %d\n", resultado);
 
    return 0;
}

Solução onde os conceitos matemáticos acima são utilizados:

 
#include <stdio.h>
 
int gauss(int n)
{
    return (n*(n+1))/2;
}
 
int main(int argc, char **argv)
{
    int resultado;
 
    resultado = (3*gauss(333) + 5*gauss(199)) - 15*gauss(66);
    printf("Resultado: %d\n", resultado);
 
    return 0;
}