Euler Solution 12

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 12

What is the first triangle number (1,3,6,10,15...) to have over 500 divisors?

Haskell by SanguineV

Runtime: 12.479 seconds

{- Generate an endless list of pairs, the index of the triangular number and
 - the value of the triangular number.
 - Note: starts from (0,0) which is not a real triangular number! -}
triangles :: [(Integer, Integer)]
triangles = (0,0):tris
  where
    tris = zipWith (\(x1,x2) y -> (y,x2 + y)) triangles [1..]

{- The "fun" bit, from the inside out it works as follows:
 - 1. Take the triangular number and create a list of integers up to the square
 -    root of the number.
 - 2. Only keep numbers in the list that are proper divisors of the triangular 
 -    number.
 - 3. Take this construct and discard it if it has less than 251 divisors (i.e.
 -    maximum 500 proper divisors.
 - 4. Take the first element of this list.
 - 5. Success... print the result (index, triangular number,[divisors])
 - NOTE: solution broken onto multiple lines for clarity, needs to be on a single
 - line to compile!
 -}
main = print (head 
    (filter (\(n,v,ds) -> length ds > 250)
      (map (\(n,v) -> (n,v,filter (\x -> v `mod` x == 0) [1 .. floor(sqrt (fromIntegral v))]))
       triangles)))

Python by Althalus

Runtime: 141 Seconds

from math import sqrt
import time
start_time = time.time()

answer = 0
triangle=0
next = 1

while answer == 0:
	#get the next triangle number in the sequence.
	triangle = triangle+next
	next = next+1
	#Get divisors
	i=1
	divisors = 0
	while i <= sqrt(triangle) and divisors <= 250:
		if triangle%i == 0:
			divisors = divisors+1
		i=i+1
	if divisors >=250:
		answer = 1
print(divisors)
print(triangle)
run_time = time.time() - start_time
print (run_time)
Personal tools