Euler Problem 203 asks:
The binomial coefficients nCk can be arranged in triangular form, Pascal’s triangle, like this:
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 nCk 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 22, 32, 52, and 72. 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/100ths 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.
…mrt
You 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