Project Euler

As part of my year of focus, I’ve been trying to spend more consistent chunks of time working on programming. In particular, right now I’m focusing on doubling down on my Python knowledge, and exploring some other aspects of computer science that interest me. After checking out a few books and tutorials, I’ve made my way back to a website that I found a number of years ago, which is the most intriguing to me: Project Euler.

The gist of Project Euler is to give a wide range of mathematically-oriented programming puzzles for people to solve. You can always just go on there for ideas of small programs to write, whether it’s to learn some math or to try out a new computer language. In my case, I’m trying to write the most efficient programs possible, making use both of clever algorithms I spend time figuring out or researching, and making use of Python syntax to make particularly elegant solutions. If you make a simple account, you can keep track of your progress and access message boards about each problem.

It has been very engaging so far. They are more bite-sized, but give ideas for more complex programs that can be written which are more general purpose. Rather than writing a script that solves a problem, I can focus on writing broad functions that may be helpful.

A fun problem I worked on today involved triangular numbers. These are just numbers you get from adding together all the positive integers before it. So, the seventh triangular number is just 1+2+3+4+5+6+7=28.

The goal was to find the smallest triangular number with more than 500 divisors. Here’s the Python code I wrote for it. (I apologize, I can’t figure out how to make syntax highlighting work right now.


import math

def getTriangular(n): ## Generates a list of triangular numbers up to n
    triangularList = [sum(i for i in range(1,k+1)) for k in range(1, n+1)]
    return triangularList

def getNumberDivisors(n):  ## Generates number of divisors
    numDivisors = 2  ## We don't care about n=1, so assume it has 1 and n
    for divisor in range(2,int(math.sqrt(n))+1): ## Only check to sqrt(n)
        if n % divisor == 0:  ## Needs to be a divisor
            if divisor * divisor == n: ## If square root
                numDivisors += 1
            else:
                numDivisors += 2  ## Otherwise, divisor has a factor
                                  ## pair larger than n//2

    return numDivisors


def main():
    triangleList = getTriangular(25000) ## Hopefully big enough
    is500 = False
    triangleIndex = 7 ## It's certainly larger than seventh number
    while not is500:
        triangleIndex += 1
        #print(triangleIndex)
        if getNumberDivisors(triangleList[triangleIndex]) > 500:
            is500 = True
            print(triangleList[triangleIndex]) ## Tell me the number

main()

The code runs reasonably quickly, which is always the goal. The standard view on Project Euler problems (and I believe it is their official stance) is that well-optimized solutions should run for no longer than a minute on nearly any computer. The first few problems should take substantially less time than that.

I recommend giving them a try if you have an itch for some challenges, and either want to work on optimizing your code in a certain language, or try out the functions in a new language. For example, the fact that Python supports arbitrarily large integer addition (compared to C or Java) makes some problems pretty trivial. Thinking about how to deal with other languages becomes rather interesting.

Leave a Reply