My Secret Addiction: Project Euler Problems

BLUF (Bottom Line Up Front): This is a personal post how I become involved with programming and my continued interest in solving mathy programming problems.

I used to believe that programming was just beyond my abilities. I thought that only the hacker type that discovered programming books when they were 10 and had few other distractions could really do it, and that it was beyond the reach of most ordinary people, including me.

As a Plebe (freshman) at West Point, I had to take an introduction to information technology course based around Jython (Python on JVM). The course material was surprisingly confusing to me for a while (it didn’t help that we had a terrible REPL which didn’t color code language syntax versus permissible variable names and that we used a lot of obscure functions for picture editing).

I was over halfway through the course when I somehow discovered ProjectEuler.net and a better REPL. I ended up programming for nearly all of my free time for nearly 2 weeks straight and realized that I actually did have a knack for programming. I decided to transfer from being an operations research major to being a computer science major, which I was and still am excited about.

Anyways, I still spend some of my free time programming these Project Euler problems because they are so damn fun and a tractable way to improve my still basic programming skills. I lost all my computer files last semester, so below is the Project Euler problems that I have solved since then:

A Counterintuitive Probability Game

I read an interesting math paper by Thomas Cover that I struggled to believe at first. I recommend you read it before continuing reading this post (it’s short). Thus, I decided to test out the claim using Python.

The results hold. When the range that the third random number, C, falls in is the same as the range which the other two numbers may be selected from, the win rate is 66%. When C is a fixed number equally between the upper and lower limit of what the other two numbers may be, the win rate is 75%.

Thus, the benefit of using a wide range of C on the Real number line is to ensure that you are at least sometimes choosing a value in between the ranges in which the other play is selecting numbers from (they don’t have to choose anywhere around 0). If your C is never between their two numbers, your probability of winning is indeed 1/2.

Primality Testing, Factorization, and Sieving Implementation

Prime testing, factorization, and sieving algorithms in Javascript.

I figured that for my daily post today, I would learn Javascript and figure out how to make this website more interactive. I decided to write primality testing and prime factorization scripts and include them below:

Update: I've included a prime sieving script. Additionally, these only work for integers from 2 to 2^53.

Test if a number is prime:

Factor a number into its prime components:

Calculate all prime numbers under n:

These algorithms are only moderately faster over the most naive implementations. There are much faster algorithms out there!