Euler Problem 43

Euler Problem 43 asks:

‘The number, 1406357289, is a 0 to 9 pandigital number because it
‘is made up of each of the digits 0 to 9 in some order, but it also
‘has a rather interesting sub-string divisibility property.

‘Let d_(1) be the 1st digit, d_(2) be the 2nd digit, and so on.
‘In this way, we note the following:

‘    * d_(2)d_(3)d_(4)=406 is divisible by 2
‘    * d_(3)d_(4)d_(5)=063 is divisible by 3
‘    * d_(4)d_(5)d_(6)=635 is divisible by 5
‘    * d_(5)d_(6)d_(7)=357 is divisible by 7
‘    * d_(6)d_(7)d_(8)=572 is divisible by 11
‘    * d_(7)d_(8)d_(9)=728 is divisible by 13
‘    * d_(8)d_(9)d_(10)=289 is divisible by 17

‘Find the sum of all 0 to 9 pandigital numbers with this property.

This problem, over the course of a week, gave me fits. The smallest 0-to-9 pandigital number is 1023456789. The largest is 9876543210. To check every number between them loops 8 billion, 853 million+ times. That’s not doable in “Euler time” of under one minute on a reasonable computer. That’s the “brutest” of brute force approaches, and I knew it was wrong. By inspecting the example case, swapping the 1 and 4 does not change the modulo 2 computation, and swapping the 0 and 6 does not affect the modulo 2 or 3 computations. So, there’s 4 answers there. Turns out there are two more.

It wasn’t until I looked at the problem from inside out that I came up with an approach. The 10th digit has to be whatever is left. The 9th digit has to be whatever is not used in the first 8, and the 8th digit has to be whatever is not used in the first 7, etc. This gave me 10 loops. The following code runs in 20.5 seconds on my MacBookPro running Excel 2002 under Parallels.

Sub Problem_043()
 
   Dim T       As Single
   Dim Answer  As Variant
   Dim d234    As String
   Dim d345    As String
   Dim d456    As String
   Dim d567    As String
   Dim d678    As String
   Dim d789    As String
   Dim d890    As String
   Dim TEMP    As String
   Dim L10     As Long
   Dim L09     As Long
   Dim L08     As Long
   Dim L07     As Long
   Dim L06     As Long
   Dim L05     As Long
   Dim L04     As Long
   Dim L03     As Long
   Dim L02     As Long
   Dim L01     As Long
 
   T = Timer
   For L01 = 1 To 9
      For L02 = 0 To 9
         Select Case L02
            Case L01: GoTo Next_L02
         End Select
         For L03 = 0 To 9
            Select Case L03
               Case L01, L02: GoTo Next_L03
            End Select
            For L04 = 0 To 9
               Select Case L04
                  Case L01, L02, L03: GoTo Next_L04
               End Select
               For L05 = 0 To 9
                  Select Case L05
                     Case L01, L02, L03, L04: GoTo Next_L05
                  End Select
                  For L06 = 0 To 9
                     Select Case L06
                        Case L01, L02, L03, L04, L05: GoTo Next_L06
                     End Select
                     For L07 = 0 To 9
                        Select Case L07
                           Case L01, L02, L03, L04, L05, L06: GoTo Next_L07
                        End Select
                        For L08 = 0 To 9
                           Select Case L08
                              Case L01, L02, L03, L04, L05, L06, L07: GoTo Next_L08
                           End Select
                           For L09 = 0 To 9
                              Select Case L09
                                 Case L01, L02, L03, L04, L05, L06, L07, L08: GoTo Next_L09
                              End Select
                              For L10 = 0 To 9
                                 Select Case L10
                                    Case L01, L02, L03, L04, L05, L06, L07, L08, L09: GoTo Next_L10
                                 End Select
                                 TEMP = L01 & L02 & L03 & L04 & L05 & L06 & L07 & L08 & L09 & L10
                                 d234 = Mid(TEMP, 2, 3)
                                 If CLng(d234) Mod 2 = 0 Then
                                    d345 = Mid(TEMP, 3, 3)
                                    If CLng(d345) Mod 3 = 0 Then
                                       d456 = Mid(TEMP, 4, 3)
                                       If CLng(d456) Mod 5 = 0 Then
                                          d567 = Mid(TEMP, 5, 3)
                                          If CLng(d567) Mod 7 = 0 Then
                                             d678 = Mid(TEMP, 6, 3)
                                             If CLng(d678) Mod 11 = 0 Then
                                                d789 = Mid(TEMP, 7, 3)
                                                If CLng(d789) Mod 13 = 0 Then
                                                   d890 = Mid(TEMP, 8, 3)
                                                   If CLng(d890) Mod 17 = 0 Then
                                                      Answer = CDec(Answer) + CDec(TEMP)
                                                   End If
                                                End If
                                             End If
                                          End If
                                       End If
                                    End If
                                 End If
