problem_12.go

package projecteuler

/*
  http://projecteuler.net/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 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?
*/

const PROB12_TARGET = 500

func TriangleNumbers() chan int64 {
	c := make(chan int64)

	go func() {
		t := int64(1)
		i := int64(1)
		for {
			c <- t
			i++
			t += i
		}
	}()

	return c
}

func NumDivisors(n int64) int {
	// Short-circuit special case '1'.
	if n == 1 {
		return 1
	}

	upper := n
	divisors := 2
	for lower := int64(2); lower < upper; lower++ {
		if n%lower == 0 {
			upper = n / lower
			if upper == lower { // Perfect square
				divisors += 1
			} else {
				divisors += 2
			}
		}
	}

	return divisors
}

func FirstToHaveNumDivisors(target int) (int64, bool) {
	for t := range TriangleNumbers() {
		divisors := NumDivisors(t)
		if divisors > target {
			return t, true
		}
	}

	return 0, false
}

func Problem12() (int64, bool) {
	return FirstToHaveNumDivisors(PROB12_TARGET)
}