Encontrando o menor número triangular com pelo menos n divisores

Question

Uma sequência de números triangulares é gerada adicionando os números naturais. Portanto, o sétimo número triangular seria \begin{equation}1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 \end{equation} Os dez primeiros termos seriam:
\begin{equation} 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\end{equation}

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

1: 1.
3: 1, 3.
6: 1, 2, 3, 6.
10: 1, 2, 5, 10.
15: 1, 3, 5, 15.
21: 1, 3, 7, 21.
28: 1, 2, 4, 7, 14, 28.

Podemos ver que 28 é o primeiro número triangular a ter mais de cinco divisores. Qual é o valor do primeiro número triangular que tem pelo menos quinhentos divisores?

Discuta a eficiência da sua solução.

Answer 1

A ideia aqui é escrever uma função que calcule os números triangulares e, em seguida, chame outra função que verifique a quantidade de divisores que eles apresentam. Note que aqui não é necessário saber quais são os divisores de cada triangular, apenas sua quantidade.

Uma solução em Python seria:

# Importando o pacote Numpy, para lidar com vetores no Python
import numpy as np

# Criando a função que encontrará os divisores.
def encontra_divisores(x):
  # Se for zero ou um, tratamos como exceções
  if (x == 0):
    return None
  elif(x==1):
      return 1
  # Do contrário, criamos um vetor vazio para receber os valores
  else:    
      os_divisores = []
      contador = 1
      sqrtx = np.floor(np.sqrt(x))
     # Rodaremos um loop que parará quando a contagem for igual
     # à raiz quadrada de x, uma vez que necessariamente metade
     # dos divisores de x encontrar-se-á entre 1 e x^(1/2)
      while contador <= sqrtx:
        if x % contador == 0:
           # A função append adiciona entradas a vetores
            os_divisores.append(contador)
        contador += 1
      # Por fim, retornamos o resultado encontrado.
      return(os_divisores)

Em seguida, criamos uma função que recebe um valor "n" e encontra o menor número triangular com pelo menos "n" divisores.

def encontra_triangulares(n):
    soma = 1
    i = 2
    # Criamos aqui um vetor para receber os divisores.
    divisores = []
    # A função len retorna o número de entradas em um vetor.
    # Uma vez que na função anterior encontramos metade dos
    # divisores do numero recebido,  basta que o vetor tenha
    # do cumprimento n desejado.
    while len(divisores) < n // 2:
        divisores = []
        soma = soma + i
        i = i + 1
        divisores = encontra_divisores(soma)
    return(soma)

# Executando a função acima
if __name__ == '__main__':
    print(encontra_triangulares(500))

O resultado é 76576500.

De fato, em minha máquina (16GB de RAM), o código demorou cerca de 90 segundos para executar com n = 500, o que levanta a hipótese de que esse pode não ser o código mais eficiente para tal tarefa. Sinta-se à vontade para sugerir alternativas nos comentários.