Next_L10:
                              Next L10
Next_L09:
                           Next L09
Next_L08:
                        Next L08
Next_L07:
                     Next L07
Next_L06:
                  Next L06
Next_L05:
               Next L05
Next_L04:
            Next L04
Next_L03:
         Next L03
Next_L02:
      Next L02
   Next L01
 
   Debug.Print Answer; ”  Time:”; Timer – T
 
End Sub

Loop L01 only has to go from 1 to 9, since there are no leading zeros. The other 9 loops are from 0 to 9. I thank Steve Bullen for writing the Smart Indenter. There nothing above that speaks elegance to me. Looks brutish in it’s own right. I couldn’t noodle out any special significance to the modulo divisors being the first 7 primes.

…mrt

Posted in Uncategorized

12 thoughts on “Euler Problem 43

  1. I actually ran through all the numbers, but I checked the divisors first and the pandigital property second. It ran nearly 4x faster than the code above, I suspect because
    (a) checking divisors is quicker than checking pandigitality
    (b) doing up to 44 Select Case tests per number slows you down. Instead, I set up an empty array of 10 items, and for each digit of the number, I set the array element to 1 for that digit. If the array element was already 1, then it was a duplicate digit, ie not pandigital.

  2. dbb – Your comment suggested a combined approach. This one runs in 78ms. Thanks.

    Sub Problem_043B()
     
       Dim T       As Single
       Dim Answer  As Variant
       Dim d234 As String, d345 As String, d456 As String, d567 As String
       Dim d678 As String, d789 As String, d890 As String
       Dim TEMP    As String
       Dim L10 As Long, L09 As Long, L08 As Long, L07 As Long, L06 As Long
       Dim L05 As Long, L04 As Long, L03 As Long, L02 As Long, L01 As Long
       Dim n       As Long
     
       T = Timer
       For L01 = 1 To 9
          For L02 = 0 To 9
             Select Case L02
                Case L01: GoTo Next_L02
             End Select
             For L03 = 0 To 9
                Select Case L03
                   Case L01, L02: GoTo Next_L03
                End Select
                For L04 = 0 To 9
                   Select Case L04
                      Case L01, L02, L03: GoTo Next_L04
                      Case Else
                         d234 = L02 & L03 & L04
                         If CLng(d234) Mod 2  0 Then GoTo Next_L04
                   End Select
                   For L05 = 0 To 9
                      Select Case L05
                         Case L01, L02, L03, L04: GoTo Next_L05
                         Case Else
                            d345 = L03 & L04 & L05
                            If CLng(d345) Mod 3  0 Then GoTo Next_L05
                      End Select
                      For L06 = 0 To 9
                         Select Case L06
                            Case L01, L02, L03, L04, L05: GoTo Next_L06
                            Case Else
                               d456 = L04 & L05 & L06
                               If CLng(d456) Mod 5  0 Then GoTo Next_L06
                         End Select
                         For L07 = 0 To 9
                            Select Case L07
                               Case L01, L02, L03, L04, L05, L06: GoTo Next_L07
                               Case Else
                                  d567 = L05 & L06 & L07
                                  If CLng(d567) Mod 7  0 Then GoTo Next_L07
                            End Select
                            For L08 = 0 To 9
                               Select Case L08
                                  Case L01, L02, L03, L04, L05, L06, L07: GoTo Next_L08
                                  Case Else
                                     d678 = L06 & L07 & L08
                                     If CLng(d678) Mod 11  0 Then GoTo Next_L08
                               End Select
                               For L09 = 0 To 9
                                  Select Case L09
                                     Case L01, L02, L03, L04, L05, L06, L07, L08: GoTo Next_L09
                                     Case Else
                                        d789 = L07 & L08 & L09
                                        If CLng(d789) Mod 13  0 Then GoTo Next_L09
                                  End Select
                                  For L10 = 0 To 9
                                     Select Case L10
                                        Case L01, L02, L03, L04, L05, L06, L07, L08, L09: GoTo Next_L10
                                        Case Else
                                           d890 = L08 & L09 & L10
                                           If CLng(d890) Mod 17  0 Then GoTo Next_L10
                                     End Select
                                     TEMP = L01 & L02 & L03 & L04 & L05 & L06 & L07 & L08 & L09 & L10
                                     Answer = CDec(Answer) + CDec(TEMP)
                                     n = n + 1
    Next_L10:
                                  Next L10
    Next_L09:
                               Next L09
    Next_L08:
                            Next L08
    Next_L07:
                         Next L07
    Next_L06:
                      Next L06
    Next_L05:
                   Next L05
    Next_L04:
                Next L04
    Next_L03:
             Next L03
    Next_L02:
          Next L02
       Next L01
     
       Debug.Print Answer; ”  Time:”; Timer – T; n
     
    End Sub

    …mrt

  3. Hi Mike –

    Out of the 123 posted answers, only a few are recursive. A quick scan shows Python examples, and Mathematica examples, and some flavors of C. And I can’t read any of them ;-) My C is long atrophied away.

    …mrt

  4. I really liked this problem. My approach was to build the 10 digit numbers 3 digits at a time, starting with the multiples of 17. There are only 58 of these. As the prime factor goes from 17 to 2, the number of possible three digit multiple increases greatly. The key is to match the last two digits of the second set to the first two digits of the first set. For example: 728 + 289 = 7289.

    If you match the results by digit at each step and check for the pandigital property along the way, there are very few eligible results at each iteration:

    count: 27 of strings len: 4
    count: 19 of strings len: 5
    count: 14 of strings len: 6
    count: 8 of strings len: 7
    count: 4 of strings len: 8
    count: 6 of strings len: 9
    Answer: xxxxxxxxxxx | Time: 0.03125

    Looking at it again, I think this approach might have been even faster if I skipped every other prime factor. That way would have built strings of len 3, 5, 7, and 9 and matched the results by 1 digit instead of 2. Still, very few calculations, very fast.

  5. Jonah’s approach makes a lot of sense – eliminate unnecessary iterations.

    It can be supplemented by the dreaded MATHEMATICS.

    Divisibility of d(4..6) by 5 requires that d(6) could only be 0 or 5. Now d(6..8) must be divisible by 11, but d(6) can only be 0 or 5. If d(6) were 0, meaning d(6..8) falls between 11 and 99, all of these use two instances of the same numeral (even 090), which is inconsistent with the problem constraints, so d(6) MUST ONLY BE 5. Which means that d(6..8) can only be multiples of 11 between 501 and 598.

    Next, d(7..9) can’t contain the numeral 5, but must contain d(7..8) in common with d(6..8) between 501 and 598 divisible by 11. Meaning for each of the possible 5d(7..8) numbers, it’s only necessary to check 7 possible d(9) numerals each for d(7..8) base to find a multiple of 13, and since 13 > 10, there can only ever be zero or one such multiple of 13. Repeat that process for d(8..9) as base for varying d(10) for multiples of 17, and again for each base there can only ever be zero or one such multiple of 17. You wind up with a small number of possible sequences of last 5 numerals.

    At this point it’s easy enough to iterate through the remaining five digits to determine d(5) so that d(5..7) is divisible by 7. Figuring out d(4) is simple: d(2..4) must be even, so d(4) must be even, so d(4) can be any even numeral not appearing in d(5..10). Figuring out d(3) is almost as simple: d(3..5) must be divisible by 3, so d(3)+d(4)+d(5) must be divisible by 3, and since d(4) and d(5) are known, mod(d(4)+d(5),3) is known, so d(3) can be any remaining numeral with the complementary remainder when divided by 3 from the numerals not in d(4..10). Finally, both permutations of the remaining two numerals satisfy the problem constraints.

    This is a paper & pencil problem.

  6. I had to see how the VBA would look. The following requires a VBA project reference to the Windows Scripting Runtime.

    Sub foo()
      Dim d As New Dictionary, v As Variant
      Dim j As Long, k As Long
      Dim s As String, t As String
      Dim dt As Double

      dt = Timer

      ‘find multiples of 11
     For k = 506 To 594 Step 11
        s = Format(k)
        If InStr(2, s, Left$(s, 1)) + InStr(3, s, Mid$(s, 2, 1)) = 0 Then
          t = “0123456789”
          For j = 1 To 3
            t = Replace(t, Mid$(s, j, 1), “”)
          Next j
          d.Add Key:=s, Item:=t
        End If
      Next k

      ‘find multiples of 13
     For Each v In d.Keys
        t = d(v)
        k = CLng(Right$(v, 2) & “0”)
        For j = 1 To 7
          s = Mid$(t, j, 1)
          If (k + CLng(s)) Mod 13 = 0 Then
            d.Add Key:=v & s, Item:=Replace(t, s, “”)
            Exit For
          End If
        Next j
        d.Remove Key:=v
      Next v

      ‘find multiples of 17
     For Each v In d.Keys
        t = d(v)
        k = CLng(Right$(v, 2) & “0”)
        For j = 1 To 6
          s = Mid$(t, j, 1)
          If (k + CLng(s)) Mod 17 = 0 Then
            d.Add Key:=v & s, Item:=Replace(t, s, “”)
            Exit For
          End If
        Next j
        d.Remove Key:=v
      Next v

      ‘find multiples of 7
     For Each v In d.Keys
        t = d(v)
        k = CLng(Left$(v, 2))
        For j = 1 To 5
          s = Mid$(t, j, 1)
          If (k + 100 * CLng(s)) Mod 7 = 0 Then
            d.Add Key:=s & v, Item:=Replace(t, s, “”)
          End If
        Next j
        d.Remove Key:=v
      Next v

      ‘find multiples of 2
     For Each v In d.Keys
        t = d(v)
        For j = 1 To 4
          s = Mid$(t, j, 1)
          If CLng(s) Mod 2 = 0 Then
            d.Add Key:=s & v, Item:=Replace(t, s, “”)
          End If
        Next j
        d.Remove Key:=v
      Next v

      ‘find multiples of 3
     For Each v In d.Keys
        t = d(v)
        k = CLng(Left$(v, 2))
        For j = 1 To 3
          s = Mid$(t, j, 1)
          If (k + 100 * CLng(s)) Mod 3 = 0 Then
            d.Add Key:=s & v, Item:=Replace(t, s, “”)
          End If
        Next j
        d.Remove Key:=v
      Next v

      ‘permute remaining numerals
     For Each v In d.Keys
        t = d(v)
        d.Add Key:=t & v, Item:=“”
        d.Add Key:=Right$(t, 1) & Left$(t, 1) & v, Item:=“”
        d.Remove Key:=v
      Next v

      Debug.Print d.Count; Timer – dt

      d.RemoveAll
      Set d = Nothing
    End Sub

    I won’t spoil the problem by listing the results, but this procedure’s runtime averages less than 1E-03, so less than a millisecond.

  7. I really want to know,how do you make your vb code look so nice,i use livewriter write my own bolg,but it does not support writing code.thank you!

  8. First: determine the last three digits of the string: numbers between 16 and 1000 divisible by 17 consisting of unique digits. Put those numbers in a string (c0), where numbers are separated by pipelines (|).
    Second: split the string c0 in a matrix (sq)
    Third: add 1 number to the left of the each string and determine whether the new number and first 2 digits of the string can be divided by 13,11,7,5,3,2 respectively. If so add the number to the string c0
    Variable c1 contains the result.

    In this way the number of loops and the amount of loopcycles can be minimized, especially when the divisionnumber is 5 or 2

    Sub Euler43()
      Dim j As Long, jj As Long, jjj As Long, c0 As String
       
      For j = 17 To 999 Step 17
        If Replace(Replace(Format(j, “000”), Left(Format(j, “000”), 1), “”), Left(Replace(Format(j, “000”), Left(Format(j, “000”), 1), “”), 1), “”)  “” Then c0 = c0 & Format(j, “000”) & “|”
      Next
       
      For j = 1 To 7
        sq = Split(Left(c0, Len(c0) – 1), “|”)
        c0 = “”
        For jj = 0 To UBound(sq)
          For jjj = 0 To 9 Step Choose(j, 1, 5, 1, 2, 1, 1, 1)
            If j < 7 And InStr(sq(jj), jjj) = 0 And Val(jjj & Left(sq(jj), 2)) Mod Choose(j, 13, 11, 7, 5, 3, 2) = 0 Then c0 = c0 & jjj & sq(jj) & “|”
            If j = 7 And InStr(sq(jj), jjj) = 0 Then c1 = c1 + Val(jjj & sq(jj))
          Next
        Next
      Next
    End Sub

Leave a Reply

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