R: Project Euler 30-39

problem30.R

limit <- 1
while (9^5*limit >= 10^limit) limit <- limit+1
n <- 2:(9^5*limit)
f <- function(x, y) (x %/% 10^y %% 10)^5
sum(n[n == rowSums(outer(n, limit:0, f))])

problem31.R

answer <- 2
coin <- c(2, 5, 10, 20, 50, 100)
s <- sapply(coin, function(x) list(c(x, x)))
while (length(s) > 0) {
	top <- s[[1]]
	s <- s[-1]
	if (top[1] > 200) next
	answer <- answer + 1
	for (n in coin[coin <= top[2]]) s <- c(list(c(n+top[1], n)), s)
}
answer

problem32.R

library(pracma)

x <- colSums(t(perms(1:9))*(10^(8:0)))
n <- x[
	(x%/%1e7*((x%/%1e4)%%1e3) == x%%1e4) |
	(x%/%1e8*((x%/%1e4)%%1e4) == x%%1e4)
]
sum(unique(n%%1e4))

problem33.R

library(gmp)

answer <- as.bigq(1,1)
a <- (a <- 10:99)[a%%10 != 0]
for (x in a) for (y in a[a > x]) {
	n <- as.bigq(x,y)
	x1 <- x%/%10; x2 <- x%%10; y1 <- y%/%10; y2 <- y%%10
	if (	(x1 == y2 && as.bigq(x2,y1) == n) ||
		(x2 == y1 && as.bigq(x1,y2) == n)
	) answer <- answer*n
}
denominator(answer)

problem34.R

limit <- 1
while (limit*factorial(9) > 10^limit) limit <- limit + 1

value <- function(n) {
	if (length(n) < 2) return(0)
	answer <- sum(factorial(n))
	d <- answer%/%10^(floor(log10(answer)):0)%%10
	if (length(n) != length(d)) return(0)
	if (all(n == sort(d))) answer else 0
}
 
nexts <- function(x) sapply(tail(x,1):9, function (i) list(append(x,i)))
 
answer <- 0
s <- sapply(0:9, list)
while (length(s) > 0) {
	top <- s[[1]]
	s <- s[-1]
	if (length(top) < limit) {
		answer <- answer + value(top)
		s <- c(nexts(top), s)
	}
}
answer

problem35.R

library(gmp)

isAnswer <- function(x) {
	if (length(x) == 1) return(FALSE)
	for (n in 1:length(x)) {
		y <- c(tail(x,n), head(x,length(x)-n))
		n <- sum(y*(10^((length(y)-1):0)))
		if (isprime(n) == 0) return(FALSE)
	}
	TRUE
}

nexts <- function(x) sapply(c(1,3,7,9), function(y) list(c(x,y)))

answer <- 4
stack <- sapply(c(1,3,7,9), list)
while (length(stack) > 0) {
	top <- stack[[1]]; stack <- stack[-1]
	if (isAnswer(top)) answer <- answer + 1
	if (length(top) < 6) stack <- c(nexts(top), stack)
}
answer

problem36.R

d2i <- function(x) sum(x * 10^((length(x)-1):0))
nexts <- function(x) sapply(0:9, function(n) list(c(n, x)))

nums <- numeric(0)
s <- sapply(c(1,3,5,7,9), list)

while(length(s) > 0) {
	top <- s[[1]]; s <- s[-1]
	x <- c(rev(top), top); y <- c(rev(top[-1]), top)
	nums <- c(nums, d2i(x), d2i(y))
	if (length(top) < 3) s <- c(nexts(top), s)
}

palindrome <- function(n) {
	x <- numeric(0)
	while (n > 0) {x <- c(x, n%%2); n <- n%/%2}
	all(x == rev(x))
}

sum(nums[sapply(nums, palindrome)])

problem37.R

library(gmp)

isAnswer <- function(n) {
	while (n > 0) {
		if (isprime(n) == 0) return(FALSE)
		n <- n%/%10
	}
	TRUE
}

nexts <- function(n) c(1,2,3,5,7,9) * 10^(floor(log10(n))+1) + n

answer <- numeric(0)
s <- c(2,3,5,7)
while (length(s) > 0) {
	top <- s[1]; s <- s[-1]
	if (isAnswer(top)) answer <- c(answer, top)
	if (isprime(top) > 0) s <- c(nexts(top), s)
}

sum(answer[answer > 9])

problem38.R

concat <- function(x) {
	answer <- x
	n <- 2
	while(answer < 1e8) {
		y <- x*n
		answer <- answer * (10^(floor(log10(y))+1)) + y
		n <- n+1
	}
	answer
}

pandigital <- function(n) {
	setequal(n %/% 10^floor((log10(n)):0) %% 10, 1:9)
}

xs <- (xs <- sapply(1:9876, concat))[xs < 1e9]

for (x in sort(xs, decreasing=TRUE)) {
	if (pandigital(x)) {answer <- x; break}
}

answer

problem39.R

children <- function(t) c(
list(c( t[1]-2*t[2]+2*t[3],  2*t[1]-t[2]+2*t[3],  2*t[1]-2*t[2]+3*t[3])),
list(c( t[1]+2*t[2]+2*t[3],  2*t[1]+t[2]+2*t[3],  2*t[1]+2*t[2]+3*t[3])),
list(c(-t[1]+2*t[2]+2*t[3], -2*t[1]+t[2]+2*t[3], -2*t[1]+2*t[2]+3*t[3]))
)

c <- numeric(1000)

check <- function(x) {
	y <- (n <- 1) * x
	while (y <= 1000) {c[y] <<- c[y]+1; y <- (n <- n+1) * x}
}

s <- list(c(3,4,5))
while (length(s) > 0) {
	top <- s[[1]]; s <- s[-1]
	x <- sum(top)
	if (x <= 1000) {check(x); s <- c(children(top), s)}
}

which.max(c)