project euler-Problem 43

November 7, 2011
By

(This article was first published on YGC » R, and kindly contributed to R-bloggers)

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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

    d2d3d4=406 is divisible by 2
    d3d4d5=063 is divisible by 3
    d4d5d6=635 is divisible by 5
    d5d6d7=357 is divisible by 7
    d6d7d8=572 is divisible by 11
    d7d8d9=728 is divisible by 13
    d8d9d10=289 is divisible by 17

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

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
rmDup <- function(vec) {
    idx <- sapply(vec, function(n) {
        nv <- unlist(strsplit(as.character(n), split=""))
        return(length(unique(nv)) == length(nv))
    }
                  )
   return(vec[idx])
}
 
n <- 102:999
prime <- c(13,11,7,5,3,2)
d <- n[ n %% 17 ==0]
d <- rmDup(d)
 
retain <- c()
for (i in 1:length(prime)) {
    for (j in  d) {
        lastdigits <- j %% 10^i
        first2digit <- (j-lastdigits)/10^i
        for (n in 0:9) {
            m <- n*100+first2digit
            if( m %% prime[i] ==0 ) {
                retain <- c(retain,m*10^i+lastdigits)
            }
        }
    }
    d <- rmDup(retain)
    if (i != length(prime))
        retain <- c()
}
 
s <- 0
for (i in d) {
    if(nchar(as.character(i)) == 9) {
        xx <- 0:9
        firstDigit <- xx[!xx %in% unlist(strsplit(as.character(i), split=""))]
        s <- s+ firstDigit*10^9+i
    }
    if(nchar(as.character(i)) == 8) {
        xx <- 1:9
        firstDigit <- xx[!xx %in% unlist(strsplit(as.character(i), split=""))]
        if(length(firstDigit) == 1)
            s <- s+ firstDigit*10^9+i
    }
}
 
print(s)

The implementation is not elegant, but amazingly fast.

> system.time(source("Problem43.R"))
[1] 16695334890
   user  system elapsed 
      0       0       0 

Related Posts

To leave a comment for the author, please follow the link and comment on his blog: YGC » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.