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

¡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:

1. Este problema lo proporciona el maravilloso sitio web. ProyectoEuler.net , al que puedes suscribirte aquí ! 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!

   
   

2. 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 número triangular que tiene más de 500 divisores . Lo primero es lo primero, veamos mejor qué es un número triangular y qué es un divisor.

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 siempre puedes organizarlos como un triángulo . Aquí hay unos ejemplos:

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 Gauss , quien afirmó que la suma de los enteros consecutivos es igual a:

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 divisor (o factor ) de un número n, es realmente simple: es un número j que se puede multiplicar por otro entero k para dar n nuevamente. Por ejemplo, 3 es divisor de 18, porque podemos multiplicar 3 y 6 para obtener de nuevo 18.

Sin embargo, 5 no es divisor de 18, porque no hay un número k que multiplicado por 5 dé como resultado 18.

Por definición, también obtenemos una propiedad importante: si j es un divisor de n porque puede multiplicarse por k para obtener n, entonces también k es un divisor de n porque puede multiplicarse por j para obtener n.

De esta forma podemos estar seguros de que un número n siempre tiene al menos dos divisores j y k (de hecho, j siempre puede ser 1 y k ser n ).

Además, por decirlo de otra forma, un número j es divisor del número n si el resto de n/j es igual a 0 . Entonces, por ejemplo, 18/3 = 6 y el resto es 0.

Podemos formalizar mejor este concepto con aritmética modular diciendo que j es divisor de n si n % j = 0. En otras palabras, obtenemos esta segunda propiedad:

La tercera y última propiedad que nos interesa es que no puede haber divisor de un número n mayor que n/2, en lugar de n mismo. 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.

Esto se debe a que nuevamente, si j \ n, es porque j * k = n. Por tanto, también k\n. Tomemos 18 nuevamente como ejemplo, busquemos sus divisores y coloréelos para reflejar esta propiedad.

Entonces, por ejemplo, si j = 3, k = 6, y al revés si j = 6, k = 3, esto significa que el j más pequeño que podemos usar, además de 1, es 2, lo que nos da el k más grande posible, n/2 (9 en nuestro caso) . Esto funciona:

• 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 n por 2 (porque ser impar nos dará un número racional); esto significa que solo podemos usar j > 2, lo que siempre nos dará resultados k < n/2.

  
  

Finalmente, solo hay un caso en el que j y k pueden ser iguales: cuando n es un número cuadrado. Por ejemplo, cuando n = 36, un factor posible j = 6 producirá otro factor k = 6. Hablaremos más sobre este caso más adelante en la parte del código.

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 Go , 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 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:

Creamos nuestra función que acepta un número entero n y devuelve una matriz de números out , que contendrá nuestros divisores. Después de eso, out los factores triviales, a saber, 1 y n .

Luego comenzamos a hacer un bucle j de 2 a n/2 (de la segunda propiedad; también tenga en cuenta que no estamos interesados en n/2 en sí mismo porque en caso de que n sea par, k = n/2 se agregará a los divisores por j = 2 iteración: por eso nos detenemos en j<n/2 y no j≤ n/2 ).

De esta manera, podemos comprobar si hay divisores solo en la primera mitad de n , lo que acelera bastante el proceso.

En cada bucle, comprobamos 3 cosas:

• La tercera instrucción if en realidad verifica si n%j==0 , en otras palabras, si 0 ≡ n (mod j). Si es así, encontramos un factor y agregamos j a la lista. También podemos agregar su contraparte k a la lista, calculando n/j y luego pasar al siguiente j ;

• La segunda instrucción if verifica si n es un cuadrado, y si j es la raíz de n . Si es así, solo se agregará un divisor j a out , para evitar duplicados, y luego el algoritmo continúa.

  
  

  Supongamos que n = 36 : si faltara este pequeño bloque, se activaría la tercera instrucción if, lo que out que recibiera j = 6 y k = n/j = 36/6 = 6 , creando así un duplicado.

• La primera declaración if es la más compleja: su propósito es verificar si estamos comenzando a tener pares jk repetidos. Si es así, podemos romper el bucle instantáneamente, ya que nuestro factor ya estará presente de entrada y out .

  
  

Específicamente sobre este tercer punto, hay dos casos para verificar: si out[len(out)-1] == j o out[len(out)-2] == j .

El primer caso es el clásico: toma el número T₇ = 28 por ejemplo:

Cuando j = 7 , será igual al último valor insertado. Por lo tanto, podemos romper el bucle.

El segundo caso solo ocurre cuando encontramos un cuadrado n . Tome 36 de nuevo, por ejemplo:

Cuando j = 9 , será igual al último valor añadido antes de la raíz cuadrada de n , que aparece una sola vez. Por lo tanto, en este punto, podemos romper el ciclo.

Finalmente, podemos simplemente return out a tener nuestros divisores.

Aplicación de los resultados

Ahora que tenemos nuestra función, podemos aplicarla a cada número triangular. Vamos a crear un contador c que servirá como generador de nuestros números triangulares. Calculamos el número triangular asociado tn con la ecuación de Gauss y comprobamos cuántos divisores tiene.

Si es más de 500, devolvemos ese tn como resultado.

Pero... ¡hay una trampa!

ProjectEuler.net es realmente un proyecto encantador: además de presentar acertijos y problemas matemáticos, 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, no creo que sea justo simplemente dar la solución para copiar y pegar y obtener el logro . 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! 😅

Complejidad del tiempo

¡Estoy seguro de que hay muchas mejores soluciones porque siento que esta es una oportunidad bastante terrible!

La función FindDivisor se ejecuta en tiempo lineal: ya que depende del tamaño de la instancia n , y también se ejecuta como máximo n/2 bucles; podemos considerarlo como un O(n).

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 tn se convierte en el argumento o nuestra función, y ejecutamos como máximo n/2 bucles dentro de él, podemos reescribir la complejidad del tiempo como O(tn*tn/2) = O(tn²/2) = O(tn²). Entonces, ¡una solución de tiempo cuadrático , desafortunadamente!

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