Euler problem 43. Sub-string divisibility
Ok. Take all numbers that contains the ten digits 0:9 exactly once.
Lets call position 1 in such a number d1, position 2 d2 etc.
Of these numbers, sum the numbers that satisfies a set of conditions. The conditions are, that 1. d2d3d4 is divisible by 2 2. d3d4d5 is divisible by 3 3. d4d5d6 is divisible by 5 4. d5d6d7 is divisible by 7 5. d6d7d8 is divisible by 11 6. d7d8d9 is divisible by 13 7. d8d9d10 is divisible by 17
This could be done by hand.
From condition 3, we know that d6 is either 0 or 5, but combined with condition 5, if d6 is 0, the only values for d7d8 that are divisible by 11 would be 011, 022 etc.
That would violate restriction 0 - a digit can only occur once. So d6 must be 5.
It is possible to pare it all down in this way.
However, I solve these problems as a way of training programming. So…
What I need is all the allowed numbers:
library(gtools) test <- permutations(10,10,c(0:9))
Permutations(n,m,v) takes a vector v with length n, and returns all permutations of m elements from the vector.
test now contains the 3628800 numbers that are pandigital 0:9.
What is even better, is that I get them in a nice matrix. So it is easy to subset based on the restrictions.
Condition 1, d4 must be equal:
test <- subset(test,test[,4]%in%c(0,2,4,6,8))
Next condition 2, d3d4d5 must be divisible by 3. Or:
(d3100 + d410 + d5)%%3 == 0
test <- subset(test,((test[,3]100+test[,4]10+test[,5])%%3)==0)
Condition 3. d6 is either 0 or 5:
test <- subset(test,test[,6]%in%c(0,5))
Yeah, I know that 0 is not allowed.
Condition 4 - the same as condition 2, just with d5,d6 and d7. And modulus 7
test <- subset(test, ((test[,5]100+test[,6]10+test[,7])%%7)==0)
Condition 5 - now I won’t explain that again, it’s the same procedure as last time:
test <- subset(test, ((test[,6]100+test[,7]10+test[,8])%%11)==0)
Condition 6:
test <- subset(test, ((test[,7]100+test[,8]10+test[,9])%%13)==0)
And finally condition 7:
test <- subset(test, ((test[,8]100+test[,9]10+test[,10])%%17)==0)
Lets collapse the digits to numbers:
res <- apply(test,1,paste, collapse=““)
And convert them to numeric:
res <- as.numeric(res)
And finally sum them:
answer <- sum(res)
Super simple. The permuations could of course be optimized. If I instead get all the permutations of c(0:4,6:9), and then insert 5 in the appropriate column, I save some time. Making all the 3628800 permutations takes a little while.
Lessons learned
This was a good exercise in using subset. And also in using matrices instead of dataframes for everything.