Excel - gregorymorrison/euler1 GitHub Wiki

Even though I use Excel heavily, I've never used its formulas much beyond the basic - I'm simply more comfortable in a more formal programming environment. I knew there were basic operations, but this Euler exercise brings up an interesting question - just how Turing-complete are Excel formulas?

Apparently a lot more than I expected. With the addition of Array Formulas, Excel functions can both accept arrays as arguments and return arrays. Thus, Excel supports the canonical Map, Filter, and Fold - tres bien! Witness:

In this example of Map, ROW() returns the array [1:10] to the function n*2, and the whole returns the array [2,4, ... 18,20]:

=ROW(1:10) * 2

In this example of Filter, ROW() returns the array [1:10] to the function IF(), and the whole returns the array [2,4,6,8,10]:

=IF(MOD(ROW(1:10),2)=0,ROW(1:10),"")

And in this example of Fold, we'll use the built-in SUM(), which returns 55 when we pass it the array [1:10]:

=SUM(ROW(1:10))

Array functions must be entered in using Shift-Ctrl-Enter, which is probably why I never stumbled upon them over all these years.

So, combining these gives us the following Euler1 using Excel's built-in functions. Or does it? It doesn't seem to work - it returns the incorrect result 499,500:

=SUM( IF(OR(MOD(ROW(1:999),3)=0, MOD(ROW(1:999),5)=0), ROW(1:999), FALSE) )

What's going on here? The following works as expected, returning 166,833:

=SUM( IF(MOD(ROW(1:999),3)=0, ROW(1:999), FALSE) )

I haven't been able to figure this out. It seems that OR(MOD3, MOD5) returns true for all elements in the set. I'm ready to chalk this up to a bug in Excel. Damnit, and I was all ready to go wield some Excel-fu.

Okay, but can we actually get a solution using Excel's formulas? Sure, if we use a different algorithm that doesn't require looping; here is one that uses Carl Freidrich Gauss's summation technique. I won't bother breaking it down - it's complicated. Paste this formula in cell A1, then enter in a number in B1 (in this case 999) and get your solution:

= (3*((FLOOR(A2/3,1)^2+FLOOR(A2/3,1))/2)) + (5*((FLOOR(A2/5,1)^2+FLOOR(A2/5,1))/2))
   - (15*((FLOOR(A2/15,1)^2+FLOOR(A2/15,1))/2))

Update: a kind reader got this to work for me! Apparently the above code doesn't work because OR returns TRUE if any element of the array is true. The following modification works because attempting to add together two booleans forces Excel to cast TRUE to 1 and FALSE to 0:

=SUM( IF((MOD(ROW(1:999),3)=0)+(MOD(ROW(1:999),5)=0), ROW(1:999), FALSE) )