/*

  Problem 12
  """
  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:

       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

  We can see that the 7th triangle number, 28, is the first triangle number to have 
  over five divisors.

  Which is the first triangle number to have over five-hundred divisors?)
  """

  This Pop-11 program was created by Hakan Kjellerstrand (hakank@gmail.com).
  See also my Pop-11 / Poplog page: http://www.hakank.org/poplog/

*/
compile('/home/hakank/Poplib/init.p');

define sumlist(list) -> res;
   applist(0, list, nonop + ) -> res;
enddefine;

define prodlist(list) -> res;
   applist(1, list, nonop * ) -> res;
enddefine;

define sumlist2(list)->res;
    lvars i;
    lvars sum = 0;
    for i in list do
        sum+i->sum;
    endfor;
enddefine;

;;; This version is faster
define triangle_number(n)->sum;
    lvars i;
    lvars sum=0;
    for i from 1 to n do 
        sum+i->sum;
    endfor

enddefine;

;;; slower
define triangle_number2(n)->sum;
    lvars i;
    sumlist([%for i from 1 to n do i endfor%])
enddefine;


define num_divisors2(n);
    lvars s = 0;
    lvars i;
    for i from 1 to round(sqrt(n)) do
        if n mod i = 0 then
            s + 1 -> s;
        endif;
    endfor;
    return(s);
enddefine;

;;;
;;; Calculate the factors and their exponents for number n
;;;
define factorsHash(n);
    lvars hash = newmapping([], 100, 0, true);
    
    lvars m=n;
    while m mod 2 = 0 do
        hash(2)+1->hash(2);    
        m div 2->m;
    endwhile;
    
    lvars t = 3;
    while m > 1 and t < ceiling(sqrt(m)) do
        while m mod t = 0 do
            hash(t)+1->hash(t);  
            m div t -> m;
        endwhile;
        t+2->t;
    endwhile;
    if m > 1 then
        hash(m)+1->hash(m);
    endif;
    hash;
enddefine;

;;;
;;; 1.8s
;;;
define problem12();

    lvars i = 0;
    lvars len = 0;
    lvars tnum = 0;
    while 2*len <= 500 do
        ;;;triangle_number(i) -> tnum;
        tnum+i->tnum;
        num_divisors2(tnum) -> len;
        i + 1 -> i;
    endwhile;
    tnum =>
enddefine;

;;;
;;; 0.20s
;;;
define problem12b();

    lvars i = 0;
    lvars len = 0;
    lvars tnum = 0;
    lvars v, tmp;
    while len <= 500 do
        i + 1 -> i;        
        tnum+i->tnum;
        0->len;
        ;;; the length is the products of the (exponents+1)
        prodlist([% for v in [%explode(factorsHash(tnum))%] do v(2)+1 endfor%])->len;
    endwhile;
    tnum =>
enddefine;


;;; 'problem12()'=>
;;; problem12();
;;; timediff()=>;

'problem12b()'=>
problem12b();
timediff()=>;