Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the th triangle number would be 1 + 2 + 3 + 4 + 5 + ... + n . The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Brute force

Tentar calcular os números triangulares e verificar quantos divisores tem?

Tentativa 1 - 26/12/2025

Inicialmente essa o programa rodava por muito tempo, desconfio que tenho que aprimorar essa função de divisores.

Pensando melhor

1. O for-loop deve ir só até metade do número
2. Procurar somente os números pares, porque eles tem bem mais dividores

Ainda assim para calcular apenas um triangle = 1 bilhão, o programa demora 2 segundos

Tentativa 2 - 26/12/2025

Precisa achar outra forma de calcular os divisores ou otimizar essa função existente

Considerar que o primeiro número com 500 divisores seja um par bem redondo, tipo 1000? ou 1200? E se em vez de procurar o número, eu forçasse ser $2 . 4 . 6 . 8$? Vou testar multiplicar os 100 primeiros pares

Vish, da um numero muito enorme

Sem brute force

Considerando que o número 28 já tem 6 divisores

Tentativa 3 - 26/12/2025

Vou fazer um script pra tentar achar um padrão nos números de até 3 digitos (999) que tenham mais divisores

A intuição de que seria um par bem redondo bateu, mas O que tem de especial no 840?

Factorizando por primos $840 = 2 * 2 * 2 * 3 * 5 * 7$ Vários primos pequenos?

Tentativa 4 - 26/12/2025

Não posso viajar muito, o número em questão precisa ser um triângulo. Ainda preciso testar eles

Como que 28 = 6 divisores? Como que 840 = 32 divisores?

Tive que pequisar

$28 = 2 * 2 * 7 = 2^2 * 7^1$

$840 = 2 * 2 * 2 * 3 * 5 * 7 = 2^3 * 3^1 * 5^1 * 7^1$

Existe uma fórmula, conta-se os expoentes e soma 1

$(a+1)(b+1)(c+1)...$

$840 = (3+1)(1+1)(1+1)(1+1) = 4 * 2 * 2 * 2 = 32$

Então eu quero uma fórmula que me dê o número de divisores de um número

$(a+1)(b+1)(c+1)... > 500$

Ou tentar calcular divisores assim, inves de brute force, aí eu posso verificar manualmente os números triangulares

Vou ter que achar novamente a fórmula de fatorização por primos (já usei em algum desafio anterior)

resposta 76576500

agora com um log dos últimos números para poder verificar se não tem nada errado