17 de noviembre de 2013

Highly divisible triangular number - Project Euler, problema 12

El problema de hoy requiere contar los divisores de números triangulares. Una vez que uno tiene una función para contar divisores y una fórmula para el n-ésimo número triangular es solo cuestión de hacer un ciclo hasta que que encontremos un número que cumpla con los requisitos del problema:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
 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
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
La teoría detrás de la función d, que cuenta los divisores de un entero dado, está en el link que puse en los comentarios del código, y en cuanto a la función del n-ésimo número triangular solo se trata de una fórmula muy conocida de la súma de los primeros n enteros positivos: $\frac{n(n+1)}{2}$.

Aquí el código:

%número de divisores
function r=d(n)
%Usé esto
%http://mathschallenge.net/library/number/number_of_divisors
%con la esperanza de que fuera mas eficiente que la "fuerza bruta" xDÇ
 f=factor(n);
 k=f(1);
 r=1;
 c=1;
 for i=2:length(f)
  if f(i)!=k
   r*=c+1;  
   c=0;
   k=f(i);
  end 
  c+=1;
 end
 r*=c+1;
end

%n-ésimo número triangular
function t=T(n)
 t=n*(n+1)*0.5;
end

m=500;
i=1; 
%cuenta los divisores de cada número triangular hasta que
%deja de ser menor que m
while d(T(i))<m
 i+=1;
end
T(i)