Euler Problem 203 asks:

The binomial coefficients

^{n}C_{k}can be arranged in triangular form, Pascal’s triangle, like this:

123456789 11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 7 21 35 35 21 7 1.........It can be seen that the first eight rows of Pascal’s triangle contain twelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.

A positive integer n is called squarefree if no square of a prime divides n. Of the twelve distinct numbers in the first eight rows of Pascal’s triangle, all except 4 and 20 are squarefree. The sum of the distinct squarefree numbers in the first eight rows is 105.

Find the sum of the distinct squarefree numbers in the first 51 rows of Pascal’s triangle.

Each number inside Pascal’s Triangle is the sum of the two numbers above it. Pascal’s Triangle, traditionally zero-based, can be portrayed in an array, like this:

nk | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|

0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 |

3 | 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 |

4 | 1 | 4 | 6 | 4 | 1 | 0 | 0 | 0 |

5 | 1 | 5 | 10 | 10 | 5 | 1 | 0 | 0 |

6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | 0 |

7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |

In this form, each number below row(0) and right of column(0) is the sum of the number diagonally left and above with the number directly above. There is another way to determine each number, which is what Euler’s * ^{n}C_{k}* notification signifies. Where

*n*is the row, and

*k*is the column, each number is

*n!/((n-k)!*k!)*. In the problem statement, the largest

*n*is 50. Therefore the largest prime-squared we have to deal with is 49, and the largest prime is 7. We have no need to investigate higher.

Once we build the 0×50, 0×50 Pascal array, a collection is the perfect tool to collect(duh!) unique entries because you can’t have duplicates; and because of symmetry, we only need look in the left half of the array. Finally, loop through the distinct numbers checking the remainders from the divisions by 2^{2}, 3^{2}, 5^{2}, and 7^{2}. If all of them are non-zero, the distinct number is square-free, and add it to the running total to form the answer. Equivalently, as implemented, if any of them are zero, then square-free is false, and don’t add the distinct number.

This is the code that does this. It runs in about 2/100^{ths} of a second, and builds the “triangle” by addition rather than factorization.

Dim Pascal(0 To 50, 0 To 50) As Double

Dim R As Long, C As Long, N As Long, P As Long

Dim Answer As Double, T As Single

Dim DistinctNums As New Collection

Dim Item As Double, Key As String

Dim Prime(1 To 7) As Boolean, SquareFree As Boolean

Dim Max As Double

T = Timer

Pascal(0, 0) = 1

For R = 1 To 50 ‘Build the array

Pascal(R, 0) = 1

Pascal(R, R) = 1

Pascal(R, 1) = R

Pascal(R, R – 1) = R

For C = 1 To R – 1

Pascal(R, C) = Pascal(R – 1, C – 1) + Pascal(R – 1, C)

Next C

Next R

For R = 0 To 50 ‘Collect distinct numbers

For C = 0 To 25

If Pascal(R, C) 0 Then

Key = CStr(Pascal(R, C))

If Not IsIn(DistinctNums, Key) Then

Item = Pascal(R, C)

DistinctNums.Add Item:=Item, Key:=Key

If Item > Max Then Max = Item

End If

End If

Next C

Next R

Sift Sieve:=Prime

Debug.Print Max

For N = 1 To DistinctNums.Count

SquareFree = True

For P = 1 To UBound(Prime)

If Prime(P) Then

If DistinctNums(N) / (P * P) – Int(DistinctNums(N) / (P * P)) = 0 Then

SquareFree = False

Exit For

End If

End If

Next P

If SquareFree Then Answer = Answer + DistinctNums(N)

Next N

Debug.Print Answer; ” Time:”; Timer – T

End Sub

Function IsIn(Col As Collection, Key As String) As Boolean

Dim errNum As Long, TEMP As Variant

errNum = 0

Err.Clear

On Error Resume Next

TEMP = Col.Item(Key)

errNum = CLng(Err.Number)

On Error GoTo 0

If errNum = 5 Then ‘IsIn = False

Exit Function

End If

IsIn = True ‘errNums 0 , 438

End Function

Function Sift(ByRef Sieve() As Boolean) As Variant

‘Sets Sieve(n) TRUE if prime

Dim Limit As Long, BreakPT As Long

Dim N As Long, m As Long

Limit = UBound(Sieve)

BreakPT = Int(Sqr(Limit))

Sieve(1) = False

Sieve(2) = True

For N = 3 To Limit

Sieve(N) = True

If N Mod 2 = 0 Then Sieve(N) = False

Next N

For N = 3 To BreakPT Step 2

If Sieve(N) Then

For m = N * N To Limit Step 2 * N

Sieve(m) = False

Next m

End If

Next N

End Function

It’s probably overkill to use a sieve for only 4 prime numbers, but it’s a tool the tool box now. I wanted to use “distinctnum(n) mod p*p” but that throws errors for large values of distinctnum(n), so I went with definition of mod instead.

*…mrt*

Whew; math. Nice job…I think.

Use the symmetry of Pascal’s triangle (PT). If you index the 0th through 50th order rows 0..50 for rows and -50..50 for columns using the convention that even order rows use even column indices and odd order rows use odd column indices, PT(row, -col) = PT(row, col) for all row and col. You only need to fill out PT for nonnegative col.

Also, with only 4 squared primes to check, the Sieve of Eratosthenes is too much overhead.

The following runs a bit more than 10 times faster than your code, and it’s all in one procedure (which is one of the reasons it’s faster).

Dim dn As New Dictionary

Dim pt As Variant, p As Double

Dim i As Long, j As Long

ReDim pt(1 To 51) As Double

pt(1) = 1

pt(2) = 1

dn.Add Key:=1, Item:=False

‘use the symmetry of the triangle and don’t do more than necessary

For i = 2 To 50

For j = i + 1 To i 2 + 1 Step -1

pt(j) = pt(j) + pt(j – 1)

p = pt(j)

‘check if divisible by squared primes 2, 3, 5 or 7

If p / 4 – Int(p / 4) Then _

If p / 9 – Int(p / 9) Then _

If p / 25 – Int(p / 25) Then _

If p / 49 – Int(p / 49) Then _

If Not dn.Exists(p) Then dn.Add Key:=p, Item:=False

Next j

If i Mod 2 = 0 Then pt(j) = pt(j + 2)

Next i

Erase pt

pt = dn.Keys

dn.RemoveAll

For i = LBound(pt) To UBound(pt)

euler203fb = euler203fb + pt(i)

Next i

Erase pt

End Function

fzz –

Very nice. I particularly like doing the “heavy-lifting” in the dictionary keys, and having the item be a tiny boolean. That’s a neat trick, and all that’s required..

For those scoring at home, to use a dictionary object, you need to set a reference (via the Tools menu) to the Microsoft Scripting Runtime. One advantage of a dictionary over a collection is that a dictionary has an “exists” method (as fzz used). Takes the place of my IsIn(collection,key) function. Dictionaries are slower than collections, but you can’t improve on fzz’s zero seconds.

…mrtYou guys and your collections / dictionaries. It makes things so…easy. My idea was to build the triangle, add each number to a list, sort the list, and then pull out the unique values for testing. It runs in a blink, but it’s not nearly so neat and clean as fzz’s. Well done.

-Josh

fzz

I’m a ‘hit it until it works’ coder, rarely using subtleties of variable types – other than arrays. I wouldn’t, for example, think to use dictionaries or collections, though obviously it looks like I should.

So when someone ReDims something other than an array it confuses me. Can you shed light on the internals of:

Dim pt As Variant

ReDim pt(1 To 51) As Double

gruff999