project euler-Problem 43

November 7, 2011
By

[This article was first published on YGC » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 their blog: YGC » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.



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.

Search R-bloggers

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)