Problema de Codificação Diária: Números Triangulares e Grandes Divisores

Bem vindos a todos com mais um problema para resolver! Hoje falaremos sobre números triangulares e seus divisores: especialmente os enormes!

Embora possamos admirar minha fabulosa representação artística de números triangulares na natureza, vamos fazer nossas isenções de responsabilidade habituais:

1. Este problema é fornecido pelo site maravilhoso ProjectEuler.net , que você pode assinar aqui ! Existem mais de 800 problemas de matemática e codificação para resolver e um vasto arquivo de discussões sobre eles. É literalmente a ferramenta perfeita para quebrar a cabeça e aprender algo novo! Vá conferir e tente resolver seus desafios também!

   
   

2. Não sou um programador especialista: apenas um cara que gosta de escrever sobre esse tipo de coisa e gosta de compartilhar suas fotos. Tenho certeza de que esta não será a solução ideal, portanto, se você tiver uma melhor ou tiver alguma ideia sobre como otimizá-la, será mais do que bem-vindo se quiser compartilhar!

Chega de papo, vamos ver o que o problema de hoje tem a oferecer:

A sequência de números triangulares é gerada pela adição dos números naturais. Portanto, o 7º número do triângulo seria 1+2+3+4+5+6+7=28. Os dez primeiros termos seriam:1,3,6,10,15,21,28,36,45,55,…

Vamos listar os fatores dos sete primeiros números triangulares:

Podemos ver que 28 é o primeiro número triangular a ter mais de cinco divisores.

Qual é o valor do primeiro número triangular a ter mais de quinhentos divisores?

O problema é bastante direto: nos pedem para entender qual é o primeiro número triangular que tem mais de 500 divisores . Primeiramente, vamos dar uma olhada melhor no que é um número triangular e o que é um divisor.

Números Triangulares

Números triangulares são um subconjunto particular de números que são formados pela soma de todos os números naturais até um certo. Eles são chamados de triangulares porque você sempre pode organizá-los como um triângulo . aqui estão alguns exemplos:

Na imagem acima, são o 3º, o 4º e o 5º números triangulares. Assim, por exemplo, o 3º número é formado como 1+2+3 = 6, o 4º como 1+2+3+4 = 10 e assim por diante. De modo geral, então, o número triangular nᵗʰ, Tₙ, é igual a

Esta é, com certeza, uma das séries mais famosas da matemática, apresentada também por Gauss , que afirmou que a soma de números inteiros consecutivos é igual a:

Então, basicamente, se quisermos calcular o terceiro número triangular, por exemplo, simplesmente calculamos 3*4/2 = 6. Isso será muito útil quando começarmos a escrever nossa solução!

os divisores

Para dar uma definição do divisor (ou fator ) de um número n, é muito simples: é um número j que pode ser multiplicado por outro inteiro k para dar n novamente. Por exemplo, 3 é um divisor de 18, porque podemos multiplicar 3 e 6 para obter 18 novamente.

No entanto, 5 não é um divisor de 18, porque não há nenhum número k que multiplicado por 5 dê 18.

Pela definição, também obtemos uma propriedade importante: se j é um divisor de n porque pode ser multiplicado por k para obter n, então também k é um divisor de n porque pode ser multiplicado por j para obter n.

Dessa forma, podemos ter certeza de que um número n sempre terá pelo menos dois divisores j e k (na verdade, j sempre pode ser 1 e k ser n ).

Além disso, colocando de outra forma, um número j é um divisor do número n se o resto de n / j for igual a 0 . Assim, por exemplo, 18/3 = 6 e o restante é 0.

Podemos formalizar melhor este conceito com a aritmética modular dizendo que j é um divisor de n se n % j = 0. Ou seja, obtemos esta segunda propriedade:

A terceira e última propriedade que nos interessa é que não pode haver divisor de um número n maior que n/2, em vez do próprio n . Isso é bem simples de entender. Pela primeira propriedade, sabemos que os fatores estão de alguma forma “ligados” no intervalo 1,…,n.

Isso ocorre porque, novamente, se j \ n, é porque j * k = n. Portanto, também k \ n. Vamos pegar 18 novamente como exemplo, encontrar seus divisores e colori-los para refletir essa propriedade.

Então, por exemplo, se j = 3, k = 6, e vice-versa se j = 6, k = 3, isso significa que o menor j que podemos usar, além de 1, é 2, o que nos dá o maior k possível, n/2 (9 no nosso caso) . Isso funciona:

• para números pares, caso em que o maior fator será exatamente igual à metade de n;

• para números ímpares: se não podemos dividir n por 2 (porque ser ímpar nos dará um número racional); isso significa que só podemos usar j > 2, o que sempre nos dará resultados k < n/2.

  
  

Finalmente, há apenas um caso em que j e k podem ser iguais: quando n é um número quadrado. Por exemplo, quando n = 36, um possível fator j = 6 produzirá outro fator k = 6. Discutiremos mais sobre esse caso posteriormente na parte do código.

Esses conceitos são bastante triviais, claro, mas serão muito importantes em nossa solução!

O código

