Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

+3 votos
108 visitas
perguntada Mar 20 em Programação Computacional por Rodrigo Stuckert (46 pontos)  

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.

Compartilhe

4 Respostas

+1 voto
respondida Set 9 por Lucas Lourenço (51 pontos)  
selecionada Set 9 por Rodrigo Stuckert
 
Melhor resposta

Obrigado pela réplica, Rodrigo, foram muito boas as suas colocações. Gostaria de compartilhar também uma segunda solução que pensei após estudar as primeiras aulas do curso, em especial a aula 8 que traz a ideia de list comprehension. Em resumo, uso tal conceito e substituo as duas funções originais por uma. A descrição de cada passo encontra-se nas próprias linhas do código:

def encontra_triangulares_3(n):
if n == 0 or n == 1:
    return 1  # Manipulando primeiro as exceções
my_list=[1] 
k=2
while True:
    my_list.append(my_list[-1]+k) # my_list é atualizada com os triangulares 
    sqrt = int(np.floor(np.sqrt(my_list[-1]))) # Em cada etapa do loop, avaliamos a parte inteira da raiz quadrada do último elemento de my_list. 
    div_list = [i for i in range (1,sqrt+1) if my_list[-1] % i == 0] # Usamos então list comprehensions para criar a lista de divisores de 1 até sqrt
    if len(div_list) >= n/2: # Sem perda de generalidade, podemos definir essa condição para encontrar a resposta.
        return my_list[-1]
        break # Paramos o loop para que ele não faça um cálculo a mais.
    k += 1

# Executa o código
if __name__ == '__main__':
    print(encontra_triangulares_3(500))

Na aula, o professor comentou que list comprehensions são mais eficientes do que os loops for/while. Para ilustrarmos a eficiência, me baseei no código da aula 6 sobre complexidade de algoritmos. Temos em azul a função da minha resposta original, em verde a do Rodrigo e em vermelho a solução mais recente. Dividi a comparação em dois gráficos, um com n variando de 0 a 100 e outro de 0 a 600. Temos que de 0 a 300 divisores não se observa muita diferença, mas a partir desse ponto o código com list comprehensions torna-se gradativamente mais eficiente.

encontra triangulares 1 vs encontra triangulares 3
A imagem será apresentada aqui.
A imagem será apresentada aqui.

encontra triangulares 2 vs encontra triangulares 3
A imagem será apresentada aqui.
A imagem será apresentada aqui.

Novas sugestões, acréscimos e críticas ao são sempre bem-vindos.

Código para os gráficos de tempo de processamento:

import matplotlib.pyplot as plt  
import time   
import numpy as np      
n=100
times=np.empty([n,2])
theN=np.empty([n])
step=1
N=(-step+1)

for i in range(0,n):
    N=N+step
    theN[i]=N
    print(theN)

    beg_ts = time.time()
    encontra_triangulares_1(N)
    end_ts = time.time()
    times[i,0]=end_ts-beg_ts

    beg_ts = time.time()
    encontra_triangulares_3(N)
    end_ts = time.time()
    times[i,1]=end_ts-beg_ts

# Gráfico:
ax = plt.subplot(111)
ax.plot(theN,times[:,0],color='b')
ax.plot(theN,times[:,1],color='r')
ax.set_ylabel('Execution Time')
ax.set_xlabel('n')
plt.show()
comentou Set 9 por Rodrigo Stuckert (46 pontos)  
Muito boa sua solução, Lucas. Você conseguiu deixar a execução mais rápida, ao mesmo tempo em que cortou uma função da resolução, substituindo-a por uma única linha de código.

Assim sendo, tenho apenas uma sugestão de correção a fazer: assim como no meu primeiro código, essa versão não está apontando corretamente o número de divisores quando o triangular é um quadrado perfeito. Para corrigir isso, basta que você altere, dentro do loop while, a condição if de ">=" para ">". Assim, sua solução estará ideal.

No mais, nada mais tenho  a declarar, parabéns pela solução.
comentou Set 15 por Lucas Lourenço (51 pontos)  
Olá, Rodrigo. Obrigado pela resposta. De fato, eu mencionei tal exceção e eu mesmo caí nela. Parabéns pelas soluções.
+2 votos
respondida Mar 20 por Rodrigo Stuckert (46 pontos)  
editado Ago 6 por Rodrigo Stuckert

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:

import numpy as np # Pacote para lidar com vetores no Python

def encontra_divisores(x):
   """ Encontra os divisores de um inteiro x. """
  if (x == 0): # Se for zero ou um, tratamos como exceções
    return None
  elif(x==1):
      return(1)
  else:    # Do contrário, criamos um vetor vazio para receber os valores
      os_divisores = []
      count = 1
      sqrtx = np.floor(np.sqrt(x)) # np.floor arredonda para baixo

     # 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 count <= sqrtx:
        if x % count == 0:
            os_divisores.append(count)  # append adiciona entradas a vetores
        count += 1

      return(os_divisores)

Em seguida, criamos uma função para encontrar os números triangulares.

def encontra_triangulares(n):
    """ Encontra o menor número triangular com pelo menos "n" divisores. """
    soma = 1
    i = 2
    divisores = []  # Vetor para receber os divisores.

    # 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:  # len retorna o número de entradas em um vetor.
        divisores = []
        soma = soma + i
        i = i + 1
        divisores = encontra_divisores(soma)
    return(soma)

# Executa a função
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.

comentou Ago 4 por Lucas Lourenço (51 pontos)  
editado Ago 4 por Lucas Lourenço
Para comentar a resposta do Rodrigo, eu dividirei minha contribuição em três partes, com (1) um comentário geral, (2) alguns específicos e (3) uma alternativa de resposta.
+2 votos
respondida Ago 4 por Lucas Lourenço (51 pontos)  

Para comentar a resposta do Rodrigo, eu dividirei minha contribuição em três partes, com (1) um comentário geral, (2) alguns específicos e (3) uma alternativa de resposta.

1. Comentários gerais:

A resposta oferecida é bastante intuitiva, bem estruturada e não encontrei uma forma mais direta de resolver o problema. Se entendi corretamente o objetivo da função proposta, o que queremos é uma função que retorne o primeiro número triangular com pelo menos n divisores. Ao trabalhar com ela, no entanto, notei que não se encontra o resultado esperado para todos os valores de n. Pelo que fui capaz de diagnosticar, a resposta é adequada na maioria dos casos (inclusive quando n = 500, que é o que o exercício pede) porém em outros não, note:

A imagem será apresentada aqui.

Vamos considerar o primeiro caso em que há divergência. Quando n = 3, o primeiro número triangular com ao menos 3 divisores é 6:

D(1): 1
D(3): 1, 3
D(6): 1, 2, 3, 6

A função retorna 3. Isso acontece pois o while loop é interrompido no 3. Nesse estágio, a função avalia se “len(divisores) < n // 2”, em que o lado esquerdo da desigualdade corresponde ao tamanho da lista que contém metade dos divisores do número triangular em questão. No caso do 3, temos "len(divisores) = 1". Assim, seu comprimento é 1. Ao avaliar a sentença “len(divisores) < n // 2”, portanto, temos 1 < 1, o que, por ser falso, interrompe o loop. A resposta retornada é então 3. Para resolver, podemos utilizar a divisão convencional (/) ao invés da parte inteira (floor division, //). Dessa forma, a desigualdade analisada pelo loop passará a ser 1 < 1.5, que por ser verdadeira, dará continuidade ao loop. No entanto, ao fazer isso, uma resposta que estava correta antes passa a ficar incorreta agora (n = 1), além da diferença quando n = 10 ainda permanecer, note:

A imagem será apresentada aqui.

A primeira inconsistência (n = 1) surge pois, na primeira vez em que o loop roda, "len(divisores)" é igual a 0 e n/2 é igual 0.5. Assim, o while loop não é interrompido e o número triangular é atualizado para o seguinte (isto é, 3). Uma maneira mais simples de corrigir isso consiste em se criar uma exceção:

    if n == 0 or n == 1:
    return 1

Já a segunda inconsistência (n = 10) acontece devido a uma exceção que poucas vezes aparece, mas que deve ser considerada no código: nem sempre a lista retornada pela primeira função conterá metade dos divisores do número. Isso acontecerá particularmente naqueles casos em que o argumento avaliado tiver uma raiz quadrada inteira, como o 36, o que fará com que o número de divisores seja ímpar.

D(36): 1, 2, 3, 4, 6, 9, 12, 18, 36
encontra_divisores(36) = [1, 2, 3, 4, 5, 6]

Nesses casos, o loop deve continuar pois "len(divisores)" não terá metade do tamanho da lista de divisores de 36, mas sim a metade + 1. Por exemplo, se n for igual a 10 e não incluirmos essa exceção, a resposta será 36 pois "len(divisores) = 5" e "n/2 = 5". Mas note que o número de divisores de 36 não é 10, mas sim 9 – não podemos parar o loop aqui. Caso contrário – se a raiz não for inteira, o que representa a maioria dos casos – o loop é interrompido. Essa exceção só volta a se repetir no 48º número triangular (1225, cuja raiz é 35). Ela não interfere os demais resultados, sendo por isso o código original retorna a resposta correta quando n = 500. Para tratar tal exceção, proponho a seguinte estrutura:

        while len(divisores) <= n / 2:
        if len(divisores) == n / 2 and divisores[-1] != np.sqrt(soma):
            return soma
        else:
            soma = soma + i
            i = i + 1
            divisores = encontra_divisores_1(soma)
    return soma

Nela, definimos uma regra de parada do loop ao avaliar exatamente os casos com raiz não-inteira, que são a maioria. No entanto, se o último número da lista de divisores (indicado por "divisores[-1]") for igual à raiz quadrada do número triangular, permitimos o loop continuar rodando. Assim, quando n = 10, teremos o triangular 120.

2. Comentários específicos

Como ressaltei, a solução oferecida é bastante intuitiva e, ao meu entendimento, está bem estruturada. Alguns comentários bastante pontuais:

1. Na função "encontra_divisores", ao criar a exceção para quando x for igual a 1, seria interessante que a função retornasse o objeto lista

return [1]

ao invés do inteiro 1, apenas para que se mantenha o padrão do restante da função, que é sempre o de retornar uma lista. Caso contrário, se levarmos um inteiro para a função seguinte – que utiliza o comando len – podemos obter erro, já que esse comando é para listas, tuples, dicionários... mas não para números inteiros.

2. No while loop da função "encontra_triangulares", não me pareceu ser necessário declarar o objeto "divisores = [ ]" dentro do *loop*. Declará-lo no começo da função parece ser suficiente.

3. Resposta alternativa

# Contribuições Lucas Lourenço:
import numpy as np
def encontra_divisores_1(x):
  if (x == 0):
    return None
  elif(x==1):
      return [1]
  else:    
      os_divisores = []
      contador = 1
      sqrtx = np.floor(x**0.5)
      while contador <= sqrtx:
        if x % contador == 0:
            os_divisores.append(contador)
        contador += 1
      return(os_divisores)
def encontra_triangulares_1(n):
    soma = 1
    i = 2
    divisores = []
    if n == 0 or n == 1:
        return 1
    else:
        while len(divisores) <= n / 2:
            if len(divisores) == n / 2 and divisores[-1] != np.sqrt(soma):
                return soma
            else:
                soma = soma + i
                i = i + 1
                divisores = encontra_divisores_1(soma)
        return soma

Para gerar as tabelas comparativas da parte 1:

    for i in range (1,31):
    string=""
    if encontra_triangulares(i) != encontra_triangulares_1(i):
        string="*"
        print("{0: ^10d} | {1:^20d} | {2:^20d} | {3: ^10s}".format(i,encontra_triangulares(i),encontra_triangulares_1(i),string))

Quanto à eficiência, a resposta mantém a mesma estrutura do código original e, portanto, não há ganho de eficiência. Como não pensei em nenhuma solução que economize linhas ou simplifique as funções, deixo aqui o espaço aberto para que o Rodrigo, o professor e os demais colegas possam contribuir. Fiquem a vontade também para apontarem qualquer imprecisão ou deslize no meu comentário.

comentou Ago 6 por Rodrigo Stuckert (46 pontos)  
Excelentes apontamentos e sugestões, Lucas. Postei uma sugestão de nova formulação abaixo, visando a otimização no tempo de execução, e já incorporando suas observações
+1 voto
respondida Ago 6 por Rodrigo Stuckert (46 pontos)  
editado Ago 6 por Rodrigo Stuckert

Gostaria de agradecer às colocações do Lucas, que foram todas bastante válidas. Para resolver o problema da alocação temporal, decidi reformular a solução original sem o uso de listas ou vetores. Existe um overhead considerável toda vez que se usa a função append em uma lista, pois o Python estará constantemente realocando a memória reservada para aquela lista. Além disso, a questão solicita apenas nos exige que encontremos o número de divisores, de forma que não é imperativo saber quais são eles.

Também para evitar problemas com resultados imprecisos na função "encontra_divisores", optei por fazer com que ela calculasse o número exato de divisores, já levando em conta os casos de números que são quadrados perfeitos.

Segue a reformulação:

import numpy as np # Pacote de álgebra linear

def encontra_divisores_2(x): # teste
    """ Encontra o número de divisores de um número inteiro.

    x: inteiro.
    """
    if(x == 0): # Se for zero ou um, tratamos como exceções
        return None
    elif(x == 1):
        return(1)

    num_divisors = 0 # Número de divisores
    count = 1 # Número a ser testado (incrementalmente)
    sqrtx = np.ceil(np.power(x, 0.5)) # np.ceil: arredonda para cima

    while count < sqrtx:
        if x % count == 0: # Se a divisão for exata, adiciona o valor.
            num_divisors += 1
        count += 1

    # Dobraremos o número encontrado para saber o número de divisores
    if np.power(x, 0.5) % 1 == 0: # Se x for quadrado perfeito, sua raíz será divisor tb
        return((num_divisors * 2) + 1)
    else:
        return(num_divisors * 2)


def encontra_triangulares_2(n):
    """ Encontra o menor número triangular com pelo menos "n" divisores. 

    n: número de divisores
    """
    my_sum = 1 # Soma parcial dos números
    i = 2 # Próximo número a ser somado
    divisors = 1 # Contagem de divisores

    if n == 0 or n == 1:
        return(1)
    else:
        while divisors < n:
            my_sum = my_sum + i
            divisors = encontra_divisores_2(my_sum)
            i += 1
        return(my_sum)

# Executa o código
if __name__ == '__main__':
    print(encontra_triangulares_2(500))

Acredito que o caminho para futuras reduções do tempo de execução seria o uso de fatoriais pra encontrar os divisores. Deixo a porta aberta para sugestões de correções ou melhorias

...