Euler Problem 203

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.

Sub Problem_203()
   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

Posted in Uncategorized

5 thoughts on “Euler Problem 203

  1. 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).

    Function euler203fb()
      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

  2. 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

  3. 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

  4. 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

Leave a Reply

Your email address will not be published. Required fields are marked *