¡Bienvenidos todos con otro problema que resolver! Hoy hablaremos sobre los números triangulares y sus divisores: ¡especialmente los enormes!  Si bien podemos admirar mi fabulosa representación artística de números triangulares en la naturaleza, tengamos nuestros descargos de responsabilidad habituales:  Este problema lo proporciona el maravilloso sitio web.  , al que puedes suscribirte  ! Hay más de 800 problemas matemáticos y de codificación para resolver y un vasto archivo de discusiones sobre ellos. ¡Es, literalmente, la herramienta perfecta para desmontar la cabeza y aprender algo nuevo! ¡Echa un vistazo y trata de resolver tus desafíos también!   ProyectoEuler.net   aquí  No soy un programador experto: solo un tipo que disfruta escribiendo sobre este tipo de cosas y le gusta compartir sus tomas. Estoy seguro de que esta no será la solución óptima, así que si tienes una mejor o alguna idea sobre cómo optimizarla, ¡eres más que bienvenido si quieres compartirla!  Basta de hablar, veamos qué tiene que ofrecer el problema de hoy:   La secuencia de números triangulares se genera sumando los números naturales. Entonces, el número del séptimo triángulo sería 1+2+3+4+5+6+7=28. Los diez primeros términos serían: 1,3,6,10,15,21,28,36,45,55,…     Hagamos una lista de los factores de los primeros siete números triangulares:   Podemos ver que 28 es el primer número triangular que tiene más de cinco divisores.   ¿Cuál es el valor del primer número triangular que tiene más de quinientos divisores?  El problema es bastante sencillo: se nos pide que entendamos cuál es el primer   que tiene más de 500   . Lo primero es lo primero, veamos mejor qué es un número triangular y qué es un divisor. número triangular divisores  números triangulares  Los números triangulares son un subconjunto particular de números que se forman por la suma de todos los números naturales hasta uno determinado. Se llaman triangulares porque   . Aquí hay unos ejemplos:  siempre puedes organizarlos como un triángulo  En la imagen de arriba, son los números triangulares 3, 4 y 5. Entonces, por ejemplo, el tercer número se forma como 1+2+3 = 6, el cuarto como 1+2+3+4 = 10, y así sucesivamente. Entonces, en términos generales, el número triangular nᵗʰ, Tₙ, es igual a  Esta es, por supuesto, una de las series más famosas de las matemáticas, presentada también por   , quien afirmó que la suma de los enteros consecutivos es igual a: Gauss  Básicamente, si queremos calcular el tercer número triangular, por ejemplo, simplemente calculamos 3*4/2 = 6. ¡Esto será muy útil una vez que comencemos a escribir nuestra solución!   los divisores  Para dar una definición del   (o   ) de un número   es realmente simple: es   Por ejemplo, 3 es divisor de 18, porque podemos multiplicar 3 y 6 para obtener de nuevo 18. divisor factor n, un número   que se puede multiplicar por otro entero   para dar   nuevamente. j k n  Sin embargo, 5 no es divisor de 18, porque no hay un número   que multiplicado por 5 dé como resultado 18. k  Por definición, también obtenemos una propiedad importante: si   es un divisor de   porque puede multiplicarse por   para obtener   entonces también   es un divisor de   porque puede multiplicarse por   para obtener  j n k n, k n j n.    (de hecho,   siempre puede ser 1 y   ser   ). De esta forma podemos estar seguros de que un número   siempre tiene al menos dos divisores   y  n j k j k n  Además, por decirlo de otra forma,   . Entonces, por ejemplo, 18/3 = 6 y el resto es 0. un número   es divisor del número   si el resto de   es igual a 0 j n n/j  Podemos formalizar mejor este concepto con   diciendo que   es divisor de   si   En otras palabras, obtenemos esta segunda propiedad:  aritmética modular j n n % j = 0.  La tercera y última propiedad que nos interesa es que   Esto es bastante simple de entender. De la primera propiedad, sabemos que los factores están de alguna manera “vinculados” entre sí en el rango 1,…,n. no puede haber divisor de un número   mayor que   en lugar de   mismo. n n/2, n  Esto se debe a que nuevamente, si   es porque   Por tanto, también   Tomemos 18 nuevamente como ejemplo, busquemos sus divisores y coloréelos para reflejar esta propiedad.  j \ n, j * k = n. k\n.  Entonces, por ejemplo, si   y al revés si   esto significa que el   más pequeño que podemos usar, además de 1, es 2, lo que nos da el   más grande posible,   (9 en nuestro caso)   Esto funciona: j = 3, k = 6, j = 6, k = 3, j k n/2 .  para números pares, en cuyo caso el factor mayor será exactamente igual a la mitad de  n;  para números impares: si no podemos dividir   por 2 (porque ser impar nos dará un número racional); esto significa que solo podemos usar   lo que siempre nos dará resultados  n j > 2, k < n/2.  Finalmente,   Por ejemplo, cuando   un factor posible   producirá otro factor   Hablaremos más sobre este caso más adelante en la parte del código. solo hay un caso en el que   y   pueden ser iguales: cuando   es un número cuadrado. j k n n = 36, j = 6 k = 6.  Estos conceptos son bastante triviales, por supuesto, ¡pero serán muy importantes en nuestra solución!   El código  El código se escribirá en   , ya que es un lenguaje realmente rápido que aún mantiene un gran nivel de legibilidad. Partiremos la solución en dos: primero, crearemos   . Go una función para encontrar los divisores de un número, y luego la aplicaremos a los números triangulares  Veamos primero la función:   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Creamos nuestra función que acepta un número entero   y devuelve una matriz de números   , que contendrá nuestros divisores. Después de eso,   los factores triviales, a saber, 1 y   . n out out n  Luego comenzamos a hacer un bucle   de 2 a   (de la segunda propiedad; también tenga en cuenta que no estamos interesados en   en sí mismo porque en caso de que   sea par,   se agregará a los divisores por   iteración: por eso nos detenemos en   y no   ). j n/2 n/2 n k = n/2 j = 2 j<n/2 j≤ n/2  De esta manera, podemos comprobar si hay divisores solo en la primera mitad de   , lo que acelera bastante el proceso. n  En cada bucle, comprobamos 3 cosas:  La tercera instrucción if en realidad verifica si   , en otras palabras, si 0 ≡ n (mod j). Si es así, encontramos un factor y agregamos   a la lista. También podemos agregar su contraparte   a la lista, calculando   y luego pasar al siguiente   ; n%j==0 j k n/j j  La segunda instrucción if verifica si   es un cuadrado, y si   es la raíz de   . Si es así, solo se agregará un divisor   a   , para evitar duplicados, y luego el algoritmo continúa. n j n j out  Supongamos que   : si faltara este pequeño bloque, se activaría la tercera instrucción if, lo que   que recibiera   y   , creando así un duplicado. n = 36 out j = 6 k = n/j = 36/6 = 6  La primera declaración if es la más compleja: su propósito es verificar si estamos comenzando a tener pares   repetidos. Si es así, podemos romper el bucle instantáneamente, ya que nuestro factor ya estará presente de entrada y   . jk out  Específicamente sobre este tercer punto, hay dos casos para verificar: si   o   . out[len(out)-1] == j out[len(out)-2] == j  El primer caso es el clásico: toma el número T₇ = 28 por ejemplo:  Cuando   , será igual al último valor insertado. Por lo tanto, podemos romper el bucle. j = 7  El segundo caso solo ocurre cuando encontramos un cuadrado   . Tome 36 de nuevo, por ejemplo: n  Cuando   , será igual al último valor añadido antes de la raíz cuadrada de   , que aparece una sola vez. Por lo tanto, en este punto, podemos romper el ciclo. j = 9 n  Finalmente, podemos simplemente   a tener nuestros divisores. return out   Aplicación de los resultados  Ahora que tenemos nuestra función, podemos aplicarla a cada número triangular. Vamos a crear un contador   que servirá como generador de nuestros números triangulares. Calculamos el número triangular asociado   con la ecuación de Gauss y comprobamos cuántos divisores tiene. c tn  Si es más de 500, devolvemos ese   como resultado. tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Pero... ¡hay una trampa!    además de presentar acertijos y problemas matemáticos,   . ProjectEuler.net es realmente un proyecto encantador: su objetivo principal es proporcionar una herramienta para comenzar a aprender, pensar y razonar sobre matemáticas  Y eso me encanta: están tan comprometidos que publicar resultados y guías para sus problemas está prohibido (este es uno de los primeros 100 problemas, así que entiendo que está permitido).  Dado esto,   . Por esta razón, no le estoy dando la solución real: pruébelo usted mismo e intente encontrar un algoritmo mejor que el mío (hay muchos). ¡Lo siento chicos! 😅 no creo que sea justo simplemente dar la solución para copiar y pegar y obtener el logro   Complejidad del tiempo  ¡Estoy seguro de que hay muchas mejores soluciones porque siento que esta es una oportunidad bastante terrible!  La función   se ejecuta en tiempo lineal: ya que depende del tamaño de la instancia   , y también se ejecuta como máximo   bucles; podemos considerarlo como un O(n). FindDivisor n n/2  Sin embargo, primero debemos calcular cada número triangular, lo que también toma un tiempo O(tn), donde tn es el resultado (el último que realmente calculamos). Dado esto, aproximadamente la complejidad temporal de todo el algoritmo debería ser O(tn*n).  Dado que   se convierte en el argumento o nuestra función, y ejecutamos como máximo   bucles dentro de él, podemos reescribir la complejidad del tiempo como O(tn*tn/2) = O(tn²/2) = O(tn²). Entonces, ¡una   , desafortunadamente! tn n/2 solución de tiempo cuadrático  Sin embargo, me sorprendió que incluso si el algoritmo tiene ese tipo de complejidad, funciona bastante rápido. Para dar un resultado en mi máquina (AMD Ryzen 5, avg. ck. 2700 MHz) tomó 322.564227 ms.  Sin embargo, tratar de encontrar el primer número triangular que supere los 1000 divisores tomó 3.827144472 segundos, por lo que es claramente visible que el consumo de tiempo está aumentando rápidamente.   Conclusión  ¡Finalmente lo logramos! Espero que hayan disfrutado el artículo y que puedan sacar algo interesante de él: si es así, dejen un par de aplausos y compartan el artículo con alguien que pueda estar interesado en este tema.  Un gran agradecimiento a ProjectEuler nuevamente por el fantástico trabajo: realmente quiero sugerirle que vaya y vea lo que pueden ofrecer; ¡Seguro que te resultará súper interesante!  Y como siempre, gracias por leer.   Nicolás

Read My Stories

Este audio es producido en el idioma original de la historia!

Problema diario de codificación: números triangulares y grandes divisores

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Las capas invisibles: por qué las entrevistas con los usuarios son un activo irremplazable

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Las capas invisibles: por qué las entrevistas con los usuarios son un activo irremplazable

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps