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:  Este problema é fornecido pelo site maravilhoso  , que você pode assinar  ! 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!   ProjectEuler.net   aqui  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   que tem mais de 500   . Primeiramente, vamos dar uma olhada melhor no que é um número triangular e o que é um divisor. número triangular divisores  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   . aqui estão alguns exemplos:  você sempre pode organizá-los como um triângulo  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   , que afirmou que a soma de números inteiros consecutivos é igual a: Gauss  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   (ou   ) de um número   é muito simples: é   Por exemplo, 3 é um divisor de 18, porque podemos multiplicar 3 e 6 para obter 18 novamente. divisor fator n, um número   que pode ser multiplicado por outro inteiro   para dar   novamente. j k n  No entanto, 5 não é um divisor de 18, porque não há nenhum número   que multiplicado por 5 dê 18. k  Pela definição, também obtemos uma propriedade importante: se   é um divisor de   porque pode ser multiplicado por   para obter   então também   é um divisor de   porque pode ser multiplicado por   para obter  j n k n, k n j n.    (na verdade,   sempre pode ser 1 e   ser   ). Dessa forma, podemos ter certeza de que um número   sempre terá pelo menos dois divisores   e  n j k j k n  Além disso, colocando de outra forma,   . Assim, por exemplo, 18/3 = 6 e o restante é 0. um número   é um divisor do número   se o resto de   for igual a 0 j n n / j  Podemos formalizar melhor este conceito com   dizendo que   é um divisor de   se   Ou seja, obtemos esta segunda propriedade:  a aritmética modular j n n % j = 0.  A terceira e última propriedade que nos interessa é que   Isso é bem simples de entender. Pela primeira propriedade, sabemos que os fatores estão de alguma forma “ligados” no intervalo 1,…,n. não pode haver divisor de um número   maior que   em vez do próprio   . n n/2, n  Isso ocorre porque, novamente, se   é porque   Portanto, também   Vamos pegar 18 novamente como exemplo, encontrar seus divisores e colori-los para refletir essa propriedade.  j \ n, j * k = n. k \ n.  Então, por exemplo, se   e vice-versa se   isso significa que o menor   que podemos usar, além de 1, é 2, o que nos dá o maior   possível,   (9 no nosso caso)   Isso funciona: j = 3, k = 6, j = 6, k = 3, j k n/2 .  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   por 2 (porque ser ímpar nos dará um número racional); isso significa que só podemos usar   o que sempre nos dará resultados  n j > 2, k < n/2.  Finalmente,   Por exemplo, quando   um possível fator   produzirá outro fator   Discutiremos mais sobre esse caso posteriormente na parte do código. há apenas um caso em que   e   podem ser iguais: quando   é um número quadrado. j k n n = 36, j = 6 k = 6.  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   , 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   . Go 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:   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Criamos nossa função que aceita um inteiro   e retorna um array de inteiros   , que conterá nossos divisores. Depois disso,   aos fatores triviais, ou seja, 1 e o próprio   . n out out n  Em seguida, iniciamos o loop   de 2 para   (da segunda propriedade; observe também que não estamos interessados no próprio   porque, no caso de   ser par,   será adicionado aos divisores pelo   iteração: é por isso que paramos em   e não   ). j n/2 n/2 n k = n/2 j = 2 j<n/2 j≤ n/2  Dessa forma, podemos verificar os divisores apenas na primeira metade de   , acelerando bastante o processo. n  Em cada loop, verificamos 3 coisas:  A terceira instrução if realmente verifica se   , em outras palavras, se 0 ≡ n (mod j). Nesse caso, encontramos um fator e adicionamos   à lista. Também podemos acrescentar sua contraparte   à lista, calculando   e passando para o próximo   ; n%j==0 j k n/j j  A segunda instrução if verifica se   é um quadrado e, portanto,   é a raiz de   . Nesse caso, apenas um divisor   será adicionado a   , para evitar duplicatas, e então o algoritmo segue em frente. n j n j out  Suponha que   : se este pequeno bloco estivesse faltando, a terceira instrução if seria acionada, fazendo com que   recebesse   e   , criando assim uma duplicata. n = 36 out j = 6 k = n/j = 36/6 = 6  A primeira instrução if é a mais complexa: sua finalidade é verificar se estamos começando a ter pares   repetidos. Nesse caso, podemos quebrar o loop instantaneamente, pois nosso fator já estará presente em   . jk out  Especificamente sobre este terceiro ponto, há dois casos a verificar: se   ou   . out[len(out)-1] == j out[len(out)-2] == j  O primeiro caso é o clássico: pegue o número T₇ = 28 por exemplo:  Quando   , será igual ao último valor inserido. Portanto, podemos quebrar o loop. j = 7  O segundo caso só ocorre quando encontramos um quadrado   . Pegue 36 novamente, por exemplo: n  Quando   , será igual ao último valor anexado antes da raiz quadrada de   , que aparece apenas uma vez. Portanto, neste ponto, podemos quebrar o loop. j = 9 n  Finalmente, podemos simplesmente   para obter nossos divisores. return out   Aplicando os resultados  Agora que temos nossa função, podemos aplicá-la a todo número triangular. Vamos criar um contador   que servirá de gerador para nossos números triangulares. Calculamos o número triangular associado   com a equação de Gauss e verificamos quantos divisores ela possui. c tn  Se for maior que 500, retornamos esse   como resultado. tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Mas... tem um porém!    além de apresentar enigmas e problemas matemáticos,   . O ProjectEuler.net é realmente um projeto adorável: 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,   . 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! 😅 não acho justo apenas fornecer a solução para copiar e colar e obter a conquista   Complexidade de tempo  Estou confiante de que existem muitas soluções melhores porque acho que esta é uma foto terrível!  A função   executa em tempo linear: já que depende do tamanho da instância   , e também executa no máximo   loops; podemos considerá-lo um O(n). FindDivisor n n/2  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   se torna o argumento ou nossa função e executamos no máximo   loops dentro dele, podemos reescrever a complexidade de tempo como O(tn*tn/2) = O(tn²/2) = O(tn²). Portanto, uma   , infelizmente! tn n/2 solução de tempo quadrático  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

Read My Stories

Este áudio é produzido no idioma original da história!

Muito longo; Para ler

Make resilience your competitive advantage

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

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Digital Nomads Ouçam: O que você precisa saber sobre o novo visto DTV da Tailândia

Modelo Bitcoin UTXO, alimentando um ecossistema único

Crescimento de Criptomoedas: Criando Personas de Usuários Eficazes

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Digital Nomads Ouçam: O que você precisa saber sobre o novo visto DTV da Tailândia

Modelo Bitcoin UTXO, alimentando um ecossistema único

Crescimento de Criptomoedas: Criando Personas de Usuários Eficazes

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps