OTIMIZAÇÃO NO CÁLCULO DO
NUMERO DE DIVISORES DOS
NUMEROS TRIANGULARES
César Henrique Bernabé
Lucas Augusto Santos
Os Numeros Triangulares

Os numeros triangulares são gerados pela adição dos
numeros naturais:
1= 1
3= 1+2
6= 1+2+3
10= 1+2+3+4

O PROBLEMA: Encontrar o primeiro numero
triangular com 500 divisores em tempo ágil.
A primeira solução

Primeiramente tentamos achar “na força
bruta” gerando a lista com os numeros
triangulares e contando os divisores de cada
um.
divisores1 n = [x|x<-[1..n], y<-[1..n], n ==
x*y] (203729 reduções)
triangularrecursivo a = if a==1 then 1 else
(triangularrecursivo (a-1) + a)
(1218 reduções)
A primeira solução
As funções não se mostraram eficientes por dois
motivos:
1. O número de reduções da primeira função é alto
pois é necessário percorrer duas listas de tamanho n,
ficando assim n² comparações.
2. A segunda função, apesar de ser recursiva, não é
eficiente, pois a medida que a cresce, será necessário
fazer todas as comparações menores que ‘a’ até
chegar a base da recursão.

A segunda solução

Como segunda tentativa, chegamos as
seguintes soluções:
divisores2 n = [x| x<-[1..n], mod n x ==0]
(8154 reduções)
triangular a = (a* (a+1)/2) (41 reduções)
Essa segunda solução trabalha de forma
semelhante
à
primeira, porém
com
modificação nas funções.
A segunda solução
Foram feitos dois aprimoramentos:
 O numero de comparações da primeira função
agora é n, já que depende somente do
tamanho de uma lista.
 A segunda função agora calcula diretamente o
número triangular n, sem depender dos
numeros anteriores.
A segunda solução
 Essa
solução ainda não é ideal pois caso
‘n’ esteja em um valor muito alto para
verificar
os
divisores,
estaremos
calculando e armazenando na memória
desnecessariamente
uma
grande
quantidade de divisores dos numeros
anteriores.
A terceira solução

Um modo de otimizar o calculo dos divisores, seria uma
função que retorne o numero de divisores sem precisar
calcula-los e armazena-los. Pesquisando, descobrimos que
seria possivel da seguinte forma:
Exemplo: 24 tem 8 divisores, e pode ser fatorado da
seguinte maneira: 2³x3¹
Onde as bases são numeros primos, e os expoentes são o
numeros de vezes que eles ocorrem. O numero de
divisores de 24 seria então: (3+1)x(1+1)=8.
A terceira solução






primos x = [2] ++ [x|x<-[3,5..x], (divisores x) ==[1,x]]
f n a = if (div n a) <a then 0 else 1 + f (n/a) a
g n = [a,f (n,a) | a <-(primos n)]
h lista = if tail h == [] then 1 else ((tail(head h)) + 1)* h
(tail lista)
divisores4 n = h(g n)
programa triangular a = if divisores4 (triangular a) >=
500 then a else programa (triangular (a+1))
A terceira solução
A terceira solução demonstrou-se mais eficiente do que as
anteriores pois não foi necessário calcular cada divisor para
termos a quantidade deles, já que é isso que realmente
importa no problema.