Euler Problem 43 asks:
‘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.
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
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.
Ewwwww.
One word: recursion.
dbb – Your comment suggested a combined approach. This one runs in 78ms. Thanks.
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
Drat – those Cases Else are all ” mod n not equal to 0? and the ampersands are clear.
…mrt
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
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.
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.
I had to see how the VBA would look. The following requires a VBA project reference to the Windows Scripting Runtime.
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.
Wow. Fzz, that’s fast!
How do you include code in blog comments?
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!
Ekin: This blog uses iG:Syntax Hiliter at http://blog.igeek.info/still-fresh/2006/02/25/code-for-fun/
You might try http://www.codeplex.com/Highlight4Writer or http://www.hanselman.com/blog/BestCodeSyntaxHighlighterForSnippetsInYourBlog.aspx
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
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