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

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, 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.

Sponsors

Mango solutions



plotly webpage

dominolab webpage



Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training

datasociety

http://www.eoda.de





ODSC

ODSC

CRC R books series





Six Sigma Online Training









Contact us if you wish to help support R-bloggers, and place your banner here.

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)