Project Euler Problem 12

Problem 12

08 March 2002

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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 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?

Answer: 76576500

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Euler {
    class Program {
        static void Main(string[] args) {
            int triangleNum = 0;
            for (int i = 1; ; i++) {
                triangleNum += i;
                int numDivisors = 0;
                for (int j = 1; j * j <= triangleNum; j++) {
                    if (triangleNum % j == 0) numDivisors += 2;
                }
                Console.WriteLine(triangleNum + " " + numDivisors);
                if (numDivisors > 500) break;
            }
            Console.ReadKey();
        }
    }
}

 

Python

 

def problem12():
    triangleNum = 0;
    i = 1
    while True:
        triangleNum += i
        numDivisors = 0
        j = 1
        while j * j <= triangleNum:
            if triangleNum % j == 0: numDivisors += 2
            j += 1       
        print triangleNum, numDivisors
        if numDivisors > 500: break
        i += 1

Go

func problem11() {

    triangleNum := 0

    for i := 1; ; i++ {

        triangleNum += i

        numDivisors := 0

        for j := 1; j*j <= triangleNum; j++ {

            if triangleNum%j == 0 {

                numDivisors += 2

            }

        }

        fmt.Println(triangleNum, numDivisors)

        if numDivisors > 500 {

            break

        }

    }

}

func main() {

    problem11()

}

C++

void problem11() {

    int triangleNum = 0;

    for (int i = 1; ; i++) {

        triangleNum += i;

        int numDivisors = 0;

        for (int j = 1; j * j <= triangleNum; j++) {

            if (triangleNum % j == 0) numDivisors += 2;

        }

        // cout << triangleNum << " " << numDivisors << endl; // slow

        printf("%d %d\n", triangleNum, numDivisors);        

        if (numDivisors > 500) break;

    }

}

Javascript

var problem12 = function() {

    var triangleNum = 0;

    for (var i = 1; ; i++) {

        triangleNum += i;

        var numDivisors = 0;

        for (var j = 1; j * j <= triangleNum; j++) {

            if (triangleNum % j == 0) numDivisors += 2;

        }

        if (numDivisors > 500) return triangleNum;

    }

}

problem12()

Clojure

; euler12
; triangle numbers 1 3 6 10 15 ...
(defn tri
  ([] (tri 1 1))
  ([s i] (cons s (lazy-seq (tri (+ s (inc i)) (inc i))))))

(defn num-factor [n]
(+ 2 (* 2 (count (filter #(zero? (mod n %)) (range 2 (Math/sqrt n)))))))

(defn num-factor* [n]
 (loop [i 2, nf 0]
   (if (<= (* i i) n)
     (if (zero? (mod n i))
       (recur (inc i) (inc nf))
       (recur (inc i) nf))
     (+ 2 (* 2 nf)))))

(defn euler12 []
 (first (drop-while #(<= (num-factor %) 500) (tri))))

(defn euler12* []
  (loop [i 1, n 1]
    (if (> (num-factor* n) 500)
      n
      (recur (inc i) (+ n (inc i))))))

(time (println (euler12)))
(time (println (euler12*)))

 

Racket

 

 

#lang racket
; euler12
(define triangle-num 0)
(let loop ((i 1))
  (set! triangle-num (+ triangle-num i))
  (define num-factor 0)
  (let loop ((j 1))
    (when (<= (* j j) triangle-num)
      (when (zero? (modulo triangle-num j)) (set! num-factor (+ num-factor 2)))
      (loop (add1 j))))
  (if (> num-factor 500)
      (displayln triangle-num)
      (loop (add1 i))))

 

Common Lisp

 

(defun problem12 () 
  (let ((triangleNum 0))
    (loop for i from 1 do
      (incf triangleNum i)
      (let ((numDivisors 0))
        (loop for j from 1
          while (<= (* j j) triangleNum) do
            (when (zerop (mod triangleNum j)) (incf numDivisors 2)))
        (when (> numDivisors 500) (return))))
    (format t "~:d~%" triangleNum)))

(defun problem12b () 
  (loop with triangleNum = 0
    for i from 1 do
    (incf triangleNum i)
    (when (>
        (loop for j from 1
          while (<= (* j j) triangleNum)
          when (zerop (mod triangleNum j))
          summing 2)
      500)
      (format t "~:d~%" triangleNum)
      (return))))
   
(problem12)
(problem12b)

 

L++

(main
  (def triangleNum 0)
  (for (def i 1) || (++ i)
    (+= triangleNum i)
    (def numDivisors 0)
    (for (def j 1) (<= (* j j) triangleNum) (++ j)
        (if (== 0 (% triangleNum j)) (+= numDivisors 2)))   
    (when (> numDivisors 500)
      (prn triangleNum " " numDivisors) (break))))

Arc

 

(def problem12 ()
  (= triangleNum 0
    i 1)
  (catch
    (while t     
      (++ triangleNum i)
      (= numDivisors 0)
      (= j 1)
      (while (<= (* j j) triangleNum)
        (when (is 0 (mod triangleNum j)) (++ numDivisors 2))
        (++ j))
      ;(prn triangleNum #\space numDivisors)
      (when (> numDivisors 500) (throw nil))
      (++ i)))
  (prn triangleNum))
   
(problem12)

 

newLISP

 

(define (problem12)
  (setf triangleNum 0
    i 1)
  (catch
    (while true     
      (++ triangleNum i)
      (setf numDivisors 0)
      (setf j 1)
      (while (<= (* j j) triangleNum)
        (when (= 0 (mod triangleNum j)) (++ numDivisors 2))
        (++ j))
      ;(println triangleNum " " numDivisors)
      (when (> numDivisors 500) (throw))
      (++ i)))
  (println triangleNum))
   
(problem12)
(exit)