O código será escrito em Go , pois é realmente uma linguagem rápida que ainda mantém um ótimo nível de legibilidade. Vamos dividir a solução em duas: primeiro, vamos criar uma função para encontrar os divisores de um número, e depois vamos aplicá-la aos números triangulares .

Vamos ver a função primeiro:

Criamos nossa função que aceita um inteiro n e retorna um array de inteiros out , que conterá nossos divisores. Depois disso, out aos fatores triviais, ou seja, 1 e o próprio n .

Em seguida, iniciamos o loop j de 2 para n/2 (da segunda propriedade; observe também que não estamos interessados no próprio n/2 porque, no caso de n ser par, k = n/2 será adicionado aos divisores pelo j = 2 iteração: é por isso que paramos em j<n/2 e não j≤ n/2 ).

Dessa forma, podemos verificar os divisores apenas na primeira metade de n , acelerando bastante o processo.

Em cada loop, verificamos 3 coisas:

• A terceira instrução if realmente verifica se n%j==0 , em outras palavras, se 0 ≡ n (mod j). Nesse caso, encontramos um fator e adicionamos j à lista. Também podemos acrescentar sua contraparte k à lista, calculando n/j e passando para o próximo j ;

• A segunda instrução if verifica se n é um quadrado e, portanto, j é a raiz de n . Nesse caso, apenas um divisor j será adicionado a out , para evitar duplicatas, e então o algoritmo segue em frente.

  
  

  Suponha que n = 36 : se este pequeno bloco estivesse faltando, a terceira instrução if seria acionada, fazendo com que out recebesse j = 6 e k = n/j = 36/6 = 6 , criando assim uma duplicata.

• A primeira instrução if é a mais complexa: sua finalidade é verificar se estamos começando a ter pares jk repetidos. Nesse caso, podemos quebrar o loop instantaneamente, pois nosso fator já estará presente em out .

  
  

Especificamente sobre este terceiro ponto, há dois casos a verificar: se out[len(out)-1] == j ou out[len(out)-2] == j .

O primeiro caso é o clássico: pegue o número T₇ = 28 por exemplo:

Quando j = 7 , será igual ao último valor inserido. Portanto, podemos quebrar o loop.

O segundo caso só ocorre quando encontramos um quadrado n . Pegue 36 novamente, por exemplo:

Quando j = 9 , será igual ao último valor anexado antes da raiz quadrada de n , que aparece apenas uma vez. Portanto, neste ponto, podemos quebrar o loop.

Finalmente, podemos simplesmente return out para obter nossos divisores.

Aplicando os resultados

Agora que temos nossa função, podemos aplicá-la a todo número triangular. Vamos criar um contador c que servirá de gerador para nossos números triangulares. Calculamos o número triangular associado tn com a equação de Gauss e verificamos quantos divisores ela possui.

Se for maior que 500, retornamos esse tn como resultado.

Mas... tem um porém!

O ProjectEuler.net é realmente um projeto adorável: além de apresentar enigmas e problemas matemáticos, seu foco principal é fornecer uma ferramenta para começar a aprender, pensar e raciocinar sobre matemática .

E eu adoro isso: eles estão tão comprometidos que publicar resultados e guias para seus problemas é realmente proibido (esse é um dos primeiros 100 problemas, então eu entendo que é permitido).

Diante disso, não acho justo apenas fornecer a solução para copiar e colar e obter a conquista . Por esse motivo, não estou dando a você a solução real: experimente você mesmo e tente criar um algoritmo melhor que o meu (existem muitos). Desculpem rapazes! 😅

Complexidade de tempo

Estou confiante de que existem muitas soluções melhores porque acho que esta é uma foto terrível!

A função FindDivisor executa em tempo linear: já que depende do tamanho da instância n , e também executa no máximo n/2 loops; podemos considerá-lo um O(n).

No entanto, devemos calcular cada número triangular primeiro, o que também leva tempo O(tn), onde tn é o resultado (o último que realmente calculamos). Dado isso, aproximadamente a complexidade de tempo de todo o algoritmo deve ser O(tn*n).

Como tn se torna o argumento ou nossa função e executamos no máximo n/2 loops dentro dele, podemos reescrever a complexidade de tempo como O(tn*tn/2) = O(tn²/2) = O(tn²). Portanto, uma solução de tempo quadrático , infelizmente!

Fiquei surpreso, porém, que mesmo que o algoritmo seja desse tipo de complexidade, ele roda muito rápido mesmo assim. Para dar um resultado na minha máquina (AMD Ryzen 5, avg. ck. 2700 MHz), demorou 322,564227 ms.

Tentar encontrar o primeiro número triangular excedendo 1000 divisores levou 3,827144472 segundos, então é claramente visível que o consumo de tempo está aumentando rapidamente.

Conclusão

Finalmente conseguimos! Espero que tenham gostado do artigo, e espero que tenham tirado algo interessante dele: se sim, por favor, deixem um ou dois palmas e compartilhem o artigo com alguém que possa se interessar por esse assunto!

Um grande agradecimento ao ProjectEuler novamente pelo trabalho fantástico: eu realmente quero sugerir que você vá e verifique o que eles podem oferecer; Tenho certeza que você vai achar super interessante!

E como sempre, obrigado por ler.

Nicola