For the uninitiated, Project Euler is a fantastic source of brain food. The website contains hundreds of typically mathematically-based problems, and are usually best solved by programming solutions. For this reason, PE can be a great way to learn a programming language - if you’re familiar enough with algorithms, Google is usually sufficient to fill the gaps in your code.

Because PE problems can be quite enjoyable to work out on your own, I hereby warn the reader that the following material may spoil their experience for problem 148.

This blog post is mostly an excuse to populate and test my website - however, I found this experience enlightening, and thought it was worth writing about. This PE problem was one that I had naively attempted to solve years ago with C, and revisited at the start of the year with Haskell. 148 is easy to understand, as so many PE problems are. The devil is in the details, and investigation reveals many curiousities. Rather prominently, if you transform Pascal’s triangle element-by-element into a 1 or 0 for “not divisible” or “divisible”, you will get a Sierpinski triangle. The following code illustrates this nicely:

Compile1 and run that as ./pascal_divbyn 3 27, for example:

This shows you all the elements of the first 27 rows of Pascal’s triangle that are not divisible by 3. Very cute.

The pattern is reasonably obvious from here. The powers of your prime (in this case, 3) are important; that’s where the fractal pattern repeats (is that the right terminology?). So, back to the problem - we develop a formula involving triangular numbers that easily describes all numbers divisible by 7 up to the highest power of 7 less than $10^9$. But what do you do for those rows between $7^{\lfloor\log_{7}10^{9}\rfloor}$ and $10^9$? If you tried to brute force it, you would have $10^9$ mod operations on just the last row. There must be a better way.

If you sum each of these rows and print the result (such as with the following line):

… you will get:

There’s definitely a pattern here! If you could generalise this up to an arbitrary number (say, $10^9$), then we’re done.

It turns out my mathematician friend2 knew of a very relevant theorem3. It basically boils down to taking the row number of Pascal’s triangle and converting it to base p (prime), adding 1 to each digit, and multiplying all digits. A couple of examples, returning to our prime 3; look at row 17 and 18:

$17_{10} = 122_3$ $\rightarrow 233$ $\rightarrow 18$

$18_{10} = 200_3$ $\rightarrow 311$ $\rightarrow 3$

This means row 17 of Pascal’s triangle contains 18 numbers that are not divisible by 3, and row 18 has 3 numbers.

So, you could be terrible (like me), and write some code that counts from $0$ to $10^9$, converts to base 7, increments and multiplies, such as below:

This solves 148 in about 10s on my i7-2960XM laptop. Impressive, given that we have to account for each of the $10^9$ rows.

However, as my friend2 points out, this could be simplified greatly. Take a look at $10^9$ in base 7:

If our base 7 number was actually $30000000000$, then all would need to do is calculate $T_3$4, then multiply by $28^n$, where $n$ is the number of digits after the digit in question (in this case, there are 10 following digits). The $28$ comes from $T_7$, which arises from each digit effectively contributing the sum of $1$ to $7$. Thus, if 148 posed the problem for $30000000000_7$ rows, the answer would be $T_3\times28^{10}=1777180600172544$.

However, our problem is slightly more complicated, as there are other digits. Move onto the next one:

We add our previous result to this one ($T_3\times28^{9}$), but we need to incorporate the fact that we’ve “added onto” the most significant digit. This is done by simply multiplying this digit’s contribution by all previous digits plus 1, like so:

For fun, I wrote this in Go:

This solves 148 virtually instantly. Satisfying my functional craving, Haskell:

Again, runs virtually instantly.

1. I usually compile Haskell code with something like: ghc -O2 --llvm <code.hs>

2. Thanks Dave Horsley!  2

3. Lucas’ theorem - Paper and Wikipedia article

4. $T_n$ is the $n^{th}$ triangular number