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:
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 :
- 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 - firstname.lastname@example.org 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 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