Project Euler - Problem 12

As a 2 years researcher, I feel a bit rusty to code.  I search a good set of execises to hone my abilities again and I stumbled upon Project Euler. This site hosts increasing number of very well formed algorithmic problems and discussions. It ranges very basic problems to very high level ones, requiring profound knowledge and practice.

After that intro. I want to introduce one of the example question from Project Euler. NOTE THAT, IF YOU ALREADY KNOW THE SITE AND YOU TRY TO SOLVE THAT PROBLEM, DO NOT CHEAT YOURSELF.

Here is the problem statement we try to solve.

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?

Here what I propose as a solution. It is decomposed into those basic parts .

  • Find number of divisors of given number  --  main idea here is to use the following fact http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
  • Find kth triangle number via : k*(k+1) / 2 --  this is just the simple formulation to find the sum of first k numbers http://cseweb.ucsd.edu/groups/tatami/kumo/exs/sum/
  • Finding set of N prime numbers or extend the given prime set -- this set would be useful to find the divisors. Instead of trying each number, we now that each distinct divisor of the given number must be the exponent of one of the unique prime number. Therefore we just iterate on the primes' set as dividing the number into smaller quotient if the next prime is a exact divisor. ( look at the below code for better intuition )
  • Check whether the given number is prime or not -- this is a sub-step to create the set of N prime numbers. For efficient check we just use the numbers that are less than the square of the candidate number. If in that interval, one of the number divides exactly the candidate it is raised as non-prime. Otherwise it is known to be prime.

'''
Eren Golge - erengolge@gmail.com
Solution to Project Euler Problem 12
'''

import math
import operator

def find_sum(n):
	return n*(n+1)/2

def find_num_divisor(num,primes):
	'''
	Find number of divisors of the given number

	Iterate over each prime number and count its exponent as it is able
	to divide the remaining quotient. Add one to each prime's exponent
	and multiply them at the end. Refer to
	http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
	'''
	next_prime = primes[0]
	num_divisor = 1
	prime_count = 1
	while next_prime <= num:
		exponent = 0
		while num % next_prime == 0:
			num /= next_prime
			exponent += 1
		exponent += 1
		num_divisor *= exponent
		next_prime = primes[prime_count]
		prime_count += 1
	return  num_divisor

def return_n_primes(n, primes = None):
	'''
	Merge the set of n prime numbers or extend the given primes' set

	Input:
		n - number of prime numbers
		primes - list of prime numbers that are already curated. If it is
		None start from scratch

	Output:
		primes - set of n prime numbers
	'''

	if primes == None:
		counter = 0
		cur_val = 2
		primes  = []
	else:
		cur_val = primes[-1]
		counter = len(primes)
	while counter < n:
		if check_prime(cur_val):
			primes.append(cur_val)
			counter += 1
		cur_val += 1
	return primes

def check_prime(num):
	'''
	Check whether the given number is prime or not

	Iterate over all the values in the interval [2, sqrt(num)], if no
	exact divisor is found then raise the number as prime.
	'''
	if num == 1:
		return False
	check_val =  int(math.floor(math.sqrt(num)))
	for i in range(check_val,1,-1):
		if num % i == 0:
			return False
	return True

if  __name__ == '__main__':
	LIM = 500
	num_divisors = 0
	primes = return_n_primes(500)
	next_tri_val = 1
	while num_divisors < LIM:
		# find the next triangle number
		tri_val = find_sum(next_tri_val)
		try:
			# find number of divisors, if primes' set is short than extend it
			num_divisors = find_num_divisor(tri_val,primes)
			next_tri_val += 1
		except:
			# if primes list is not enough extend it
			return_n_primes(len(primes)+100,primes)
		print 'num divisors ', num_divisors
	print tri_val

Share