06.14.08

Project Euler: Problem 12

Posted in python tagged , , at 4:08 pm by redochre

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?

A solution:
Below, the function prime_factors is given here.

from factor import prime_factors
from operator import mul

triangle_num = 3 # starting place: 1+2=3
max_factors = 2
to_add = 2

while max_factors <= 500:
    to_add += 1
    triangle_num += to_add
    factors = prime_factors(triangle_num)
    count = []
    while len(factors) != 0:
        count.append(factors.count(factors[0])) # how many of the first factor
        del factors[:count[-1]] # take out all instances of first factor
    # count is now a list of how many of each factor
    # e.g. for 28 = 2*2*7, count = [2,1]
    # number of all factors is then given by (2+1)*(1+1) because each factor
    # will have the form (2**x)*(7**y) where x = 0 or 1 or 2, y = 0 or 1
    not_just_prime_factors = reduce(mul, [count[i]+1
                                          for i in range(len(count))])
    max_factors = max(not_just_prime_factors, max_factors)

print triangle_num
print max_factors

3 Comments »

  1. Chris said,

    15 July, 2008 at 1:41 pm

    Beautiful solution. I’ve been struggling with this one for a while. The main limiting factor in my solution is determining the number of factors for each triangle number. I came up with a somewhat efficient solution:

    	d = set([1,n])
	ps = primes(n) # gets a list of primes up to n using Sieve of Eratosthenes
	for p in ps:
		result, remainder = divmod(n,p)
		if remainder == 0:
			d.add(p)
			d.add(result)
	return sorted(d)

    Basically, for every prime up to n, if that prime is a divisor of n, add it and n/prime to the set of divisors. Quite fast for small n, but, well, what isn’t :)
    I don’t quite understand the (2 + 1) * (1 + 1) part of your algorithm, and it is quite clear that it is the key to solving this puzzle. I’d love to see the math behind that explained in more detail.
    Again, great solution.

  2. Luke said,

    16 July, 2008 at 8:56 am

    I think there’s a problem with your method chris.

    Let n = 16
    2 is a divisor of n, add 2 and 8 to the list of divisors
    3, 5, 7, 11, 13 don’t divide evenly into 16. But what about 4? 4 is not prime nor does 4 times a prime equal 16 so it will not be added to the list of divisors.

    Please reply by email as I don’t check this website often.

  3. Craig Campbell said,

    20 July, 2008 at 3:48 pm

    this is the best factorization algorithm i have made to date…
    i solved 12 in ~18 seconds.
    hope you like it. :)
    def factorize(n): #returns list of all the factors in “n”
    div_n=[1]; max = n; i = 2
    while i <= max:
    if n % i == 0:div_n.append(i);div_n.append(n/i) #if n is divisible then append n and result
    if n%2==0:i+=1
    else: i+=2
    max=int((n/i)+1)
    return div_n


Leave a Comment